Вход

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

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 67206
Дата создания 2014
Страниц 18
Источников 2
Мы сможем обработать ваш заказ 4 октября в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 810руб.
КУПИТЬ

Содержание

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

Фрагмент работы для ознакомления

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;}

Список литературы [ всего 2]

Литература 1. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск: пер. с англ. – М.: Мир, 1978. — 846 с. 2. Мейер Б. Методы программирования: В 2-х томах. Т.2 / Б.Мейер, К Бодуэн; пер. с франц. Ю.А.Первина. Под ред. А.П.Ершова. – М.: Мир, 1982, 368с. список литературы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
© Рефератбанк, 2002 - 2022