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

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);

}

}

}

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

Таблица 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 и намного быстрее метода поразрядной сортировки. Метод поразрядной сортировки тоже хорош, но только не для сортировки чисел, а например, для сортировки строковых данных.

Размещено на Allbest.ru