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

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

10 40 04 05 01 21 01

10 40 04 05 ∞ 21 01 04

10 40 ∞ 05 ∞ 21 01 04 05

10 40 ∞ ∞ ∞ 21 01 04 05 10

∞ 40 ∞ ∞ ∞ 21 01 04 05 10 21

∞ 40 ∞ ∞ ∞ ∞ 01 04 05 10 21 40

∞ ∞ ∞ ∞ ∞ ∞ 01 04 05 10 21 40

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

Дано: Множество элементов М={M[1], M[2], …, M[n]}.

Необходимо: Упорядочить это множество по убыванию (по возрастанию действия будут выполняться по аналогичной схеме).

Схема сортировки следующая:

1. Пусть i – номер элемента в массиве М. На первом шаге i=1.

2. Найти максимальный элемент в множестве М[i], M[i+1], …, M[n].

3. Поменять его местами с первым элементом М[i].

4. Увеличить i на единицу (то есть, i:=i+1).

5. Выполнять шаги 2-4 пор тех пор, пока i не станет равно n; в этом случае, на последнем месте будет находиться минимальный элемент.

Оценим данный алгоритм:

Шаги 1-2 будут повторяться: Если n – количество элементов в последовательности.

Сначала (n-1), потом (n-2), потом (n-3), … 2, 1 раз. То есть мы имем:

n-1+n-2+n-3+… +2+1=n(n-1)/2=(n²-n)/2

То есть оценка этого алгоритма сортировки == О((n²-n)/2).

• Сравнительный анализ методов сортировки.

Сконцентрируем свое внимание на общей эффективности каждого алгоритма.

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет (n²-n)/2 сравнений, где n — количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n - 1 раз, а внутренний выполняется в среднем n/2 раз. Произведение этих величин и дает предыдущее выражение.

Обратите внимание на член n² в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n², поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n² не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов.

Шейкер-сортировка и является улучшенным вариантом по сравнению с пузырьковой сортировкой, но она по-прежнему имеет время выполнения порядка n². Это объясняется тем, что количество сравнений не изменилось, а количество обменов уменьшилось лишь на относительно небольшую константу. Шейкер-сортировка лучше пузырьковой, но есть еще гораздо лучшие алгоритмы сортировки.

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

В отличие от пузырьковой сортировки и сортировки посредством выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n - 1; в противном случае его производительность является величиной порядка n².

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

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