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

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 = 100 000; //количество сортируемых элементов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 = 100 000; //количество сортируемых элементов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;}.