Методы сортировки
Лабораторная
работа
Методы
сортировки
Комбинаторные
Алгоритмы.
Мулюкин Алексей
Санкт-Петербург,
2011
Методы сортировки
. Метод быстрой сортировки с параметром M = 1 и M =
256
. Метод поразрядной сортировки
Архив файлов для сортировки: new_files2
Описание методов сортировки
. Метод быстрой сортировки с параметром M
В заданном массиве A
выбирается опорный элемент. Сравнивается каждый элемент массива с опорным
элементом и на основании сравнения основной массив разбивается на 3 подмножества,
в которых элементы массива A
меньше, равны и больше опорного элемента. Для каждого из подмножеств, процесс
сравнения повторяется, при условии, что кол-во элементов в полученном
подмножестве больше M. Если же их
меньше, то выполняется сортировка по методу Пузырька.
2. Метод поразрядной сортировки
Каждый элемент заданного массива A помещается во вспомогательный массив Bi , где i - значение n-ого
разряда элемента. Получившиеся массивы склеиваются, и процесс повторяется для
следующего или предыдущего разряда (least significant digit (LSD) или most
significant digit (MSD)) .
Текст программы
В программе используется специальный класс FileSorter, который распределяет сортируемые
файлы по отдельным потокам. Замер времени производиться с помощью функции
подсчета тактов процессора и частоты. Результат предоставляется в mks и экспортируется в таблицу.
Некоторые части класса диагностики (Замер времени, и экспорт в
таблицу)
using System.Runtime.InteropServices;class FileSorter
{int maxFileOnThread = 32;int sortCount = 40;
[DllImport("Kernel32.dll")]extern bool
QueryPerformanceCounter(ref Int64 performanceCount);
[DllImport("Kernel32.dll")]extern bool
QueryPerformanceFrequency(ref Int64 frequency);string ExportToTable()
{sb = new StringBuilder();format =
"{0}\t{1}\t{2}\t{3}\n";.Append(name+'\n');.AppendFormat(format,
"File name", "Element count", "Rnd value, %",
"time, mks");(int i = 0; i < files.Length; i++)
{fi = new FileInfo(files[i]);.AppendFormat(format, fi.Name,
fileSize[i], rndValue[i], time[i]);
}sb.ToString();
}void threadBegin()
{(int i = 0; i < files.Length; i++)
{(StreamReader sr = new StreamReader(files[i]))
{[] list = sr.ReadToEnd().Split("
\t\n".ToCharArray(), StringSplitOptions.RemoveEmptyEntries).ToArray();[]
iList = new int[list.Length];(int j = 0; j < list.Length;
j++).TryParse(list[j], out iList[i]);[i] = iList.Length;fi = new
FileInfo(files[i]);.TryParse(fi.Name.Substring(6, 3), out rndValue[i]);[][] arr
= new int[sortCount][];(int k = 0; k < sortCount; k++)
{[k] = new int[iList.Length];(int j = 0; j < iList.Length;
j++)[k][j] = iList[j];
}_start = 0;(ref _start);(int k = 0; k < sortCount;
k++)(ref arr[k], 0, arr[k].Length - 1);_finish = 0;(ref _finish);_freq = 0;(ref
_freq);[i] = (ulong)(((double)(_finish - _start) / (double)_freq)*1000000 /
(double)sortCount);(EventFileSortEnd != null)(this, files[i], time[i]);
}
}(EventSortEnd != null)(this);
}
}
Код быстрой сортировки
class QuckSorter : FileSorter
{int M;QuckSorter(string name, string[] files, int m)
: base(name, files)
{.M = m;
}override FileSorter Copy(string name, string [] files)
{new QuckSorter(name, files, M);
}void simpleSort(ref int[] list, int start, int end)
{(int i = start; i <= end; i++)(int j = i; j <= end;
j++)(list[i] > list[j])
{loc = list[i];[i] = list[j];[j] = loc;
}
}override void beginSort(ref int[] list, int start, int end)
{len = end - start + 1;(len <= 0)
{;
}if (len <= M)
{(ref list, start, end);
}if (len > M)
{x = list[(start + end) / 2];i = start;j = end;
{(list[i] < x) ++i;(list[j] > x) --j;(i <= j)
{loc = list[i];[i] = list[j];[j] = loc;++; j--;
}
} while (i <= j);(start < j)(ref list, start, j);(i
< end)(ref list, i, end);
}
}
}
Код поразрядной сортировки
сортировка
алгоритм файл строковый
class RadixSorter : FileSorter
{RadixSorter(string name, string[] files)
: base(name, files)
{
}int getDigit(int i, int digit)
{(i / (int)Math.Pow(10, digit - 1)) % 10;
}
override void beginSort(ref int[] list, int start, int end)
{range = 10;m = 10;<int>[] arr = new
List<int>[range];(int i = 0; i < range; i++)[i] = new
List<int>();(int i = 1; i < m; i++)
{
//Выбираем список(int j = 0; j < list.Length; j++)
{temp = getDigit(list[j], i);[temp].Insert(0, list[j]);
}
{(int z = arr[j].Count - 1; z >= 0; z--)[l++] =
arr[j][z];[j].Clear();
}
}
}override FileSorter Copy(string name, string[] files)
{new RadixSorter(name, files);
}
}
Результаты тестирования сортировок:
Таблица 1. Метод быстрой сортировки M = 1
|
Среднее время сортировки, mks
|
Степень перемешенности
|
|
Кол-во элементов в файле
|
0
|
25
|
50
|
75
|
100
|
Общий итог
|
|
64
|
8
|
6
|
5
|
5
|
5
|
6
|
|
128
|
14
|
14
|
64
|
16
|
14
|
24
|
|
256
|
154
|
25
|
28
|
29
|
565
|
160
|
|
512
|
62
|
65
|
64
|
64
|
1621
|
375
|
|
1024
|
140
|
175
|
134
|
139
|
139
|
145
|
|
2048
|
303
|
789
|
335
|
313
|
603
|
469
|
|
4096
|
1322
|
654
|
1728
|
1888
|
1228
|
1364
|
|
8192
|
2635
|
4622
|
1579
|
1134
|
2765
|
|
16384
|
3342
|
3072
|
4101
|
5447
|
5073
|
4207
|
|
32768
|
12949
|
13768
|
5582
|
5515
|
5420
|
8647
|
|
65536
|
11294
|
10401
|
12099
|
24841
|
20571
|
15841
|
|
Общий итог
|
2929
|
3054
|
2338
|
3828
|
3307
|
3091
|
Таблица 2. Метод быстрой сортировки M = 256
|
Среднее время сортировки, mks
|
Степень перемешенности
|
|
Кол-во элементов в файле
|
0
|
25
|
50
|
75
|
100
|
Общий итог
|
|
64
|
4
|
5
|
6
|
5
|
6
|
5
|
|
128
|
502
|
13
|
14
|
14
|
13
|
111
|
|
256
|
25
|
29
|
29
|
30
|
31
|
29
|
|
512
|
82
|
66
|
844
|
68
|
71
|
226
|
|
1024
|
118
|
334
|
140
|
152
|
224
|
|
2048
|
306
|
320
|
300
|
516
|
1318
|
552
|
|
4096
|
1618
|
1384
|
572
|
785
|
821
|
1036
|
|
8192
|
2958
|
3428
|
2423
|
2049
|
1450
|
2461
|
|
16384
|
3133
|
3713
|
4258
|
3323
|
4973
|
3880
|
|
32768
|
8153
|
7437
|
6871
|
5699
|
5528
|
6738
|
|
65536
|
10388
|
12387
|
11344
|
14659
|
18780
|
13512
|
|
Общий итог
|
2481
|
2651
|
2454
|
2481
|
3013
|
2616
|
Таблица 3. Метод поразрядной сортировки
|
Среднее время сортировки, mks
|
Степень перемешенности
|
|
Кол-во элементов в файле
|
0
|
25
|
50
|
75
|
100
|
Общий итог
|
|
64
|
579
|
199
|
1400
|
138
|
138
|
491
|
358
|
384
|
308
|
387
|
316
|
351
|
|
256
|
2759
|
1029
|
813
|
1135
|
2291
|
1605
|
|
512
|
4732
|
4684
|
4668
|
2272
|
4462
|
4163
|
|
1024
|
7324
|
6971
|
8265
|
7178
|
8221
|
7592
|
|
2048
|
22315
|
17083
|
19917
|
16407
|
13440
|
17832
|
|
4096
|
43948
|
44352
|
76570
|
54110
|
43911
|
52578
|
|
8192
|
160098
|
162747
|
191348
|
179007
|
206887
|
180017
|
|
16384
|
757493
|
727585
|
730982
|
688288
|
763776
|
733625
|
|
32768
|
2617615
|
2378564
|
2385147
|
2386646
|
2426168
|
2438828
|
|
65536
|
9890266
|
9364969
|
9390190
|
9969119
|
9680887
|
9659086
|
|
Общий итог
|
1155324
|
1164510
|
1209517
|
1195499
|
1190561
|
Графики зависимости времени сортировки от кол-ва элементов в
файле и от степени перемешенности элементов
График 1. Быстрая сортировка с параметром M = 1
График 2. Быстрая сортировка с параметром M = 256
График 3. Поразрядная сортировка
Последующие графики строятся по средним значениям заданного ключа.
Таблица 4. Зависимость времени сортировки от кол-ва элементов в данном
массиве
|
Кол-во элементов
|
Быстрая сортировка, M = 1
|
Быстрая сортировка, M = 256
|
Поразрядная сортировка
|
|
64
|
6
|
5
|
491
|
|
128
|
24
|
111
|
351
|
|
256
|
160
|
29
|
1605
|
|
512
|
375
|
226
|
4163
|
|
1024
|
145
|
224
|
7592
|
|
2048
|
469
|
552
|
17832
|
|
4096
|
1364
|
1036
|
52578
|
|
8192
|
2765
|
2461
|
180017
|
|
16384
|
4207
|
3880
|
733625
|
|
32768
|
8647
|
6738
|
2438828
|
|
65536
|
15841
|
13512
|
9659086
|
График 4. Зависимость времени сортировки от кол-ва элементов в данном массиве
Таблица 5. Зависимость времени сортировки от степени перемешенности
элементов массива
|
Степень перемешенности
|
0
|
25
|
50
|
75
|
100
|
|
Быстрая сортировка, M = 1
|
3054
|
2338
|
3828
|
3307
|
|
Быстрая сортировка, M = 256
|
2481
|
2651
|
2454
|
2481
|
3013
|
|
Поразрядная сортировка
|
1227953
|
1155324
|
1164510
|
1209517
|
1195499
|
Таблица 6. Соотношение времени выполнения сортировок
|
Время
|
Быстрая, M = 1
|
Быстрая, M = 256
|
Поразрядная
|
|
Быстрая, M = 1
|
3091
|
1
|
1,181774159
|
0,002596429
|
|
Быстрая, M = 256
|
2616
|
0,846185367
|
1
|
0,00219706
|
|
Поразрядная сортировка
|
1190561
|
385,1444234
|
455,1537271
|
1
|
График 5. Зависимость времени сортировки от степени перемешенности элементов
массива
Вывод
В процессе выполнения работы, были выявлены особенности исследуемых
алгоритмов сортировки данных.
1) Быстрая сортировка, M = 1:
Просто и адекватно запоминающийся алгоритм сортировки, один из самых
распространенных. В данной работе он оправдал себя. По итоговым графикам видно,
что время выполнения не сильно зависит от степени перемешенности элементов
массива. На «Графике 1» можно видеть сильный разброс времени выполнения
сортировки. Такие погрешности, скорей всего можно отнести к технической
реализации алгоритма. И убрать эту погрешность, оптимизировав и упростив
алгоритм сортировки.
2) Быстрая сортировка, M = 256:
Поскольку алгоритм используется тот же, что и при первом типе сортировки
есть небольшой разброс, который на больших массивах сводится к минимуму.
Рассматривая графики «График 1» и «График 4» можно заметить, что по сравнению
при параметре M = 1 график выглядит естественнее. К
тому же по итогам «Таблицы 5» видно, что скорость выполнения сортировки при
параметре M = 256 немного быстрее аналога. Кроме
того скорость выполнения стала менее зависимой от степени перемешенности.
3) Поразрядная сортировка:
Алгоритм достаточно запутанный, но после понимания реализуется не сложно
и довольно таки быстро. Однако скорость его выполнения не радует. По данным
«Таблицы 5» видно, что данный алгоритм проигрывает методу быстрой сортировки
почти в 400 раз, а это достаточно крупное число. Но плюс данного метода в том,
что его можно применить для сортировки строк в алфавитном порядке. По «Графику
3» можно заметить, что алгоритм слабо чувствителен к степени перемешенности
элементов в массиве. Однако скорость сортировки очень резко падает при
увеличении кол-ва элементов в массиве.
Подводя окончательные итоги, хочу сказать, что одним из самых лучших
методов из трех данных проявил метод быстрой сортировки при параметре M = 256. Он прост в написании, быстр,
по сравнению со своим аналогом при M = 1 и намного быстрее метода поразрядной сортировки. Метод поразрядной
сортировки тоже хорош, но только не для сортировки чисел, а например, для
сортировки строковых данных.