Введение.
Сортировка - это расположение элементов множества данных
в определенной последовательности: в порядке возрастания
или убывания ключей - признаков сортировки.
Сортировки применяются при:
1) Обеспечении более эффективной обработки в больших объемах данных (например для ускорения поиска данных);
2) Представления массивов данных в форме удобной для восприятия (например для упорядочевания списка имен);
Критерии оценки различных видов сортировок:
1) количество сравнений и пересылок данных;
2) время сортировки заданного объема данных;
3) ресурсы ЭВМ требуемые для сортировки;
4) сложность алгоритма сортировки;
Методы сортировок (внутренних) можно разделить на:
1) сортировки выбором;
2) сортировки включением;
3) сортировки обменом;
4) сортировки распределением;
5) сортировки подсчетом;
6) сортировки слиянием;
В данном разделе можно найти множество алгоритмов различных
видов внутренних сортировок с пояснениями и пример программы на
Delphi с использованием 4-х видов сортировок и возможностью их
сравнения при заданных условиях.
Сортировка выборкой.
Суть данного метода состоит в том, что из неупорядоченного входного
массива (каждый раз в цикле) выбирается максимальный(минимальный)
элемент массива и помещается в требуемое место выходного массива.
Если массив упорядочивается по возрастанию, то его заполнение идет с
конца, а если по убыванию, то с начала массива.
Метод простого выбора:
Процесс сортировки состоит в следующем:
1) Перебираются по i номера элементов сортируемого массива от Kol до 2;
2) Для каждого i номера элнментов с номерами от 1 до i выбирается максимальный
элемент m;
3) Элементы с номерами i и m меняются местами.
for i:= Kol downto 2 do
begin m:= 1;
for j:= 2 to i do
begin
if a[j] > a[m] then m:= j;
buf:= a[m]; a[m]:= a[i]; a[i]:= buf;
end;
end;
Особенности метода:
1) Кол-во сравнений метода всегда пропорционально N^2, даже если множество
упорядочено;
2) Дополнительная ОЗУ для размещения выходного массива не требуется;
Сортировка включением.
Сортировка включением состоит в том, что из входного массива элементы
берутся подряд, в выходной массив они размещаются так, чтобы не
нарушить его упорядоченности. Каждый элемент, включаемый в выходной
массив, постепенно проходит на свое место.
Метод пузырькового включения:
Процесс сортировки состоит в следующем:
1) В начале принимаем в качестве упорядоченного один первый элемент массива;
2) Перебираем остальные элементы массива по i от 2 до n;
3) Значение элемента i помещается в переменной b, а номер его места - в
переменной m;
4) Для поиска места для упорядочиваемого массива перебираем по j номера
упорядоченных элементов от (i-1) до 1;
5) производится замена положения упорядочеваемого элемента и элемента
находящегося на найденной для него позиции места.
for i:= 2 to n do
begin b:= a[i]; m:= i;
for j:= i - 1 downto 1 do
begin
if a[j] <= b then break;
a[m]:= a[j]; m:= j;
end; a[m]:= b;
end;
Особенности метода:
1) Сортировка множества K = N - 1; в этом основное достоинство метода;
2) В худшем случае, если массив упорядочен в обратном порядке,
кол-во сравнений: K = N^2/2;
Cреднее кол-во сравнений: K = N^2/4.
Сортировка методом Шелла.
Процесс сортировки состоит в следующем:
1) N элементов исходного массива разбивается на k групп таким
образом, чтобы в каждую группу входило не более 2-х элементов;
элементы одной группы располагаются на расстоянии d друг от друга;
d - шаг группы, должен быть степенью 2-х;
2) Производится сортировка в группах, в данном случае используется
метод пузырькового включения, рассмотренный выше;
3) k - количество групп и d - шаг группы уменьшаются вдвое,
выполняется П.2, и так до тех пор, пока шаг станет равным 1;
4) снова выполняется П.2, после чего сортировка завершена.
Особенности метода:
1) При больших значениях N время сортировки данным методом
значительно меньше, чем в 2-х прошлых методах.
Среднее кол-во сравнений:
KS <= (0.5 * N^3/2).
Обменные сортировки.
Этот метод называют также методом перестановки соседних элементов.
В данном методе сортируемый массив остается в процессе сортировки на
одном и том же месте. Минимальные элементы как бы всплывают в начало
массива.
Быстрая сортировка:
Процесс сортировки состоит в следующем:
1) Сначала множество разбивается на 3 подмножества таким образом, чтобы
A1+(i-1) <= Ai <= A(i+1)+N;
2) Подмножества длиною меньше M сортируются более простым методом;
3) Из стека извлекаются для сортировки границы несортированых подмножеств.
4) Сортировка завершается, когда стек будет пуст.
Особенности метода:
1) При больших значениях N время сортировки данным методом значительно
меньше, чем в 2-х первых методах, но приблизительно равно времени
сортировки методом Шелла.
Кол-во сравнений колеблется от
N^log2N
до
N^2.
Сортировка методом подсчета.
Данная сортировка не рассматривается в программе, написанной к данной
главе, но при желании вы можете сами дописать ее в программу. При
сортировке подсчетом определяются номера мест элементов массива,
расстановка по которым даст сортированный массив. Метод основан на
том, что j-ключ упорядоченной последовательнсти больше (j-1)-ключа
массива.
Процесс сортирови состоит в следующем:
1) Определяются в массиве b номера мест элементов массива a, расстановка
по которым в массиве c даст сортированный массив;
2) Перебираются номера элементов массива a по i = N / 2, с сравнением
значения элементов a[i] и a[j], где j = (i-1) / 1;
3) После формирования массива b, производится расстановка элементов массива a в массиве c.
for i:= 1 to n do b[i]:= 1;
for i:= n downto 2 do
for j:= i-1 downto 1 do
if a[i] < a[j] then inc(b[j], 1)
else inc(b[i], 1);
for i:= 1 to n do c[b[i]]:= a[i];
Программа.
Данная программа была написана на Delphi для наглядной демонстрации 4-х
методов сортировки, описанных в данной главе (простой выбор,
пузырьковое включение, быстрая сортировка и метод Шелла).
В данной программе необходимо ввести массив чисел, либо ввести кол-во
элементов массива в соответствующее поле и нажать на кнопку с названием
соответствующей сортировки, после чего все результаты можно увидеть в
текстовом поле. В программе есть счетчик времени, добавленный для
возможности сравнения результатов от всех сортировок и возможность
просмотра всех операций выполняемых сортировками, если вы поставили
флаг в поле "выводить все действия". Кроме того есть возможность
остановки процесса сортировки.
На примере данной программы можно убедиться в выгодности методов
быстрой сортировки и сортировки методом Шелла и в малой продуктивности
выборочной и пузырьковой сортировок. Особенно разница видна на больших
массивах.
Рассмотрим случай с массивом из 1000 произвольных элементов и
результаты всех 4-х сортировок:
1) 2 секунды
2) 5 секунд (?)
3) 0 секунд (!)
4) 0 секунд (!)
В данном случае наилучшие результаты показывают 2-е последние
сортировки, как и следовало ожидать, но есть разрыв между 2-мя 1-ми
методами и он говорит о большей выгоде 1-го метода.
Рассмотрим 2-й случай с 3000 элементов:
1) 21 секунда
2) 35 секунд (?)
3) < 1 секунды (!!)
4) < 1 секунды (!!)
В данном случае можно наблюдать выгодность 2-х последних методов,
которые сортируют данный (не малый!) массив за 0 секунд (!!), а у 2-х
первых методов на это уходит гораздо больше времени! Снова можно
наблюдать отсталость 3-го метода.
Рассмотрим 3-й случай с 9999 элементами:
1) 191 секунда
2) 310 секунд
3) 0 секунд (!!!)
4) 0 секунд (!!!)
Комментарии излишни…
Вы можете провести свои опыты и сделать свои выводы, но стоит помнить,
что для обработки больших массивов не стоит использовать медленные
сортировки, особенно важна скорость сортировки в мощных математических
программах, базах данных и олимпиадах по программированию, где можно
встретиться с понятием лимита времени.
До|За:
1) Найдите в литературе или в net'е описание других методов сортировок,
попробуйте дописать их в программу.
Дополнительная информация:
1) С "Жизнью" связано множество ресурсов интернета и найти материал
по данному вопросу не проблема.
Приложение:
