Вставка сортировки или вариант выбора сортировки?

Question

У меня есть фрагмент кода here. Протестировал его в нескольких случаях, кажется, работает нормально.

Я написал код за один раз для сортировки вставки после изучения алгоритма, но есть вопрос, действительно ли это традиционная сортировка вставки?

У меня такое ощущение, что это может быть вариант (измененная версия) выбора, который является причиной моего замешательства.

В частности, это вызывает озабоченность: (С учетом массивом a из n элементов)

for(i=1;i<n;i++){ 
    for(j=0;j<i;j++){ 
     if(a[i] < a[j]){ 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
     } 
    }  
} 

Кроме того, является количество сравнений или свопов более/менее с этим своего родом подходит?

Заранее благодарим за помощь.

Answer 1

Самый прямой ответ на ваш вопрос да, это сортировка вставкой. Это очень неэффективный вставка сортировка, но тем не менее insertion сортировать.

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

Возможно, это показалось мне немного запутанным, поэтому я буду разбираться с вашим кодом.

• Ваш потенциальный элемент для каждой итерации i изначально a[i].
• Вы Перечислите линейно над уже отсортированной частью вашей последовательности, ища, где a[i] принадлежит
• После того, как вы нашли место (если он уже не где она принадлежит), нужно поменять местами a[i] с элементом a[j], который в настоящее время проживает в вашей цели.
• С этого момента, первоначальное значение a[i] теперь на месте в последовательности, но ...
• Для оставшейся части отсортированной последовательности, своп-сравнение гарантированно срабатывает, как истинный (подсказка: так зачем это делать?) против любого значения, хранящегося в a[i], потому что ранее сохраненные ранее значения уже были отсортированы. Поэтому a[i] постоянно заменяется следующим значением в отсортированной последовательности до тех пор, пока в конце концов оно не будет иметь наибольшее значение, которое по определению будет принадлежать.

Таким образом, да, это вставка-сортировка. Он поддерживает отсортированную последовательность в начале целого, которая когда-либо расширяется с каждой первичной итерацией. И для каждой первичной итерации элемент перспективы «вставлен», а задние элементы сдвигаются вниз, чтобы сделать доступное отверстие для этого.

... это количество сравнений или свопов больше/меньше с помощью этого рода-подхода?

Значительно требуется больше сравнений с вашим подходом. Каждой итерации гарантируется линейная сложность O (n), и есть итерации n. Таким образом, вы гарантировали, чтобы иметь O (N^2) сложность для ваших сравнений, которая является чумой эффективных алгоритмов сортировки. Не только худший случай; гарантировано.

---

C++ Вставка Сортировать

Тем не менее, считают это

template<typename Iter> 
void insertion_sort(Iter first, Iter last) 
{ 
    for (Iter it = first; it != last; ++it) 
     std::rotate(std::upper_bound(first, it, *it), it, std::next(it)); 
} 

Это, вероятно, seems like Greek (не в обиду греки), если вы только начинаете в C++, но не использует два фундаментальных алгоритма, которые делают его неожиданно эффективным: std::upper_bound и std::rotate.

std::upper_bound работает на отсортированной последовательности. Воспользовавшись этим, он может использовать алгоритм двоичного поиска , чтобы найти первый элемент в отсортированной последовательности, который строго превышает значение перспективы (*it). Поэтому поиск точки вставки для одной перспективы - O (logN), намного лучше, чем линейный поиск O (n).

Как только точка ввода известна, std::rotate используется для установки элемента на месте с использованием итератора точки вставки.Это эффективно делает это:

0 1 2 3 5 6 4 
     ^^ * these will be rotated right one element 

0 1 2 3 5 6 
      4 

0 1 2 3 5 6 
     4 

0 1 2 3 4 5 6 

Обратите внимание, что вращение не требует не сравнений.

Очевидно, что это решение шаблона - это не то, что кто-то будет подавать на курс исправления алгоритмов. Но я надеюсь, что это даст вам несколько идей о том, как свертывание сортировки может сводиться к минимуму:

• Использование двоичного поиска в уже отсортированной части последовательности для минимизации сравнений.
• Использование no сравнение при выполнении вращения.

Удачи.

Answer 2

Этот код представляет собой реализацию вставки-сортировки. Посмотрите на внутренний цикл:

for(j=0;j<i;j++){ 
    if(a[i] < a[j]){ 
     temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 
} 

или упрощены:

for(j = 0; j < i ; j++) 
    if(a[i] < a[j]) 
     swap(a[i], a[j]); 

Теперь мы знаем, что подмассив a[0:i - 1] уже отсортирован от предыдущего запуска внешнего контура. Это логически golfed версия нахождения индекса n, при которой нам нужно вставить a[i] и толкая все элементы с индексом в диапазоне [n, i - 1] один показатель выше:

while(j < i && a[j] <= a[i]) 
    j++; 

//insert a[i] at the appropriate index 
int tmp = a[j]; 
a[j] = a[i]; 

//push all elements starting from index n one index further 
for(; j < i; j++){ 
    int swap = tmp; 
    tmp = a[j]; 
    a[j] = swap; 
} 

Логическая эквивалентность этих двух фрагментов кода является следующие:
До нужного индекса n (индекс вставки для a[i]), никаких свопов не произойдет. Теперь мы заменили a[i] и a[n]. С этого момента a[i] будет эквивалентен tmp -переменной в приведенном выше коде. Поскольку остальная часть массива по-прежнему сортируется по индексу i - 1, теперь мы заменяем каждый элемент на его предыдущий элемент, который в настоящее время хранится в индексе i. Определенно некоторые красиво вставляемые вставки.

Внешний контур только стандартный

for(i = 0; i < array_length; i++) 
    insert a[i] at appropriate position