Автоматизация бухгалтерского учёта материальных ценностей в программе "1С: Предприятие" на примере организации ЗАО "Электротяга"

 

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

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

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

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

Санкт-Петербург, 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]);

}

//Склеиваем спискиl = 0;(int j = 0; j < range; 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Степень перемешенностиКол-во элементов в файле0255075100Общий итог6486555612814146416142425615425282956516051262656464162137510241401751341391391452048303789335313603469409613226541728188812281364819226354622157938531134276516384334230724101544750734207327681294913768558255155420864765536112941040112099248412057115841Общий итог292930542338382833073091

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

Среднее время сортировки, mksСтепень перемешенностиКол-во элементов в файле0255075100Общий итог64456565128502131414131112562529293031295128266844687122610241183753341401522242048306320300516131855240961618138457278582110368192295834282423204914502461163843133371342583323497338803276881537437687156995528673865536103881238711344146591878013512Общий итог248126512454248130132616

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

Среднее время сортировки, mksСтепень перемешенностиКол-во элементов в файле0255075100Общий итог645791991400138138491128358384308387316351256275910298131135229116055124732468446682272446241631024732469718265717882217592204822315170831991716407134401783240964394844352765705411043911525788192160098162747191348179007206887180017163847574937275857309826882887637767336253276826176152378564238514723866462426168243882865536989026693649699390190996911996808879659086Общий итог122795311553241164510120951711954991190561

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

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

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

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

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

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

Кол-во элементовБыстрая сортировка, M = 1Быстрая сортировка, M = 256Поразрядная сортировка646549112824111351256160291605512375226416310241452247592204846955217832409613641036525788192276524611800171638442073880733625327688647673824388286553615841135129659086

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

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

Степень перемешенности0255075100Быстрая сортировка, M = 129293054233838283307Быстрая сортировка, M = 25624812651245424813013Поразрядная сортировка12279531155324116451012095171195499

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

ВремяБыстрая, M = 1Быстрая, M = 256ПоразряднаяБыстрая, M = 1309111,1817741590,002596429Быстрая, M = 25626160,84618536710,00219706Поразрядная сортировка1190561385,1444234455,15372711

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

Вывод

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

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

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

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

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

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

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

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

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

Больше работ по теме: