6.5 Внешняя и внутреняя сортировка

6.5.1 Понятие сортировки

Алгоритм сортировки— этоалгоритмдля упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

"Внешней" сортировкой принято называть сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в основную память и применить один из рассмотренных в предыдущем разделе методов внутренней сортировки.

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

6.5.2 Сортировка с простым включением

Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

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

Шаг 1: i₁= 8, 23, 5, 65, 47, 34, 1, 6

Шаг 2: i₂₌ 8, 5, 23, 65, 47, 34, 1, 6

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

Шаг 3: i₃= 5, 8, 23, 65, 47, 34, 1, 6

Шаг 4: i₄= 5, 8, 23, 47, 65, 34, 1, 6

Шаг 5: i₅= 5, 8, 23, 47, 34, 65, 1, 6

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

Шаг 6: i₆= 5, 8, 23, 34, 47, 1, 65, 6

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

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

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

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

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

Шаг 7: i₇= 1, 5, 8, 23, 34, 47, 6, 65

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

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

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

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

6.5.3 Сортировка методом Шелла

Метод состоит в том, что упорядочиваемая таблица разделяется на группы элементов, каждая из которых упорядочивается методом вставки. В процессе упорядочения размеры таких групп    увеличиваются до тех пор, пока все элементы таблицы не войдут в упорядоченную группу. Выбор очередной упорядочиваемой группы и ее расположение внутри таблицы производятся так, чтобы можно было использовать предшествующую упорядоченность. Группой таблицы называют последовательность элементов, номера которых образуют арифметическую прогрессию с разностью d(dназывают шагом группы). В начале процесса упорядочения выбирается первый шаг группыd, который зависит от размера таблицы.

    d=[n/2]

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

Шаг 1: d=5(сортируются элементы, расстояние между которыми пять)

23, 8, 5, 65, 47,34, 1, 6, 13, 52 –массив не меняется

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

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

23, 1, 5, 65, 47, 34, 8,6, 13, 52– массив не меняется

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

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

23, 1, 5, 13, 47, 34, 8, 6, 65,52 – массив не меняется

Шаг 2: d=3(сортируются элементы, расстояние между которыми три)

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

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

13, 1, 5, 23,47, 34, 8, 6, 65, 52– массив не меняется

13, 1, 5, 23, 47,34, 8, 6, 65, 52– массив не меняется

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

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

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

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

13, 1, 5, 8, 6, 34, 23, 47,65, 52– массив не меняется

13, 1, 5, 8, 6, 34, 23, 47, 65,52– массив не меняется

Шаг 3: d=2(сортируются элементы, расстояние между которыми два)

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

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

5, 1, 13,8, 6, 34, 23, 47, 65, 52– массив не меняется

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

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

5, 1, 6, 8, 13,34, 23, 47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34,23, 47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23,47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23, 47,65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23, 47, 65,52– массив не меняется

Шаг 4: d=1(сортируются элементы, расстояние между которыми один)

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

1, 5,6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6,8, 13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6, 8,13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13,34, 23, 47, 65, 52– массив не меняется

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

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

1, 5, 6, 8, 13, 23, 34,47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 23, 34, 47,65, 52– массив не меняется

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

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