Что это за алгоритм сортировки?

Question

Обновление: ОК. Я вижу, что это пузырьковая сортировка, но разве она менее эффективна, потому что она не останавливается, когда на конкретном прогоне нет свопа? Он работает до тех пор, пока первый не станет нулевым.

Привет, у меня есть алгоритм сортировки следующим образом. У меня вопрос, какой алгоритм сортировки это? Я думал, что это пузырьковая сортировка, но она не выполняет несколько прогонов. Любая идея? Спасибо!

//sorting in descending order
struct node
{
    int value;
    node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers

Sort( Node *Head)
{
    node* first,second,temp;
    first= Head;
    while(first!=null)
    {
        second=first->NEXT;
        while(second!=null)
        {
            if(first->value < second->value)
            {
                temp = new node();
                temp->value=first->value;
                first->value=second->value;
                second->value=temp->value;
                delete temp;
            }
            second=second->NEXT;
        }

        first=first->NEXT;
    }
}

Answer 1

Давайте сделаем алгоритм более понятным:

Sort {
   first = head;
   while (first ≠ NULL) {
      next = first.next
      while (next ≠ NULL) {
         if (first.value < next.value)
            swap first.value and next.value
         advance next
      }
      advance first
   }
}

Это очень неэффективная реализация сортировки вставкой.

---

Пример прогона с выявлением характеристик сортировки вставки:

5 → 2 → 3 → 1 → nil
^   ^
f   n [swap]

2 → 5 → 3 → 1 → nil
^       ^
f       n

2 → 5 → 3 → 1 → nil
^           ^
f           n [swap]

1 → 5 → 3 → 2 → nil
^               ^
f               n

1 → 5 → 3 → 2 → nil   // insert the minimum value 1 to the beginning of the sublist
    ^   ^
    f   n [swap]

1 → 3 → 5 → 2 → nil
    ^       ^
    f       n [swap]

1 → 2 → 5 → 3 → nil  // insert the minimum value 2 to the beginning of the sublist
    ^           ^
    f           n

1 → 2 → 5 → 3 → nil
        ^   ^
        f   n [swap]

1 → 2 → 3 → 5 → nil  // insert the minimum value 3 to the beginning of the sublist
        ^       ^
        f       n

1 → 2 → 3 → 5 → nil  // insert the minimum value 5 to the beginning of the sublist
            ^   ^
            f   n

1 → 2 → 3 → 5 → nil
                ^
                f

Answer 2

Это своего рода гибрид между 'классической' пузырьковой сортировкой и выборочной сортировкой - но ближе к классической пузырьковой сортировке.

В классической пузырьковой сортировке внутренний цикл меняет соседние пары при обходе списка / массива.

В классической сортировке выбора внутренний цикл отслеживает наибольшее значение, которое он находит в оставшейся части списка, и заменяет его первым значением в той части списка, которую внутренний цикл в настоящее время рассматривает.

Сортировка, опубликованная в вопросе, похожа на сортировку Selection, в которой обмен всегда выполняется с первым значением в подсписке, которое рассматривает внутренний цикл. Он отличается от сортировки «Выбор» (и похож на классическую сортировку «Пузырьки») тем, что выполняет своп всякий раз, когда находит значение, превышающее текущий первый член подсписка внутреннего цикла.

Однако он отличается от классического типа Bubble тем, что не обменивается соседними парами. В классической Bubble-сортировке, когда внутренний цикл завершил работу с циклом, самый большой элемент списка отфильтровывался до нижней части списка, но в этом варианте самый маленький элемент отфильтровывался до верхней части подсистемы внутреннего цикла. -лист.

Я бы назвал это скорее вариацией классической сортировки Bubble, а не сортировки Selection, потому что рабочие характеристики сортировки в вопросе такие же, как у классической сортировки Bubble (O(n^2) сравнения и O(n^2) перестановки) в то время как сортировка выбора имеет O(n) перестановок.

Но есть еще одно различие между классической сортировкой Bubble и этой в том, что классическая сортировка Bubble стабильна , тогда как сортировка в вопросе - нет. Рассмотрим следующий список элементов при выполнении сортировки. В сравнении используются только цифры - буквы используются только для различения элементов, имеющих одинаковый ранг. Диаграммы показывают выполненные операции свопинга (для краткости сравнения не показаны):

3.a  3.b   3.c   2.a   2.b   1.a
 ^                ^
 +----------------+


2.a  3.b   3.c   3.a   2.b   1.a
 ^                            ^
 +----------------------------+


1.a  3.b   3.c   3.a   2.b   2.a
      ^                 ^
      +-----------------+


1.a  2.b   3.c   3.a   3.b   2.a
            ^                 ^
            +-----------------+


1.a  2.b   2.a   3.a   3.b   3.c

Обратите внимание, что в конце сортировки относительное положение элементов 2.a и 2.b изменилось, что указывает на нестабильную сортировку.

Answer 3

Это в значительной степени пузырьковая сортировка. Сортировка пузырьков выполняется в связанном списке, где значения меняются местами. Проверка node!=null предназначена для подтверждения того, достигнут конец или нет.

Answer 4

Сортировка вставок

Это очень похоже на пузырьковую сортировку, за исключением того, что вместо разбрасывания смежных пар элементов вы перемещаете самый маленький элемент в начало списка, а затем следующий самый маленький элемент во вторую позицию и т. Д. *

Answer 5

Это похоже на выбор сортировки . В сортировке выбора мы находим минимальное значение в списке, меняем местами первый элемент и повторяем то же самое для других элементов в списке. Но там мы не меняем местами после нахождения элемента min, вместо этого каждый раз, когда мы находим элемент меньше первого элемента (в первом проходе), мы меняем его на 1-й элемент.