Методы сортировки
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Лабораторная работа
Методы сортировки
Комбинаторные Алгоритмы.
Мулюкин Алексей
Санкт-Петербург, 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 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) --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 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. Поразрядная сортировка
Последующие графики строятся по средним значени?/p>