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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

Кроме того, Сортировка вставки стабильна, в отличие от Выбор Сортировка.

Я реализовал оба в 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

Ответ 6

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

Ответ 7

Короче говоря,

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

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

Ответ 8

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

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

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

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

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

Ответ 9

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

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

Ответ 10

Оба алгоритма обычно работают следующим образом

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

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

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

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

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

Ответ 11

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

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

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

Ответ 12

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

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

Вставка сортировки может быть показана как:

    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;

Ответ 13

Я использовал Java для реализации сортировки сортировки и выбора сортировки. введите описание изображения здесь

введите описание изображения здесь

Ответ 14

Простое объяснение может быть следующим:

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

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

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

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

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

Ответ 15

Вставка сортировки не меняются местами. Несмотря на то, что в нем используется переменная temp, смысл использования temp var заключается в том, что, когда мы обнаружили, что значение индекса меньше по сравнению со значением предыдущего индекса, мы перемещаем большее значение в место меньшего значения. индекс, который бы переписать вещи. Затем мы используем временную переменную для подстановки в предыдущем индексе. Пример: 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 используется исключительно для замены.

Ответ 16

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

Ответ 17

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

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

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

Ответ 18

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

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

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