Сортировка вставками или пузырьковая сортировка?

@Guessst · Регистрация: 06.02.2014

Здравствуйте! Подскажите пожалуйста, правильно ли что это код сортировки вставками или же это пузырьковая сортировка?

Java

1
2
3

for(int i=1;i<n;i++)     
    for(int j=i;j>0 && x[j-1]>x[j];j--) // пока j>0 и элемент j-1 > j, x-массив int
            swap(x[j-1],x[j]);        // меняем местами элементы j и j-1

(Код больше похож на пузырьковую сортировку, чем на сортировку вставками, так как здесь происходит обмен соседних элементов как в пузырьковой сортировке, а не вставка элемента в нужное место как в сортировке вставками).
Данный код был приведен здесь: http://habrahabr.ru/post/181271/.
Здесь такой же псевдокод: http://neerc.ifmo.ru/wiki/inde... 0%BC%D0%B8.
Во всех остальных местах приведен такой код сортировки вставками:

Кликните здесь для просмотра всего текста

Java

public static void insertionSort(int[] arr) {
    for(int i = 1; i < arr.length; i++){
        int currElem = arr[i];
        int prevKey = i - 1;
            while(prevKey >= 0 && arr[prevKey] > currElem){
                arr[prevKey+1] = arr[prevKey];
                arr[prevKey] = currElem;
                prevKey--;
            }
    }
}

@mocivan · 07.08.2015, 18:16

пузырьки.начните с определений. сразу станет понятно.

Кликните здесь для просмотра всего текста

https://ru.wikipedia.org/wiki/Сортировка_пузырьком
https://ru.wikipedia.org/wiki/Сортировка_вставками

@Guessst · 07.08.2015, 19:08 **[ТС]**

Именно после прочтения определений сортировки пузырьком и вставками и возник этот вопрос. Почему только на этих двух сайтах (приведенных мною выше) код алгоритма вставками написан так:

Java

1
2
3

for(int i=1;i<n;i++)     
    for(int j=i;j>0 && x[j-1]>x[j];j--) // пока j>0 и элемент j-1 > j, x-массив int
            swap(x[j-1],x[j]);        // меняем местами элементы j и j-1

После запуска данного кода стало видно, что он работает как пузырьковая сортировка.
А вот этот код (приведенный на большинстве сайтов):

Кликните здесь для просмотра всего текста

Java

public static void insertionSort(int[] arr) {
    for(int i = 1; i < arr.length; i++){
        int currElem = arr[i];
        int prevKey = i - 1;
            while(prevKey >= 0 && arr[prevKey] > currElem){
                arr[prevKey+1] = arr[prevKey];
                arr[prevKey] = currElem;
                prevKey--;
            }
    }
}

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

@mocivan · 07.08.2015, 22:57

Guessst, если делается так, то это определенно пузырек

Сообщение от Guessst

swap(x[j-1],x[j]);

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

@mocivan 95 / 95 / 50 Регистрация: 07.07.2015 Сообщений: 208
	07.08.2015, 18:16	2
	пузырьки.начните с определений. сразу станет понятно. Кликните здесь для просмотра всего текста https://ru.wikipedia.org/wiki/Сортировка_пузырьком https://ru.wikipedia.org/wiki/Сортировка_вставками 0

@mocivan 95 / 95 / 50 Регистрация: 07.07.2015 Сообщений: 208
	07.08.2015, 22:57	4
	Guessst, если делается так, то это определенно пузырек Сообщение от Guessst swap(x[j-1],x[j]); чтобы была вставка, надо значение для вставки куда-то сохранять и потом его вставлять в нужное место, что требует более интересной логики, чем просто swap. Фактически в первоначальном примере была попытка реализации вставки с помощью пузырька 1

Опции темы