Разработка программы сортировки данных на языке Turbo Pascal
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов. Например, если сортировку выбором применить для массива "bdac", то будут получены следующие проходы:
исходное положение: b d a c;
первый проход: a d b c;
второй проход: a b b c;
третий проход: a b c d.
К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3 (n-1), а в худшем случае равно n2/4+3 (n-1). В лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только n-1элементов, а каждая операция обмена требует три операции пересылки.
{сортировка выбором}Selekt (var item: DataArray; count: integer);, j, k: integer;: DataItem;i: = i to count-1 do: = i;: = item [i];
for j: = i+1 to count do {найти элемент с наименьшим значением}
if item [j] <x then: = j;: = item [j];;[k]: = item [i]; {обмен}
item [i]: = x;;; {конец сортировки выбором}
В среднем число операций обмена равно n (ln+y), где "y" является константой Эйлера, приблизительно равной 0,577216. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.
2.6 Сортировка вставкой
Сортировка вставкой является последней из класса простых алгоритмов сортировки. При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам.
Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сортировка вставкой будет проходить следующим образом:
исходное положение: d c a b;
первый проход: c d a b;
второй проход: a c d b;
третий проход: a b c d.
Ниже приводится алгоритм сортировки вставкой:
{ сортировка вставкой }Inser (var item: DataArray; count: integer);, l: integer;: DataItem;i: = 2 to count do: = item [i];: = i-1;(x0) do[j+1]: = item [j];: = j-1;;[j+1]: = x;
end;; { конец сортировки вставкой }
В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1.
Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n2 +n) - 1, давая в среднем значение 1/4 (n2+n-2).
Число операций обмена будет следующим:
для лучшего случая: 2 (n-1);
в среднем: 1/4 (n2+9n-10);
для худшего случая: 1/2 (n2+3n-4).
Таким образом, число операций обмена для худшего случая будет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая будет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т.е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.
Несмотря на то, что число сравнений может быть довольно небольшим для определенных наборов данных, постоянные сдвиги массива требуют выполнения большого числа операций пересылок.
Однако, сортировка вставкой имеет естественное поведение, требуя наименьшее число операций обмена для почти упорядоченного списка и наибольшее число операций обмена, когда массив упорядочен в обратном направлении.
2.7 Сортировка Шелла
Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов.
Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике. Каждый программист слышал или рассказывал "страшные" истории о "сортировке, которая выполнялась три дня". К сожалению, эти истории часто не являлись выдумкой.
Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Рассмотрим две очень хорошие сортировки. Первая носит название сортировки Шелла, а вторая называется быстрой сортировкой, алгоритм которой признан наилучшим. Эти сортировки выполняются очень быстро.
Сортировка Шелла получила свое название по имени ее создателя Д.Л. Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга.
Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. Ниже показана схема выполнения сортировки Шелла для массива "f d a c b e". Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы:
проход 1 f d a c b e
проход 2 c b a f d e
проход 3 a b c e d f
по?/p>