Сортировка с помощью дерева.

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 7Следующая ⇒

Построение дерева начинается с листьев, которые содержат все элементы массива. Из каждой соседней пары выбирается наименьший элемент, и эти элементы образуют следующий (ближе к корню уровень дерева). Из каждой соседней пары выбирается наименьший элемент и т.д., пока не будет построен корень, содержащий наименьший элемент массива.

Массив: 8, 23, 5, 65, 44, 33, 1, 6

Первый шаг:

Второй шаг:

Третий шаг:

Четвертый шаг:

Пятый шаг:

Шестой шаг:

Седьмой шаг:

Восьмой шаг:

Пирамидальная сортировка.

Массив: 44, 55, 12, 42, 94, 18, 6, 67

обменяли 55 и 12, забыли про 55

просеяли 12 сквозь 44, 42

обменяли местами 44 и 12, забыли про 44

просеяли 12 сквозь 42

обменяли местами 42 и 6, забыли про 42

получили 6, 12, 18.

Сортировка со слиянием.

Два массива: 5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 1

5, 8, 23, 65                    1, 6, 34, 47

Записываем меньшее значение: 5

5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 6

5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 8

5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 23

5, 8, 23 ,65                1, 6, 34, 47

Записываем меньшее значение: 34

5, 8, 23 ,65                1, 6, 34, 47

Записываем меньшее значение: 47

Осталось число 65.

Внешняя сортировка прямым слиянием.

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и записи a1, a3,..., a(n-1) пишутся в файл B, а записи a2, a4,..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4),..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее.

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: файл В 23, 5, 47, 1

     файл С 8, 65, 34, 6

Файл А: 8, 23, 5, 65, 34, 47, 1, 6

Шаг 2: файл В 8, 23, 34, 47

     файл С 5, 65, 1, 6

Файл А: 5, 8, 23, 65, 1, 34, 6, 47

Шаг 3: файл В 5, 8, 23, 65

     файл С 1, 34, 6, 47

Файл А: 1, 5, 8, 34, 6, 23, 47, 65

Шаг 4: файл В 1, 5, 8, 34

     файл С 6, 23, 47, 65

Файл А: 1, 5, 6, 8, 23, 34, 47, 65

Естественное слияние.

Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:

1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)

2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше

3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора

4. шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаются в еще более длинные наборы, и.т.д. до тех пор, пока не будет получена единая упорядоченная последовательность.

Массив: 24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40

Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:

(24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)

(24) + (08, 13, 17) = (08, 13, 17, 24)

(06, 19, 20) + (11) = (06, 11, 19, 20)

(07, 55) + (33) = (07, 33, 55)

(22) + (18) = (18, 22)

Новый набор чисел:

08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40

Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):

(08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)

(08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)

(07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55)

Новый набор:

06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40

Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:

(06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)

(06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55)

Новый набор и его две серии:

(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40)

Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:

02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров