Реализация комбинаторных алгоритмов сортировки с вычислительным экспериментом на примере методов распределения

Введение Сортировка элементов некоторого множества (ключей) – очень часто встречающаяся на практике комбинаторная задача. Современные информационные технологии связаны с обработкой и хранением достаточно больших объемов данных. Если информация представлена в упорядоченном виде, то ее обработка, в частности поиск данных, значительно упрощается. Реализации алгоритмов на разных языках программирования находят широкое практическое применение. Методы сортировки информации исследуются достаточно давно. Однако исключать возможности появления новых, еще неизвестных методов, которые основаны на оригинальных идеях, нельзя. Поэтому изучение этой области информатики остается актуальным. Кроме того, несмотря на повышение производительности вычислительной техники, важным остается вопрос об эффективности алгоритмов. С этой точки зрения анализ существующих алгоритмов также является насущной проблемой. В данной работе рассматриваются комбинаторные алгоритмы сортировки. Приводятся теоретические сведения об особенностях различных групп алгоритмов. Более подробно проводится анализ сортировок методом распределения. В практической части работы реализуется алгоритм метода распределения на языке С, а также проводится вычислительный эксперимент, позволяющий сделать выводы об эффективности реализованных алгоритмов.   Содержание

h>#include<conio.h>usingnamespacestd;//список для представления данныхstruct list{ longval;list *next; };// функция сортировки возвращает указатель // на начало отсортированного списка list *SortL(list *l, int K) {int d, p = 1;constint M = 10;list *temp;list *h[M], *t[M];// массивы для хранения указателей на //начало и конец вспомогательных списковfor (int j = 1; j <= K; j++) { for (inti = 0; i <= M - 1; i++)h[i] = (t[i] = 0);//распределение элементов по спискамwhile ( l != 0 ) { d = (l -> val / p) % 10;temp = t[d];if (h[d] == 0) h[d] = l;else temp -> next = l;temp = t[d] = l; l = l-> next;temp -> next = 0; }//сцепление списковint i;for (i = 0; i <= M - 1; i++)if ( h[i] != 0 ) break; l = h[i]; temp = t[i];for(d = i + 1; d <= M - 1; d++){if ( h[d] != 0) { temp -> next = h[d];temp = t[d];} } p *= 10; //переход к следующему разряду числа }return (l);}//функция создания связного списка//генерацияслучайныхчиселvoidcreate_list(list* &h1, int N){h1 = new list;list* pt = h1;pt -> val = rand() % 1000;for(inti = 1; i <= N; i++) {pt -> next = new list;pt = pt -> next;pt -> val = rand() % 1000;pt -> next = 0;}}//функция записи содержимого списка в файлvoidprint_list(list* &h1, ofstream &g){list *pt = h1;while (pt){g << pt -> val << " ";pt = pt -> next;}}intmain(){int N = 100000; //количество сортируемых элементовint K = 3; //разрядность числа ofstreamf_in("input.txt");ofstreamf_out("output.txt");list *lst, *sortlist;//создание спискаtime_t t;srand((unsigned) time(&t));create_list(lst, N);//печать исходного сгенерированного списка в файлprint_list(lst, f_in);clock_t tm;tm = clock();//сортировка связного списка методом распределенияsortlist = SortL(lst, 3);//время работы сортировкиtm = clock() - tm;cout <<"time = " << tm << endl;//печать отсортированного списка в файлprint_list(sortlist, f_out);f_in.close();f_out.close();getch();return 0;}Приложение 3Программа сортировки распределением связного списка строк#include<iostream>#include<fstream>#include<conio.h>#include<string>#include<conio.h>#include<time.h>usingnamespacestd;//список для представления данныхstructlist{stringstr; //указатель на строкуlist* next;};// функция сортировки возвращает указатель // на начало отсортированного списка list* SortS(list* l, unsignedint p ){//l - начало списка указателей на строки//p - разряд, по которому сортирует// количество вариантов значения одного разряда (char)constint M = 26; //массив вспомогательных списковlist* sp[M]; memset(sp, 0, sizeof(sp));list** pp[M]; for (inti = 0; i < M; i++)pp[i] = &sp[i];//распределение элементов по спискамwhile (l) {list* temp = l;l = l -> next;temp -> next = 0; //отключаем от спискаunsignedchar c = (unsignedchar)temp -> str[p]; *pp[c-65] = temp; pp[c-65] = &temp -> next; }//сцеплениесписковlist* res = 0;list** pn = &res;//пустой писок возвращаем весь - он уже отсортирован*pn = sp[0];while (*pn) pn = &((*pn) -> next);for (inti = 1; i < M; i++) {//пустые списки пропускаемif (!sp[i]) continue;if (!(sp[i] -> next))// с одним элементом сразу сцепляем *pn = sp[i];else// для остальных вызываем сортировку по следующему разряду*pn = SortS(sp[i], p + 1);while (*pn)pn = &((*pn) -> next);}returnres;}//---------------------------------------------------------------intmain(){ofstream file("input.txt"); string text;list* lst = 0;list* sortlist = 0;list** pt = &lst;time_t t;srand((unsigned) time(&t));int N = 100000; //количество сортируемых элементовint K = 7;// максимальная длина строки//заполнение списка случайными строкамиfor(int j=1; j<=N; j++){text = "";for(inti = 0; i < K; i++)text += char(rand() % 26 + 65);*pt = newlist();(*pt )->str = text;file << (*pt ) -> str << endl;(*pt )->next = 0;pt = &(*pt)->next; }file.close();clock_t tm;tm = clock();//сортировка методом распределения//от старшего разряда к младшемуsortlist = SortS(lst, 0);//время работы сортировкиtm = clock() - tm;cout <<"time = " << tm << endl;//вывод в файл отсортированного спискаofstream g("output.txt");while (sortlist){g << sortlist -> str << endl;sortlist = sortlist -> next;}getch();return 0;}Приложение 4Программа быстрой сортировки массива целых чисел#include<iostream>#include<conio.h>#include<time.h>#include<math.h>usingnamespacestd;voidSortQ(long * a, int l, int r){int x = a[l + (r - l) / 2];inti = l;int j = r;while(i <= j) {while(a[i] < x) i++;while(a[j] > x) j--;if(i <= j) {swap(a[i], a[j]);i++; j--;} }if (i<r) SortQ(a, i, r);if (l<j) SortQ(a, l, j); }intmain(){int N = 100; //количество сортируемых элементовlong R = long(pow(10.0,3));long* arr = newlong[N];//входноймассив//заполнение входного массива случайными числами//только целых чисел типа inttime_t t;srand((unsigned) time(&t));for (inti = 0; i< N; i++) arr[i] = rand() % R; //случайные числа заданной разрядности//быстрая сортировкаSortQ(arr,0, N-1);//вывод отсортированного массива чиселfor (inti = 0; i< N; i++) cout << arr[i] << ' ';cout << endl;delete[]arr;getch();return 0;}