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

Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 23.07.2012
Размер файла 1,2 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://allbest.ru/

Размещено на http://allbest.ru/

Лабораторная работа

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

Комбинаторные Алгоритмы.

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

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

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

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

2. Метод поразрядной сортировки

Архив файлов для сортировки: new_files2

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

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

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

2. Метод поразрядной сортировки

Каждый элемент заданного массива A помещается во вспомогательный массив Bi , где 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(" \t\n".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)*1000000 / (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<int>[] arr = new List<int>[range];

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

arr[i] = new List<int>();

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

Среднее время сортировки, 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

3853

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

375

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

128

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

Общий итог

1227953

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

2929

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

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


Подобные документы

  • Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.

    реферат [189,8 K], добавлен 06.12.2014

  • Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.

    курсовая работа [203,8 K], добавлен 03.12.2010

  • Понятие и основной принцип действия алгоритмов сортировки информации. Сравнительное исследование и анализ эффективности методов сортировки Шелла и Флойда в виде графиков зависимостей количества сравнений и числа перестановок элементов от объёма данных.

    контрольная работа [573,6 K], добавлен 09.11.2010

  • Алгоритмы сортировки методами простых вставок и пузырька. Зависимость среднего времени сортировки от числа сортируемых элементов. Функции, осуществляющие сортировку любого количества элементов методом простых вставок, на основе сортировки таблицы адресов.

    курсовая работа [557,1 K], добавлен 26.05.2010

  • Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.

    курсовая работа [291,5 K], добавлен 22.03.2012

  • Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.

    курсовая работа [161,7 K], добавлен 17.12.2015

  • Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора.

    курсовая работа [637,6 K], добавлен 29.11.2014

  • Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.

    курсовая работа [1,7 M], добавлен 16.04.2012

  • Определение понятия, видов и задач сортировки. Рассмотрение основ построения простых и улучшенных алгоритмов сортировки, анализ числа операций. Линейная и пирамидальная организация данных. Основные правила нижней оценки числа операций в алгоритмах.

    презентация [274,5 K], добавлен 19.10.2014

  • Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи.

    реферат [20,7 K], добавлен 20.05.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.