 |
1.2.3. Сортировка вставками. 1.2.4. Метод Шелла (сортировка с убывающим шагом). 1.2.5. Сортировка слиянием
|
|
|
|
1. 2. 3. Сортировка вставками
При сортировке вставками записи просматриваются по одной и каждая новая запись вставляется на надлежащее место среди ранее упорядоченных записей.
Известны следующие методы сортировки вставками: простая вставка, бинарная вставка, метод Шелла и др., различающиеся способами поиска подходящего места для вставки элемента.
Алгоритм сортировки простыми вставками проходит через этапы j=2, 3,..., N. На j-м этапе запись Х(J) вставляется на свое правильное место среди Х(1), Х(2),..., Х(j-1). При вставке запись Х(j) временно размещается в S и просматриваются записи Х(j-1), Х(j-2),..., Х(1); их ключи сравниваются с ключом T записи S и записи сдвигаются вправо, если обнаруживается, что их ключи больше ключа записи S. Структурограмма алгоритма сортировки методом вставки представлена на рис. 5.
Пример. Исходная последовательность
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9) K(10) K(11)
3 11 6 4 9 5 7 8 10 2 1.
При J=2 элемент K(2) сравнивается с К(1), и так как К(2)> К(1), то вставки нет. При J=3 элемент К(3) сравнивается с К(2) и К(1) и вставляется на место второго элемента К(2), а элемент К(2) предварительно сдвигается вправо на одну позицию. Сортируемая последовательность далее принимает вид
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9) K(10) K(11)
J=4: 3 4 6 11 9 5 7 8 10 2 1
J=5: 3 4 6 9 11 5 7 8 10 2 1
J=6: 3 4 5 6 9 11 7 8 10 2 1
J=7: 3 4 5 6 7 9 11 8 10 2 1
J=8: 3 4 5 6 7 8 9 11 10 2 1
J=9: 3 4 5 6 7 8 9 10 11 2 1
J=10: 2 3 4 5 6 7 8 9 10 11 1
J=11: 1 2 3 4 5 6 7 8 9 10 11.
1. 2. 4. Метод Шелла (сортировка с убывающим шагом)
Здесь исходный набор данных на каждом просмотре разбивается на части. Части образуются из записей, отстоящих друг от друга на Н позиций. Производится сортировка записей внутри этих частей обычными методами (обмен, вставка и др. ). После каждого просмотра Н сокращается. При этом число частей уменьшается, а их длина увеличивается. Сортировка заканчивается просмотром с Н=1. В методе Шелла первоначально Н устанавливается равным INT(N/2), а затем сокращается вдвое. Структурограмма метода Шелла с сортировкой вставкой отдельных частей приведена на рис. 6.
|
|
|
Пример. Исходная последовательность
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)
12 5 4 3 1 9 8 6 7.
Первоначально Н принимается равным 4. Исходная последовательность разбивается на следующие четыре части:
K(1) K(5) K(9)│ K(2) K(6)│ K(3) K(7)│ K(4) K(8)
12 1 7 │ 5 9 │ 4 8 │ 3 6.
После упорядочения элементов внутри каждой последовательности набор данных будет иметь следующий вид:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)
1 5 4 3 7 9 8 6 12.
Затем шаг H сокращается вдвое и становится равным 2. Образуются следующие 2 последовательности элементов, отстоящих друг от друга на 2 элемента:
K(1) K(3) K(5) K(7) K(9) │ К(2) К(4) К(6) К(8)
1 4 7 8 12 │ 5 3 9 6.
После упорядочения элементов внутри этих последовательностей набор данных будет иметь следующий вид:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)
1 3 4 5 7 6 8 9 12.
Затем снова H сокращается вдвое и становится равным 1. При этом полученная последовательность сортируется обычной вставкой
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)
1 3 4 5 6 7 8 9 12.
1. 2. 5. Сортировка слиянием
Сортировка слиянием является процессом объединения двух или более упорядоченных наборов данных в один упорядоченный набор данных. В процессе слияния поочередно сравниваются ключи в парах данных так, что записи с меньшими ключами помещаются в результирующий набор данных. После того как один набор данных окажется исчерпанным, все оставшиеся элементы другого пересылаются в результирующий набор без изменения порядка следования. Структурограмма алгоритма сортировки слиянием в массив C(N+M) двух массивов A(N) и B(M) имеет вид, представленный на рис. 7.
|
|
|
Данный метод можно использовать для сортировки одного
файла следующим образом. Файл разделяется на N частей размером в один элемент, и объединяются соседние (необъединенные) пары элементов. В результате образуются примерно N/2 частей размером в два элемента. Данный процесс продолжается, пока не останется только одна последовательность размером N.
Ниже показано, как выполняется этот процесс на последовательности примера. Каждая отдельная часть на рисунке заключена в скобки.
Исходный файл: [25] [57] [48] [37] [12] [92] [86] [33]
Просмотр 1: [25 57] [37 48] [12 92] [33 86]
Просмотр 2: [25 37 48 57] [12 33 86 92]
Просмотр 3: [12 25 33 37 48 57 86 92].
|
|
|
