Методы сортировки

Лабораторная работа Методы сортировки Комбинаторные Алгоритмы.

Мулюкин Алексей

Санкт-Петербург, 2011

Методы сортировки

1. Метод быстрой сортировки с параметром M = 1 и M = 256

2. Метод поразрядной сортировки Архив файлов для сортировки: new_files2

Описание методов сортировки

1. Метод быстрой сортировки с параметром M

В заданном массиве A выбирается опорный элемент. Сравнивается каждый элемент массива с опорным элементом и на основании сравнения основной массив разбивается на 3 подмножества, в которых элементы массива A меньше, равны и больше опорного элемента. Для каждого из подмножеств, процесс сравнения повторяется, при условии, что кол-во элементов в полученном подмножестве больше M. Если же их меньше, то выполняется сортировка по методу Пузырька.

2. Метод поразрядной сортировки Каждый элемент заданного массива A помещается во вспомогательный массив B_i, где i — значение n-ого разряда элемента. Получившиеся массивы склеиваются, и процесс повторяется для следующего или предыдущего разряда (least significant digit (LSD) или most significant digit (MSD)) .

Текст программы

В программе используется специальный класс FileSorter, который распределяет сортируемые файлы по отдельным потокам. Замер времени производиться с помощью функции подсчета тактов процессора и частоты. Результат предоставляется в mks и экспортируется в таблицу.

Некоторые части класса диагностики (Замер времени, и экспорт в таблицу)

using System.Runtime.InteropServices;

abstract class FileSorter

{

const int maxFileOnThread = 32;

const int sortCount = 40;

[DllImport («Kernel32.dll»)]

static extern bool QueryPerformanceCounter (ref Int64 performanceCount);

[DllImport («Kernel32.dll»)]

static extern bool QueryPerformanceFrequency (ref Int64 frequency);

public string ExportToTable ()

{

StringBuilder sb = new StringBuilder ();

string format = «{0}t{1}t{2}t{3}n» ;

sb.Append (name+'n');

sb.AppendFormat (format, «File name», «Element count», «Rnd value, %», «time, mks»);

for (int i = 0; i < files. Length; i++)

{

FileInfo fi = new FileInfo (files[i]);

sb.AppendFormat (format, fi.Name, fileSize[i], rndValue[i], time[i]);

}

return sb. ToString ();

}

private void threadBegin ()

{

for (int i = 0; i < files. Length; i++)

{

using (StreamReader sr = new StreamReader (files[i]))

{

string[] list = sr. ReadToEnd ().Split («tn» .ToCharArray (), StringSplitOptions. RemoveEmptyEntries).ToArray ();

int[] iList = new int[list.Length];

for (int j = 0; j < list. Length; j++)

int.TryParse (list[j], out iList[i]);

fileSize[i] = iList. Length;

FileInfo fi = new FileInfo (files[i]);

byte.TryParse (fi.Name.Substring (6, 3), out rndValue[i]);

int[][] arr = new int[sortCount][];

for (int k = 0; k < sortCount; k++)

{

arr[k] = new int[iList.Length];

for (int j = 0; j < iList. Length; j++)

arr[k][j] = iList[j];

}

long _start = 0;

QueryPerformanceCounter (ref _start);

for (int k = 0; k < sortCount; k++)

beginSort (ref arr[k], 0, arr[k]. Length — 1);

long _finish = 0;

QueryPerformanceCounter (ref _finish);

long _freq = 0;

QueryPerformanceFrequency (ref _freq);

time[i] = (ulong)(((double)(_finish — _start) / (double)_freq)*1 000 000 / (double)sortCount);

if (EventFileSortEnd ≠ null)

EventFileSortEnd (this, files[i], time[i]);

}

}

if (EventSortEnd ≠ null)

EventSortEnd (this);

}

}

Код быстрой сортировки

class QuckSorter: FileSorter

{

private int M;

public QuckSorter (string name, string[] files, int m)

: base (name, files)

{

this.M = m;

}

public override FileSorter Copy (string name, string [] files)

{

return new QuckSorter (name, files, M);

}

private void simpleSort (ref int[] list, int start, int end)

{

for (int i = start; i <= end; i++)

for (int j = i; j <= end; j++)

if (list[i] > list[j])

{

int loc = list[i];

list[i] = list[j];

list[j] = loc;

}

}

public override void beginSort (ref int[] list, int start, int end)

{

int len = end — start + 1;

if (len <= 0)

{

return;

}

else if (len <= M)

{

simpleSort (ref list, start, end);

}

else if (len > M)

{

int x = list[(start + end) / 2];

int i = start;

int j = end;

do

{

while (list[i] < x) ++i;

while (list[j] > x) —j;

if (i <= j)

{

int loc = list[i];

list[i] = list[j];

list[j] = loc;

i++; j—;

}

} while (i <= j);

if (start < j)

beginSort (ref list, start, j);

if (i < end)

beginSort (ref list, i, end);

}

}

}

Код поразрядной сортировки

сортировка алгоритм файл строковый

class RadixSorter: FileSorter

{

public RadixSorter (string name, string[] files)

: base (name, files)

{

}

private int getDigit (int i, int digit)

{

return (i / (int)Math.Pow (10, digit — 1)) % 10;

}

public override void beginSort (ref int[] list, int start, int end)

{

int range = 10;

int m = 10;

List[] arr = new List[range];

for (int i = 0; i < range; i++)

arr[i] = new List ();

for (int i = 1; i < m; i++)

{

//Выбираем список

for (int j = 0; j < list. Length; j++)

{

int temp = getDigit (list[j], i);

arr[temp]. Insert (0, list[j]);

}

//Склеиваем списки

int l = 0;

for (int j = 0; j < range; j++)

{

for (int z = arr[j]. Count — 1; z >= 0; z—)

list[l++] = arr[j][z];

arr[j].Clear ();

}

}

}

public override FileSorter Copy (string name, string[] files)

{

return new RadixSorter (name, files);

}

}

Результаты тестирования сортировок:

Таблица 1. Метод быстрой сортировки M = 1

Таблица 2. Метод быстрой сортировки M = 256

Таблица 3. Метод поразрядной сортировки

Графики зависимости времени сортировки от кол-ва элементов в файле и от степени перемешенности элементов

График 1. Быстрая сортировка с параметром M = 1

График 2. Быстрая сортировка с параметром M = 256

График 3. Поразрядная сортировка

Последующие графики строятся по средним значениям заданного ключа.

Таблица 4. Зависимость времени сортировки от кол-ва элементов в данном массиве

График 4. Зависимость времени сортировки от кол-ва элементов в данном массиве

Таблица 5. Зависимость времени сортировки от степени перемешенности элементов массива

Таблица 6. Соотношение времени выполнения сортировок

График 5. Зависимость времени сортировки от степени перемешенности элементов массива

Вывод

В процессе выполнения работы, были выявлены особенности исследуемых алгоритмов сортировки данных.

1) Быстрая сортировка, M = 1:

Просто и адекватно запоминающийся алгоритм сортировки, один из самых распространенных. В данной работе он оправдал себя. По итоговым графикам видно, что время выполнения не сильно зависит от степени перемешенности элементов массива. На «Графике 1» можно видеть сильный разброс времени выполнения сортировки. Такие погрешности, скорей всего можно отнести к технической реализации алгоритма. И убрать эту погрешность, оптимизировав и упростив алгоритм сортировки.

2) Быстрая сортировка, M = 256:

Поскольку алгоритм используется тот же, что и при первом типе сортировки есть небольшой разброс, который на больших массивах сводится к минимуму. Рассматривая графики «График 1» и «График 4» можно заметить, что по сравнению при параметре M = 1 график выглядит естественнее. К тому же по итогам «Таблицы 5» видно, что скорость выполнения сортировки при параметре M = 256 немного быстрее аналога. Кроме того скорость выполнения стала менее зависимой от степени перемешенности.

3) Поразрядная сортировка:

Алгоритм достаточно запутанный, но после понимания реализуется не сложно и довольно таки быстро. Однако скорость его выполнения не радует. По данным «Таблицы 5» видно, что данный алгоритм проигрывает методу быстрой сортировки почти в 400 раз, а это достаточно крупное число. Но плюс данного метода в том, что его можно применить для сортировки строк в алфавитном порядке. По «Графику 3» можно заметить, что алгоритм слабо чувствителен к степени перемешенности элементов в массиве. Однако скорость сортировки очень резко падает при увеличении кол-ва элементов в массиве.

Подводя окончательные итоги, хочу сказать, что одним из самых лучших методов из трех данных проявил метод быстрой сортировки при параметре M = 256. Он прост в написании, быстр, по сравнению со своим аналогом при M = 1 и намного быстрее метода поразрядной сортировки. Метод поразрядной сортировки тоже хорош, но только не для сортировки чисел, а например, для сортировки строковых данных.