Метод Хoopа

Метод Шелла

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

Метод пузырька (обменная сортировка с выбором)

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

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

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Этот метод, называемый также быстрой сортировкой(QuickSort), был разработан в 1962 г. (его разработал Charles Antony Richard Hoare).Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.

Сортировка вставкой. Сортировка выбором.

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

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

· количество присваиваний;

· количество сравнений.

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

· прямые методы сортировки;

· улучшенные методы сортировки.

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

1. сортировка вставкой (включением);

2. сортировка выбором (выделением);

3. сортировка обменом (так называемая "пузырьковая" сортировка).

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

Рассмотрим сортировку методом выбора.

Принцип метода заключается в следующем:

При сортировке, начиная с первого элемента последовательности, осуществляется поиск наименьшего элемента массива, после чего этот наименьший элемент меняем местами с первым из рассматриваемых элементов. Так как наименьший элемент массива после перестановки размещается на первом месте, то дальнейший поиск минимального из оставшихся элементов начинаем со второго элемента и меняем их местами (второй с наименьшим из оставшихся). Повторяя указанные операции с изменением точки отсчета начала поиска минимального из оставшихся (3-ий, 4-ый,…N-1-ый элемент), получим отсортированный по возрастанию массив.

Private Sub Command1_Click()

Cls

Dim I As Integer

Dim x(100) As Integer

For I = 1 To 10

x(I) = Rnd() * 100

Next I

For I = 1 To 10

Print x(I);

Next I

Print

For I = 1 To 9

Min = x(I)

For J = I To 10

If x(J) <= Min Then Min = x(J): k = J

Next J

x(k) = x(I)

x(I) = Min

Next I

For I = 1 To 10

Print x(I);

Next I

End Sub

Задание. Составьте программу сортировки одномерного массива рассмотренным методом по убыванию

Сортировка методом простого обмена (пузырька). Рекурсивная сортировка.

Принцип метода:

Расположим массив сверху вниз, от нулевого элемента - к последнему.

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

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

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

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.

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

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Private Sub Command1_Click()

Cls

Dim I As Integer

Dim x(100) As Integer

For I = 1 To 10

x(I) = Rnd() * 100

Next I

For I = 1 To 10

Print x(I);

Next I

Print

For I = 1 To 9

For J = I To 9

If x(I) <= x(J + 1) Then GoTo M:

p = x(I)

x(I) = x(J + 1)

x(J + 1) = p

M:

Next J: Next I

For I = 1 To 10

Print x(I);

Next I

End Sub

Сортировка массива простыми вставками.

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность...

Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.
Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.
В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.

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

1. Hайден элемент, меньший x или

2. Достигнуто начало последовательности.

Private Sub Command1_Click()

Cls

Dim I As Integer

Dim x(100) As Integer

For I = 1 To 10

x(I) = Rnd() * 100

Next I

For I = 1 To 10

Print x(I);

Next I

Print

For I = 2 To 10

For J = I - 1 To 1 Step -1

If x(I) > x(J) Then GoTo M:

Next J

J = 0

M:

b = x(I)

For k = I To J + 2 Step (-1)

x(k) = x(k - 1)

Next k

x(J + 1) = b

Next I

For I = 1 To 10

Print x(I);

Next I

End Sub

Дата добавления: 2014-01-06