Сравнение методов сортировки выбором, сортировки слиянием и сортировки вставками

h), методом слияния (merge.h) и выбором (select.h). Также разработаны функции, с помощью которых можно создать массив с заданным количеством элементов, подготовить его случайным образом или частично упорядоченным, отсортировать его любым из рассмотренных в курсовом проекте методом сортировки и узнать время сортировки массива. С помощью данного приложения был проведен экспериментальный анализ сортировок методом простых вставок, выбором и слиянием подтвердивший результаты теоретического сравнения эффективности данных сортировок. По данным экспериментального анализа в среднем сортировка методом слияния занимает значительно меньше времени, чем сортировка методами вставок и выбором. Вследствие этого можно сказать, что из рассмотренных методов — сортировка методом слияния, является наиболее эффективной на больших массивах данных.

Список литературы

Шмидский «Самоучитель программирования на Си"Портал Алгоритмы методы исходники.

http://algolist.manual.ru/Портал Конспектов.

http://www.konspektov.net/Алгоритмы и Структуры данных. Кормен. Структуры данных на.

http://habrahabr.ru/Алгоритмы сортировок. Киберфорум.

http://www.cyberforum.ru/cpp-beginners/thread27084.html.

https://ru.wikipedia.org/wiki/%D1%EE%F0%F2%E8%F0%EE%E2%EA%E0_%E2%F1%F2%E0%E2%EA%E0%EC%E8.

https://ru.wikipedia.org/wiki/%D1%EE%F0%F2%E8%F0%EE%E2%EA%E0_%F1%EB%E8%FF%ED%E8%E5%EC.

https://ru.wikipedia.org/wiki/%D1%EE%F0%F2%E8%F0%EE%E2%EA%E0_%E2%FB%E1%EE%F0%EE%EC Алгоритмы для начинающих.

http://www.cyberforum.ru/cpp-beginners/thread27084.htmlПриложение А. Текст основной программы<analiz_sortorovok.cpp>#include «stdafx.h» #include «stdio.h» #include «stdlib.h» #include «conio.h» #include «math.h» #include «time.h» ////////////////////////////////#include «inserts.h» #include «select.h» #include «merge.h» #include «crt.h» void print_array (int *a, int size);void semi_sort (int *a, int size, double factor);void rand_array (int *a, int size, int factor);void back_sort (int *a, int size);void sort (int type, int*a, int size);void prepare_array (int *a, int n, int test_type);void demo_test (int *a[], int testtypes, int size);int main (){srand (int (time (NULL)));FILE *f; fopen_s (&f," output. txt" ," w");int const max_array_count = 100, maxn = 25 000, start_n = 2000; //constants of size and quantity of arraysdouble const factor_n = 1.4641;//and stepint test_type, test_time = 100 ;int sort_types =4;//число измеряемых типов сортировок int *a[max_array_count]; for (int i=0;i<max_array_count;i++)a[i] = (int*) malloc (maxn*sizeof (int)); //arrays to test here demo_test (a, 3,20);clock_t begin, end; //current timers here for (test_type = 0;test_type<3;test_type++){/// TREE BLOCKS OF TESTING — Random, Semi-sorted, Back-sortedswitch (test_type) {case 0:{printf («…Random array testing… n»);fprintf (f," …Random array testing… n");break;}case 1:{printf («…Semi-sorted array testing… n»);fprintf (f," …Semi-sorted array testing… n");break;}case 2:{printf («…Back-sorted array testing… n»);fprintf (f," …Back-sorted array testing… n");break;}};printf («Sort type: select insert merge qsortn»);fprintf (f," Sort type: select insert merge qsortn");for (int n = start_n; n<=maxn; n=int (n*factor_n)){printf («N=%5d «, n);fprintf (f,» N=%5d «, n);for (int sort_type = 0;sort_type<sort_types;sort_type++){int cl_time = 0;//счетчикисполненийdouble timer = 0;while (timer<test_time){for (int i=0;i<max_array_count;i++)prepare_array (a[i], n, test_type);clock_stop (); begin =clock ();for (int i=0;i<max_array_count;i++){sort (sort_type, a[i], n);//сортировкауказаннымтипомif (timer + double (clock ()-begin)>test_time){cl_time ++;break;}cl_time ++;}end = clock ();//замервремениtimer += double (end-begin);//суммируемвремя}double tt = timer/cl_time;// замер времени конца процессаprintf («%8.3f «, tt);//вывод времени на экранfprintf (f,» %8.3f «, tt);//вывод времени в файл}printf («n»);fprintf (f,» n»);}printf («.

—- press a key to continue —-n");keystop ();clrscr ();fprintf (f," .

——————————————n");fflush (f);}fclose (f);_getch ();return 0;}void demo_test (int *a[], int testtypes, int size){char test_names[3][20] = {" Select" ," Insert" ," Merge" };setcolor (15,0);for (int i = 0;i<testtypes;i++){rand_array (a[i], size, 100);//random arrayprintf («Initial array: n»);print_array (a[i], size);printf («Sorting type:»);setcolor (i+11,0);printf («%7s», test_names[i]);setcolor (15,0);printf («. Sorted array: n»);sort (i, a[i], size);print_array (a[i], size);}printf («.

—- press a key to continue —-n");keystop ();clrscr ();}void prepare_array (int *a, int n, int test_type){rand_array (a, n,0);switch (test_type) {case 0: break;case 1:{semi_sort (a, n,0.5); //sort of first half of arraysbreak; }case 2:{back_sort (a, n); //back sort of all arraysbreak; }};// подготовка массива к сортировкам }int comparator (const void *a, const void *b){int *p = (int*)a,*q = (int*)b;if ((*p)>(*q)) return 1; else if ((*p)<(*q)) return -1; else return 0;}void sort (int type, int*a, int size){switch (type) {case 0:{select_sort (a, size);break;}case 1:{insert_sort (a, size);break;} case 2:{merge_sort (a, 0, size-1);break;}default: {qsort (a, size, sizeof (int),&comparator);break;}};}void print_array (int *a, int size){for (int i=0;i<size;i++)printf («%3d «, a[i]);printf («n»);}int back_comparator (const void *a, const void *b){int *p = (int*)a,*q = (int*)b;if ((*p)>(*q)) return -1; else if ((*p)<(*q)) return 1; else return 0;}void semi_sort (int *a, int size, double factor){factor=fabs (factor);if (factor>1) factor=1.0/factor;size = int (size * factor);qsort (a, size, sizeof (int),&comparator);}void rand_array (int *a, int size, int factor){factor = abs (factor);if (!factor) factor = 128*256;for (int i=0;i<size;i++)a[i]=rand ()%factor;}void back_sort (int *a, int size){qsort (a, size, sizeof (int),&back_comparator);}Приложение Б. Тексты функций сортировки<merge.h>#pragma once// сортировкаслияниемvoid merge (int *a, int first, int middle, int last) {int idx = first; // Куда будем делать слияниеint begin1 = first, end1 = middle; // Первыйиздвухсливаемыхмассивов a[begin1]. .a[end1] int begin2 = middle+1, end2 = last; // Второйиздвухсливаемыхмассивов a[begin2]. .a[end2]int *temp = new int [last — first + 1]; for (; begin1 <= end1 && begin2 <= end2;) {if (a[begin1] <= a[begin2]) {temp[idx-first] = a[begin1++]; }else {temp[idx-first] = a[begin2++]; }idx++; }for (; begin1 <= end1;){temp[idx++ - first] = a[begin1++]; }for (; begin2 <= end2;){temp[idx++ - first] = a[begin2++]; }for (idx = first; idx <= last; idx++){a[idx] = temp[idx-first]; }delete [] temp;}void merge_sort (int *a, int first, int last) { if (first < last) { int m = (first + last)/2; merge_sort (a, first, m); merge_sort (a, m+1, last); merge (a, first, m, last); }}<inserts.h>#pragma once// сортировкавставкамиvoid insert_sort (int *arr, int size) { for (int i = 0; i < size; i++) { int j; int buf = arr[i]; for (j = i — 1; j >= 0; j—) { if (arr[j] < buf) break; arr[j + 1] = arr[j]; } arr[j + 1] = buf; }}<Select.h>#pragma once// сортировкавыборомvoid select_sort (int *items, int count) {bool exchange; int a, b, c, t;for (a=0; a < count-1; ++a) {exchange = false;c = a;t = items[a]; for (b=a+1; b < count; ++b) {if (items[b] < t){c = b;t = items[b]; exchange = true;}}if (exchange){ items[c] = items[a]; items[a] = t;}}}Приложение C. Модуль работы с экраном.<CRT.h>#pragma once//модуль функций по работе с экраном, цвет позиция курсора итд#include <windows.h>#include <time.h>#include <conio.h>#include <stdlib.h>#include <stdio.h>#include <iostream>using namespace std;void gotoxy (int xpos, int ypos){//установитьпозициюкурсора COORD scrn; HANDLE hOuput = GetStdHandle (STD_OUTPUT_HANDLE); scrn. X = xpos; scrn. Y = ypos; SetConsoleCursorPosition (hOuput, scrn);}void setcolor (int text, int background) {//установитьцветсимволовифона HANDLE hOutput = GetStdHandle (STD_OUTPUT_HANDLE); SetConsoleTextAttribute (hOutput, static_cast<WORD>(background<<4 — text));}void clearline (int i){//очиститьлиниюgotoxy (0,i);for (int i=0;i<80;i++) printf (««);}void keystop (){// остановка до нажатия кнопки! int c; while (_kbhit ()) c=_getch (); while (!_kbhit ());}void clear_key_buf (){//очиститьбуферклавиатурыint c; while (_kbhit ()) c=_getch (); }void clrscr (){//очиститьэкранsystem («cls»); }void delay (long m){//задержка.

Ммиллисекундclock_t begin, end; begin=clock ();end=begin;while (long (end-begin)<m) end=clock (); }void clock_stop (){//ожидание до смены состояния счетчика времени (1 тик внутренних часов) clock_t x, y; x=clock ();y=x; while (!long (y-x)) y=clock ();}void window (int x1, int y1, int x2, int y2, char *header){//окнопокоординатамсрамкойизаголовкомint i;for (i=x1;i<x2;i++){gotoxy (i, y1);cout<<char (196);gotoxy (i, y2);cout<<char (196);}for (i=y1;i<y2;i++){gotoxy (x1,i);cout<<char (179);gotoxy (x2,i);cout<<char (179);}gotoxy (x2,y1);cout<<char (191);gotoxy (x1,y2);cout<<char (192);gotoxy (x2,y2);cout<<char (217);gotoxy (x1,y1);cout<<char (218);gotoxy ((x2+x1-strlen (header))/2,y1);cout<<header;}void floodwindow (int color, int back, int x1, int y1, int x2, int y2, char *header){//тожесамоеокноносочисткойсодержимоговсегочтовнутрикоординатsetcolor (color, back);for (int i=y1;i<=y2;i++){gotoxy (x1,i);for (int j=x1;j<=x2;j++) printf (««);}window (x1,y1,x2,y2,header);}.