Лабораторна робота
Методи сортування
Комбінаторні Алгоритми.
Мулюкіна Олексій
Санкт-Петербург, 2011
Методи сортування
. Метод швидкого сортування з параметром M = 1 і M = 256
. Метод порозрядної сортування
Архів файлів для сортування: new_files2
Опис методів сортування
. Метод швидкого сортування з параметром M
У заданому масиві A вибирається опорний елемент. Порівнюється кожен елемент масиву з опорним елементом і на підставі порівняння основний масив розбивається на 3 підмножини, в яких елементи масиву A менше, рівні і більше опорного елемента. Для кожного з підмножин, процес порівняння повторюється, за умови, що кол-во елементів в отриманому підмножині більше M. Якщо ж їх менше, то виконується сортування за методом Бульбашки. br/>В
2. Метод порозрядної сортування
В
Кожен елемент заданого масиву A поміщається в допоміжний масив B i , де 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"...
