Сортировка вставкой и сортировка по выбору

Я пытаюсь понять разницу между сортировкой вставкой и сортировкой по выбору.

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

Сортировка выбора:

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

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

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

Время Сложность сортировки выбора есть всегда n(n - 1)/2, тогда как сортировка вставкой имеет лучшую временную сложность, поскольку ее сложность наихудшего случая n(n - 1)/2. Обычно тогда требуется меньшее или равное сравнение n(n - 1)/2.

Источник: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

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

Разница в том, что делает внутренний цикл:

• При сортировке выбора внутренний цикл проходит по несортированным элементам. Каждый проход выбирает один элемент и перемещает его в его окончательное положение (в текущем конце отсортированной области).

• При сортировке вставкой каждый проход внутреннего цикла выполняет итерацию по отсортированным элементам. Отсортированные элементы перемещаются, пока цикл не найдет правильное место для вставки следующего несортированного элемента.

Таким образом, при сортировке по выбору отсортированные элементы находятся в порядке вывода и остаются на месте, как только они будут найдены. И наоборот, при сортировке вставкой несортированные элементы остаются на месте до тех пор, пока не будут использованы в порядке ввода, в то время как элементы отсортированной области продолжают перемещаться.

Что касается свопинга: сортировка выбора выполняет одну замену за проход внутреннего цикла. Сортировка вставкой обычно сохраняет вставляемый элемент, как temp до внутреннего цикла, оставляя место для внутреннего цикла, чтобы сдвинуть отсортированные элементы вверх на один, а затем копировать tempв точку вставки.

СОРТИРОВКА
ПО ВЫБОРУ Предположим, что существует массив чисел, записанных определенным / случайным образом, и допустим, что мы должны расположить их в порядке возрастания… поэтому возьмите одно число за раз и замените их наименьшим числом. имеется в списке. делая этот шаг, мы в конечном итоге получим желаемый результат.

СОРТИРОВКА ВСТАВКОЙ
Помня об аналогичном предположении, но с той лишь разницей, что на этот раз мы выбираем одно число за раз и вставляем его в предварительно отсортированную часть, что сокращает сравнения и, следовательно, более эффективно.

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

Самый простой способ понять алгоритмы сортировки - это часто получить подробное описание алгоритма (не расплывчатые вещи вроде «эта сортировка использует своп. Где-то. Я не говорю где»), получить несколько игральных карт (5-10 должно быть достаточно для простых алгоритмов сортировки) и запустите алгоритм вручную.

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

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

Сортировка вставкой может использовать подкачку во время фазы «сканирования», но не обязательно, и это не самый эффективный способ, если вы не сортируете массив с типом данных, который: (а) не может быть перемещен, а только скопирован или заменен; и (б) копировать дороже, чем менять местами. Если сортировка вставкой использует подкачку, способ ее работы заключается в том, что вы одновременно ищите место и помещаете туда новый элемент, многократно меняя местами новый элемент с элементом непосредственно перед ним, до тех пор, пока элемент перед ним больше, чем Это. Как только вы дойдете до элемента, который не больше, вы нашли правильное место и перейдете к следующему новому элементу.

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

• Сортировка вставкой : вставляет следующий элемент в правильную позицию;

• Сортировка по выбору : выбирает наименьший элемент и меняет его на текущий элемент;

Кроме того, сортировка вставкой является стабильной, в отличие от сортировки по выбору .

Я реализовал оба на Python, и стоит отметить, насколько они похожи:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

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

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

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

Коротко,

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

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

Я попробую еще раз: рассмотрим, что происходит в счастливом случае почти отсортированного массива.

При сортировке массив можно представить как состоящий из двух частей: левая часть - отсортированная, правая часть - несортированная.

Сортировка вставкой - выберите первый неотсортированный элемент и попытайтесь найти для него место среди уже отсортированных. Поскольку вы выполняете поиск справа налево, вполне может случиться так, что первый отсортированный элемент, с которым вы сравниваете (самый большой, самый правый в левой части), меньше, чем выбранный элемент, поэтому вы можете немедленно перейти к следующему несортированному элементу.

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

Кстати, это именно то, что heapsort улучшает сортировку выбора - он может находить самый маленький элемент намного быстрее из-за кучи .

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

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

Оба алгоритма обычно работают так

Шаг 1: возьмите следующий неотсортированный элемент из несортированного списка, затем

Шаг 2: поместите его в нужное место в отсортированном списке.

Один из шагов проще для одного алгоритма и наоборот.

Сортировка вставкой : берем первый элемент несортированного списка, помещаем его куда-нибудь в отсортированный список . Мы знаем, где взять следующий элемент (первая позиция в несортированном списке), но требуется некоторая работа, чтобы найти, где его разместить ( где-то ). Шаг 1 прост.

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

Внутренний цикл сортировки вставкой проходит через уже отсортированные элементы (в отличие от сортировки по выбору). Это позволяет ему прервать внутренний цикл при нахождении нужной позиции . Которое значит что:

1. Внутренний цикл в среднем проходит только половину своих элементов.
2. Внутренний цикл будет прерван еще раньше, если массив почти отсортирован.
3. Внутренний цикл будет немедленно прерван, если массив уже отсортирован, что делает сложность сортировки вставкой линейной в этом случае.

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

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

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

Сортировка вставкой может быть представлена ​​как:

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Сортировка выбора может быть представлена ​​как:

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

Выбор этих двух алгоритмов сортировки зависит от используемой структуры данных.

Когда вы используете массивы, используйте сортировку по выбору (хотя зачем, когда вы можете использовать qsort?). Когда вы используете связанные списки, используйте сортировку вставкой.

Это потому что:

• Обход связанных списков дороже массивов.
• Вставка связанного списка намного дешевле, чем массивы.

Сортировка вставкой вводит новое значение в середину отсортированного сегмента. Следовательно, данные необходимо «отодвинуть». Однако, когда вы используете связанный список, скручивая 2 указателя, вы фактически отодвигаете весь список назад. В массиве вы должны выполнить n - i замен, чтобы вернуть значения, что может быть очень дорогостоящим.

Сортировка выделения всегда добавляется в конец, поэтому при использовании массивов такой проблемы не возникает. Следовательно, данные не нужно «отбрасывать».

Простое объяснение может быть таким, как показано ниже:

Дано : несортированный массив или список чисел.

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

Сортировка вставкой:Вы видите список сверху вниз для облегчения понимания. Мы считаем первый элемент нашим начальным минимальным значением. Теперь идея состоит в том, что мы проходим по каждому индексу этого списка / массива линейно, чтобы узнать, есть ли какой-либо другой элемент в любом индексе, имеющий меньшее значение, чем начальное минимальное значение. Если мы находим такое значение, мы просто меняем местами значения по их индексам, т.е. допустим, 15 было минимальным начальным значением в индексе 1, и во время линейного обхода индексов мы встречаем число с меньшим значением, скажем 7 в индексе 9. Теперь это значение 7 в индексе 9 заменяется индексом 1, имеющим значение 15. Этот обход будет продолжать сравнивать значение текущего индекса с оставшимися индексами для замены на меньшее значение. Это продолжается до второго последнего индекса списка / массива,

Сортировка выбора:Предположим, что отсортирован первый элемент индекса списка / массива. Теперь, начиная с элемента во втором индексе, мы сравниваем его с его предыдущим индексом, чтобы увидеть, меньше ли значение. Обход можно разделить на две части: отсортированную и несортированную. Можно было бы визуализировать проверку сравнения от несортированного к отсортированному для данного индекса в списке / массиве. Допустим, у вас есть значение 19 в индексе 1 и значение 10 в индексе 3. Мы рассматриваем переход от несортированного к отсортированному, то есть справа налево. Итак, допустим, нам нужно отсортировать по индексу 3. Мы видим, что он имеет меньшее значение, чем индекс 1, если сравнивать справа налево. После идентификации мы просто помещаем это число 10 в индексе 3 на место индекса 1, имеющего значение 19. Исходное значение 19 в индексе 1 сдвигается на одну позицию вправо.

Я не добавил никакого кода, поскольку возникает вопрос о понимании концепции метода обхода.

Вставка сортировки не меняет местами. Несмотря на то, что он использует временную переменную, смысл использования temp var заключается в том, что когда мы обнаружили, что значение в индексе меньше по сравнению со значением в его предыдущем индексе, мы сдвигаем большее значение на место меньшего значения. index, который будет перезаписывать вещи. Затем мы используем временную переменную для замены в предыдущем индексе. Пример: 10, 20, 30, 50, 40. итерация 1: 10, 20, 30, 50, 50. [temp = 40] итерация 2: 10,20, 30, 40 (значение температуры), 50. Итак, мы просто вставьте значение в нужную позицию из некоторой переменной.

Но когда мы рассматриваем сортировку выбора, мы сначала находим индекс, имеющий более низкое значение, и меняем это значение со значением из первого индекса и продолжаем неоднократно менять местами, пока все индексы не будут отсортированы. Это точно так же, как и традиционная замена двух чисел. Пример: 30, 20, 10, 40, 50. Итерация 1:10, 20, 30, 40, 50. Здесь temp var используется исключительно для обмена.

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

Общее у них обоих то, что они оба используют раздел, чтобы различать отсортированную часть массива и несортированную.

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

Причина в том, что выбор ищет минимум несортированного набора и добавляет его сразу после последнего элемента отсортированного набора, тем самым увеличивая отсортированный набор на 1.

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

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

Вывод:

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

Сортировка вставкой распространяет первый элемент, найденный в несортированном разделе, в любое место отсортированного раздела.

Хотя временная сложность сортировки выбора и сортировки вставкой одинакова, то есть n (n - 1) / 2. Сортировка вставки средней производительности лучше. Протестировано на моем процессоре i5 со случайными 30000 целыми числами, сортировка по выбору занимала в среднем 1,5 с, а сортировка вставкой - в среднем 0,6 с.

С точки зрения непрофессионала (и, вероятно, самый простой способ достичь высокого уровня понимания проблемы)

Сортировка пузырьков похожа на то, чтобы стоять в очереди и пытаться отсортировать себя по высоте. Вы продолжаете переключаться с человеком рядом с вами, пока не окажетесь в нужном месте. Это происходит полностью слева (или справа в зависимости от реализации), и вы продолжаете переключаться, пока все не будут отсортированы.

Однако при сортировке выбора то, что вы делаете, похоже на раскладывание карт. Вы смотрите на карточки, берете самую маленькую, кладете ее до упора влево и так далее.

selection - выбор конкретного элемента (самого низкого) и его замена на элемент i (без итерации). (т.е. первое, второе, третье .......), следовательно, отсортированный список делается на одной стороне.

вставка - сравнение первого со вторым сравните третье со вторым и первым сравните четвертое с третьим, вторым и первым ...

ссылка, где сравниваются все сортировки