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


Download 194.81 Kb.
bet1/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.1.Метод пузырька.


Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Последовательность из N элементов данных просматривается от начала до конца так, что стоящие рядом элементы меняются местами, если первый из них меньше ("легче") второго. Таким образом, после такого просмотра самый "легкий" элемент "выталкивается" в конце последовательности.
Если теперь повторить такой просмотр еще N – 1 раз, то, очевидно, что вся заданная последовательность окажется от сортированной. Этот алгоритм можно несколько оптимизировать двумя добовлениями:

  1. Просматривая на k-м проходе не весь массив, а только элементы с первого до (N-k+1)-го;

  2. Повторяя просмотр не N раз, а лишь до тех пор, пока при очередном просмотре не произойдет ни одной перестановки.

Download 194.81 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9   10




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