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

@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
1
2
3
4
5
6
7
8
9
10
11
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
1
2
3
4
5
6
7
8
9
10
11
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. Фактически в первоначальном примере была попытка реализации вставки с помощью пузырька

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

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