Алгоритмы сортировки
Очень часто при обработке данных требуется их отсортировать, иначе говоря, упорядочить их определенным образом. Сортировка применяется в очень многих областях, будь то математические программы для расчетов или базы данных.
Существует множество различных методов сортировки данных, которые подробнейшим образом описаны в классической работе Д. Кнута "Искусство программирования для ЭВМ". Причем для разных типов данных иногда целесообразно применять разные методы сортировки. Но, тем не менее, практически каждый алгоритм сортировки можно разбить на три части:
сравнение, определяющее упорядоченность пары элементов;
перестановку, меняющую местами пару элементов;
собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.
Метод пузырька (обменная сортировка с выбором)
Идея этого метода отражена в названии. Самые легкие элементы массива “всплывают” наверх, самые “тяжелые” – тонут.
Алгоритмически это можно реализовать следующим образом: будем просматривать весь массив “снизу вверх” (от первого элемента к последнему) и менять стоящие рядом элементы в том случае, если “нижний” элемент меньше, чем “верхний”. Таким образом, мы вытолкнем наверх самый “легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортированными первых N-1 элементов (т.е. для тех, которые лежат “ниже” первого). В результате второй по величине “пузырек” встанет на свое место (второе с конца).
Очевидно, что такую процедуру необходимо проделать N-1 раз, так как в тот момент, когда (N-1)ый по счету элемент попадет на свое место, последний из сортируемых автоматически окажется на первом месте.
Пример: дана D – последовательность из 5 (N=5) чисел, которую и будем сортировать по убыванию.
D: 10 3 -1 4 15
d1 d2 d3 d4 d5
1) Задаем k=1 (должен "всплыть" первый "пузырек").
1.1. Задаем i=1; проверяем условие i N-k, т.е. 15-1? – да, значит, будем сравнивать di и di+1, т.е. d1 и d2: 10<3? – нет, поэтому d1 и d2 местами не меняем.
D: 10 3 -1 4 15
d1 d2 d3 d4 d5
1.2. Задаем i=2; проверяем условие 25-1? – да, значит, будем сравнивать d2 и d3: 3<-1? – нет, поэтому d2 и d3 местами не меняем.
D: 10 3 -1 4 15
d1 d2 d3 d4 d5
1.3. Задаем i=3; проверяем условие 35-1? – да, значит, будем сравнивать d3 и d4: -1<4? – да, поэтому d3 и d4 меняем местами.
D: 10 3 4 -1 15
d1 d2 d3 d4 d5
1.4. Задаем i=4; проверяем условие 45-1? – да, значит, будем сравнивать d4 и d5: -1<15? – да, поэтому d4 и d5 меняем местами.
D: 10 3 4 15 -1
d1 d2 d3 d4 d5
1.5. Задаем i=5; проверяем условие 55-1? – нет, значит, мы закончили проверять неотсортированную часть. Действительно, самое маленькое число (-1) встало на последнее место, т.е. первый "пузырек" "всплыл".
2) Задаем k=2 (должен "всплыть" второй "пузырек").
2.1. Задаем i=1; проверяем условие i N-k, т.е. 15-2? – да, значит, будем сравнивать di и di+1, т.е. d1 и d2: 10<3? – нет, поэтому d1 и d2 местами не меняем.
D: 10 3 4 15 -1
d1 d2 d3 d4 d5
2.2. Задаем i=2; проверяем условие 25-2? – да, значит, будем сравнивать d2 и d3: 3<4? – да, поэтому d2 и d3 меняем местами.
D: 10 4 3 15 -1
d1 d2 d3 d4 d5
2.3. Задаем i=3; проверяем условие 35-2? – да, значит, будем сравнивать d3 и d4: 3<15? – да, поэтому d3 и d4 меняем местами.
D: 10 4 15 3 -1
d1 d2 d3 d4 d5
2.4. Задаем i=4; проверяем условие 45-2? – нет, значит, мы закончили проверять неотсортированную часть. Действительно, второе по величине маленькое число (3) встало на предпоследнее место, т.е. второй "пузырек" "встал" на свое место.
Далее повторяем все действия при k=3, и т.д. до полного упорядочивания последовательности.
Блок-схема данного алгоритма приведена на рисунке.
Блок-схема сортировки последовательности по убыванию значений методом пузырька
Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Очевидно, что данный алгоритм можно несколько “модернизировать”, добавив во внутреннем цикле проверку “была ли хоть одна перестановка?”, а во внешнем проверять её результат (если ни одной перестановки не было – значит, последовательность уже упорядочена). Таким образом, можно избавиться от лишнего выполнения внешнего цикла, сократив тем самым общее количество действий, а следовательно, и время выполнения.
Сортировка выбором
Смысл данного алгоритма сводится к следующему:
Задаем номер места К в последовательности, на которое нужно будет поместить очередной упорядочиваемый элемент.
Находим в неупорядоченной части последовательности элемент с самым большим (или самым маленьким) значением, запоминая его номер.
Меняем его местами с тем, который находится на К-ом месте.
Все указанные операции повторяются до тех пор, пока не упорядочим всю последовательность.
Блок-схема алгоритма сортировки данным методом приведена на рисунке.
Блок-схема сортировки последовательности по убыванию значений методом выборки максимального элемента
Сортировка методом Шелла
Основная идея сортировки по Шеллу заключается в том, что сначала сравниваются удаленные друг от друга элементы, а не смежные, как в методе «пузырька». Это приводит к быстрому устранению большей части неупорядоченности и сокращает последующую работу. Интервал между элементами постепенно сокращается до единицы, когда сортировка фактически превращается в метод перестановки соседних элементов.
На блок-схеме, приведенной на рисунке, представлен алгоритм сортировки последовательности D, состоящей из N элементов.
Блок-схема сортировки последовательности по убыванию значений методом Шелла.
Здесь имеются три вложенных цикла. Самый внешний цикл управляет интервалом (обозначен sh) между сравниваемыми элементами, уменьшая его от N/2 в два раза при каждом проходе, пока он не станет равным нулю. Средний цикл сравнивает каждую пару элементов, разделенных на величину интервала. Самый внутренний цикл переставляет любую неупорядоченную пару.
Так как интервал sh в конце концов сводится к единице, все элементы в результате упорядочиваются правильно. /Описание взято из: Карниган Б., Ритчи Д. Язык программирования Си./
Другие алгоритмы сортировки. Сравнение алгоритмов
Конечно же, на самом деле алгоритмы сортировки не ограничиваются методами, изложенными выше. В статье С. Курковского “Алгоритмы сортировки” (журнал “Монитор”, №6-7, 1992г.) приведены также метод Хоора, называемый также быстрой сортировкой, и метод сортировки с помощью бинарного дерева. Оттуда же взята диаграмма, на которой сравнивается быстродействие этих алгоритмов (рисунок).
Очевидно, что для организации перебора неотсортированной части последовательности полезно применить цикл. Кроме того, еще один цикл (очевидно, внешний) будет "отвечать" за номер элемента, который "становится на свое место" в данный момент. Поэтому вспомним, как организуются операторы цикла в языке СИ.
Описание алгоритма решения задачи
Сначала описываются две глобальные переменные, определяющие размерность двумерного массива и глобальный массив с максимальной размерностью 20Х20
Для упрощения исходного кода и отладки, введены пользовательские функции, первая из них меняет две заданные строчки массива местами, с помощью цикла и трех математических операций:
a=a+b;
b=a-b;
a=a-b;
В результате чего переменные a и b обменяются значениями, вторая ищет минимальный элемент заданной строчки перебором, третья выводит массив на экран и в файл.
В основном блоке задаются четыре целые переменные, выполняющие роль счетчиков циклов.
Открывается файл, где в первой строчке указывается количество строк и столбцов массива, а в следующих n строках записаны по m элементов массива через пробел. Исходя из задания, предполагается, что файл существует, поэтому нет необходимости проверять наличие оного. Таким образом, сначала считывается размерность, а потом с помощью двух вложенных циклов значения переменных заносятся в массив.
С помощью описанного выше метода Шелла массив сортируется, используя функцию, возвращающую значение минимального элемента строки и функцию обмена двух строк.
Процедура вывода выводит полученный массив на экран и в файл.
Руководство программиста
Программный код приложения разрабатывался на языке СИ.
В программе использованы следующие пользовательские функции:
void swtch(строка массива с номером а, строка массива с номером b)
Меняет местами строку a со строкой b.
float min(строка массива с номером а)
Возвращает значение минимального элемента строки а.
void prn()
Выводит значение массива в файл output.txt.
Блок-схема алгоритма программы приведена в приложении А.
Листинг программы приведен в приложении В.
Пример входного и выходного файла в приложении С.
Руководство пользователя
В папке с приложением должен находиться файл input.txt, в первой строчке которого указано количество строк и столбцов массива, а в следующих n строках записаны по m элементов массива через пробел.
Работа с приложением начинается с запуска файла Lab1.exe. Программа выдаст уже отсортированный массив на экран и в файл output.txt
Пример содержания входного и выходного файла приведено в приложении С.
Вывод
В результате выполнения лабораторной работы были изучены некоторые алгоритмы сортировки данных, а так же приобретены навыки применения и реализации их на языке С при решении конкретных задач.
Приложение В
#include <stdio.h>
#include <conio.h>
int n,m;
float mat[20][20];
void swtch(int a,int b)
{
int i;
for(i=0;i<m;i++)
{
mat[a][i]=mat[a][i]+mat[b][i];
mat[b][i]=mat[a][i]-mat[b][i];
mat[a][i]=mat[a][i]-mat[b][i];
}
}
float min(int a)
{
int i1;
float m1;
m1=100000;
for(i1=0;i1<m;i1++)
if(mat[a][i1]<m1) m1=mat[a][i1];
return m1;
}
void prn()
{
int i,j;
FILE *x1;
x1 = fopen("output.txt","w");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%f ",mat[i][j]);
fprintf(x1,"%0.2f ",mat[i][j]);
}
printf("\n");
fprintf(x1,"\n");
}
fclose(x1);
}
void main()
{
int i,d,k,j;
FILE *x;
x = fopen("input.txt","r");
fscanf(x,"%d %d", &n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
fscanf(x,"%f",&mat[i][j]);
fclose(x);
for(d=n/2;d>=1;d/=2)
for(i=d;i<n;i++)
for(k=i-d;k>=0 && min(k)>=min(k+d);k-=d)
swtch(k+d,k);
prn();
getch();
}
Приложение С
Файл input.txt
15 15
0.35 854.88 890.44 282.40 554.77 126.36 482.13 758.76 372.-19 966.91 905.94 885.84 455.20 366.89 995.90
89.81 736.20 423.70 332.58 744.72 545.89 332.44 132.44 433.-12 595.07 202.37 760.63 185.32 300.82 77.75
720.81 799.20 660.10 641.80 692.79 149.62 312.54 802.63 460.00 142.16 72.89 771.98 229.47 136.70 82.01
773.29 986.83 812.84 358.93 655.92 455.90 410.22 888.39 509.85 587.66 94.85 834.54 783.44 932.69 952.22
862.55 218.21 132.90 106.73 251.68 319.47 373.44 790.82 500.24 669.71 962.23 403.65 140.41 567.87 557.75
734.01 928.82 348.47 57.41 189.01 37.81 983.22 804.33 -20.98 440.39 508.88 130.12 96.34 132.58 238.49
731.90 707.95 272.18 665.87 859.54 774.62 721.71 149.62 241.24 211.02 724.66 705.51 805.12 185.98 337.18
12.10 525.74 951.78 501.69 787.64 963.44 447.27 50.61 114.45 185.58 364.02 866.05 860.78 696.43 275.97
577.67 648.46 712.37 439.39 544.97 31.58 134.82 303.80 68.87 146.99 802.08 879.33 290.21 115.31 53.88
699.66 785.16 239.37 857.86 592.-12 232.45 89.14 213.65 15.91 347.41 855.49 700.87 731.60 98.83 574.19
231.54 428.40 783.87 79.94 578.45 658.13 579.24 914.69 153.67 294.95 169.16 737.78 788.23 408.54 510.15
525.26 229.96 431.39 -45.86 31.59 806.09 263.75 291.08 785.58- 95.99 832.55 478.13 80.40 500.90 206.90
125.09 733.14 12.05 118.69 831.63 308.77 777.19 514.91 933.97 450.79 99.15 583.82 933.14 200.22 626.70
532.07 467.31 878.29 681.02 539.05 44.84 -337.75 344.95 557.15 893.80 -64.50 628.77 979.00 128.60 761.94
71.59 437.07 136.23 208.08 46.26 297.34 937.67 668.39 560.11 236.46 93.22 -31.75 168.38 834.53 900.66
Файл output.txt
583.82 933.14 200.22 626.70 532.07 467.31 878.29 681.02 539.05 44.84 -337.75 344.95 557.15 893.80 -64.50 min=-337.75
788.23 408.54 510.15 525.26 229.96 431.39 -45.86 31.59 806.09 263.75 291.08 785.58 0.00 95.99 832.55 min=-45.86
567.87 557.75 734.01 928.82 348.47 57.41 189.01 37.81 983.22 804.33 -20.98 440.39 508.88 130.12 96.34 min=-20.98
0.35 854.88 890.44 282.40 554.77 126.36 482.13 758.76 372.00 -19.00 966.91 905.94 885.84 455.20 366.89 min=-19.00
115.31 53.88 699.66 785.16 239.37 857.86 592.00 -12.00 232.45 89.14 213.65 15.91 347.41 855.49 700.87 min=-12.00
995.90 89.81 736.20 423.70 332.58 744.72 545.89 332.44 132.44 433.00 -12.00 595.07 202.37 760.63 185.32 min=-12.00
478.13 80.40 500.90 206.90 125.09 733.14 12.05 118.69 831.63 308.77 777.19 514.91 933.97 450.79 99.15 min=12.05
185.98 337.18 12.10 525.74 951.78 501.69 787.64 963.44 447.27 50.61 114.45 185.58 364.02 866.05 860.78 min=12.10
696.43 275.97 577.67 648.46 712.37 439.39 544.97 31.58 134.82 303.80 68.87 146.99 802.08 879.33 290.21 min=31.58
628.77 979.00 128.60 761.94 71.59 437.07 136.23 208.08 46.26 297.34 937.67 668.39 560.11 236.46 93.22 min=46.26
300.82 77.75 720.81 799.20 660.10 641.80 692.79 149.62 312.54 802.63 460.00 142.16 72.89 771.98 229.47 min=72.89
731.60 98.83 574.19 231.54 428.40 783.87 79.94 578.45 658.13 579.24 914.69 153.67 294.95 169.16 737.78 min=79.94
136.70 82.01 773.29 986.83 812.84 358.93 655.92 455.90 410.22 888.39 509.85 587.66 94.85 834.54 783.44 min=82.01
932.69 952.22 862.55 218.21 132.90 106.73 251.68 319.47 373.44 790.82 500.24 669.71 962.23 403.65 140.41 min=106.73
132.58 238.49 731.90 707.95 272.18 665.87 859.54 774.62 721.71 149.62 241.24 211.02 724.66 705.51 805.12 min=132.58