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

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

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

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

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

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

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

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

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

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