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

1. Линейный выбор. Суть алгоритма заключается в следующем: при одном просмотре списка выбирается минимальный (или максимальный) элемент, затем выбранный элемент списка заносится в выходной список, а на его место во входном списке заносится фиктивный ключ (+¥ или - ¥). Процедура повторяется до тех пор, пока во входном списке не будут все фиктивные ключи.

2. Линейный выбор с обменом. Последовательными сравнениями ищется минимальный (или максимальный) элемент массива, причем в процессе поиска запоминается индекс (номер) текущего минимального элемента. После того, как просмотрены все элементы, можно поменять местами 1-й элемент с наименьшим, индекс которого в этот момент известен. Затем эта процедура повторяется, начиная со 2-го, 3-го, и т.д. до N-1 элемента.

Пример:

5 2 4 1 3 исходный массив

_ 5 2 4 1 3 номер минимального элемента = 4

1 _ 2 4 5 3 номер минимального элемента = 2

1 2 _ 4 5 3 номер минимального элемента = 5

1 2 3 _ 5 4 номер минимального элемента = 5

1 2 3 4 5 упорядоченный массив

3. Метод стандартного обмена (метод "пузырька").Используяэтот метод будем производить последовательные просмотры элементов, и каждый раз, пара за парой сравнивать соседние ключи. Если значение ключей в паре расположены в порядке возрастания (убывания), то оставляем их без изменения, в противном случае меняем их местами и переходим к следующей паре. Сортировка считается оконченной, если в ходе просмотра не была произведена ни одна перестановка. Например:

Исходный массив 1 7 6 4 2 5

1-й просмотр 1 7 6 4 2 5

6 7 число

4 7 перестановок

2 7 равно 4

5 7

--------------

1 6 4 2 5 7

2-й просмотр 1 6 4 2 5 7

4 6 число

2 6 перестановок

5 6 равно 3

--------------

1 4 2 5 6 7

3-й просмотр 1 4 2 5 6 7 число

2 4 перестановок

равно 1

--------------

1 2 4 5 6 7

4-й просмотр 1 2 4 5 6 7 число

перестановок

равно 0

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

Например:

3 3 3 3 3 . 1

11 6 4 4 4 . 2

*6 11 6 6 5 . 3

4 *4 11 9 6 . 4

9 *9 11 9 . 5

5 *5 11 . 6

7 *7 . 7

8 . 8

10 . 9

2 . 10

1 . 11

5. Метод Шелла. Эта сортировка является расширением метода
просеивания. Список из N элементов разбивается на N/2 частей. Элемент
каждой части отстоит друг от друга на N/2 позиций.

Например:

Шаг = int (11/2) = 5

Шаг = int(5/2) = 2 шаг = int(2/2) = 1

3 1 1 1 1

11 7 7 3 2

6 6 2 2 3

4 4 4 4 4

9 2 5 5 5

5 3 3 7 6

7 11 6 6 7

8 8 8 8 8

10 10 10 10 9

2 9 9 9 10

1 5 11 11 11

Усовершенствованный метод использует последовательность шагов х_i, x_i =3*x_i-1 +1. Для х_i, получаем значения: х₁=1, х₂=4, xз=13, х4=40, x₅=121, x₆=364, x₇= 1093, ..... Предположим, что надо отсортировать 1000 значений. Ищем наименьшее х_m>1000, т.е. x₇=1093. Метод рассматривает шаги, начиная с 5, потому, что x_m-2=х_7-2=x₅ и до первого шага включительно.