Методы сортировки


Download 194.81 Kb.
bet6/10
Sana04.10.2022
Hajmi194.81 Kb.
#830160
1   2   3   4   5   6   7   8   9   10
Bog'liq
Продвинутые алгоритмы сортировки. Простые методы сортировки. Сортировать по выбору.
dwg fayl, Тарийх кк-тилинде, Hujjat (8), Hujjat (8), 1-лекция, 2-tema, ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), Cv, Cv, amaliy

Сортировка вставками


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

  • 3 5 7 8 4 2 1 9 6: выбираем 4 и помним, что это элемент, который нужно вставить. 8 > 4, поэтому сдвигаем.

  • 3 5 7 x 8 2 1 9 6: здесь x – нерешающее значение, так как элемент будет перезаписан (на 4, если это подходящее место, или на 7, если смещение). 7 > 4, поэтому сдвигаемся.

  • 3 5 x 7 8 2 1 9 6

  • 3 x 5 7 8 2 1 9 6

  • 3 4 5 7 8 2 1 9 6

Теперь вы видите, что отсортированная часть дополнилась элементом. Каждая следующая итерация делает то же самое, и к концу вы получите отсортированный массив!

Реализация



Временная сложность


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

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


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

1   2   3   4   5   6   7   8   9   10




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling