Файл: Общие сведения об алгоритмах сортировки.pdf

Рисунок 13. Скриншот сортировки пузырьковым методом

Сортировка вставками демонстрирует вдвое меньшее количество проходов, по сравнению с пузырьковой сортировкой. Но при этом количество перестановок очень велико (рис.14).

Рисунок 14. Скриншот сортировки вставками

Сортировка слиянием на данном примере продемонстрировала наилучший результат (рис.15).

Рисунок 15. Скриншот сортировки слиянием

Быстрая сортировка оказалась не так хороша, как сортировка слияние, но результат все же неплохой (рис.16).

Рисунок 16. Скриншот быстрой сортировки

Однако, на уже отсортированном массиве быстрая сортировка выполняет очень большое число ненужных перестановок (рис.17).

Рисунок 17. Скриншот быстрой сортировки на уже отсортированном массиве

Заключение

На основании проведенного исследования можно сделать вывод, что выбор используемого алгоритма сортировки зависит от многих критериев. Необходимо учитывать размер массива, степень его предварительной сортировки (несортированный, частично или полностью отсортированный), потребность в устойчивости алгоритма (т.е. отсутствие лишних перестановок), наконец, скорость чтения и записи данных (есть алгоритмы с высоким числом считываний, но с небольшим числом записей данных).

В результате выполнения данной курсовой работы были исследованы наиболее популярные алгоритмы сортировки и реализовано приложение с демонстрацией всех описанных алгоритмов.

Список использованной литературы

1. https://ru.wikipedia.org Электронный ресурс
2. Роберт Седжвик. Фундаментальные алгоритмы на С++. Части 1-4: Анализ/Структуры данных/Сортировка/Поиск. - К.: Издательство ДиаСофт?, 2001.
3. Роберт Седжвик. Фундаментальные алгоритмы на С++. Часть 5: Алгоритмы на графах. - К.: Издательство ДиаСофт?, 2002.
4. Роберт Седжвик. Фундаментальные алгоритмы на С. Части 1-4: Анализ/Структуры данных/Сортировка/Поиск. - К.: Издательство ДиаСофт?, 2003.
5. Роберт Седжвик. Фундаментальные алгоритмы на С Часть 5: Алгоритмы на графах. - К.: Издательство ДиаСофт?, 2003.
6. Джон Макгрегор, Девид Сайке. Тестирование объектно-ориентированного программного обеспечения. Практическое пособие. - К.: Издательство ДиаСофт?, 2002.

Приложения

#include <iostream>

#include <locale>

#include <math.h>

using namespace std;

const int SIZE_M = 100;

int m[SIZE_M];

int pr = 0, per = 0;

void clearPr()

{

pr = 0;

per = 0;

}

void print()

{

for (int i = 0; i < SIZE_M; i++)

{

cout << m[i] << "\t";

}

cout << endl;

cout << "количество проходов = " << pr << endl;

cout << "количество перестановок = " << per << endl;

}

void create_m()

{

for (int i = 0; i < SIZE_M; i++)

{

m[i] = rand();

}

}

void selectionSort()

{

int j = 0;

int tmp = 0;

for (int i = 0; i<SIZE_M; i++)

{

j = i;

for (int k = i; k<SIZE_M; k++)

{

pr++;

if (m[j]>m[k])

{

j = k;

per++;

}

}

tmp = m[i];

m[i] = m[j];

m[j] = tmp;

}

}

void bubbleSort()

{

int tmp = 0;

for (int i = 0; i<SIZE_M; i++)

{

for (int j = (SIZE_M - 1); j >= (i + 1); j--)

{

pr++;

if (m[j]<m[j - 1])

{

per++;

tmp = m[j];

m[j] = m[j - 1];

m[j - 1] = tmp;

}

}

}

}

void insertionSort()

{

int key = 0;

int i = 0;

for (int j = 1; j<SIZE_M; j++)

{

key = m[j]; per++;

i = j - 1;

while (i >= 0 && m[i]>key)

{

pr++;

m[i + 1] = m[i]; per++;

i = i - 1;

m[i + 1] = key; per++;

}

}

}

void merge(int merged[], int lenD, int L[], int lenL, int R[], int lenR){

int i = 0;

int j = 0;

while(i<lenL||j<lenR)

{

pr++;

if (i<lenL & j<lenR)

{

if(L[i]<=R[j])

{

merged[i+j] = L[i];

i++;

per++;

}

else

{

merged[i+j] = R[j];

j++;

per++;

}

}

else if(i<lenL)

{

merged[i+j] = L[i];

i++;

per++;

}

else if(j<lenR)

{

merged[i+j] = R[j];

j++;

per++;

}

}

}

void mergeSort(int data[], int lenD)

{

if (lenD>1) {

int middle = lenD / 2;

int rem = lenD - middle;

int* L = new int[middle];

int* R = new int[rem];

for (int i = 0; i<lenD; i++)

{

pr++;

if (i<middle)

{

L[i] = data[i];

per++;

}

else

{

R[i - middle] = data[i];

per++;

}

}

mergeSort(L, middle);

mergeSort(R, rem);

merge(data, lenD, L, middle, R, rem);

}

}

void quickSort(int* data, int const len)

{

int p = 0;

int ind = lenD / 2;

int i, j = 0, k = 0;

if (lenD>1) {

int* L = new int[len];

int* R = new int[len];

p = data[ind];

for (i = 0; i<lenD; i++)

{

pr++;

if (i != ind)

{

if (data[i]<p)

{

L[j] = data[i];

j++;

per++;

}

else

{

R[k] = data[i];

k++;

per++;

}

}

}

quickSort(L, j);

quickSort(R, k);

for (int cnt = 0; cnt<len; cnt++)

{

pr++;

if (cnt<j)

{

data[cnt] = L[cnt];

per++;

}

else if (cnt == j)

{

data[cnt] = p;

per++;

}

else

{

data[cnt] = R[cnt - (j + 1)];

per++;

}

}

}

}

void main()

{

setlocale(LC_CTYPE, "Russian");

cout << "заполнение массива случайными числами: " << endl;

create_m();

print();

while (true)

{

cout << "Выберите действие: " << endl;

cout << "1 - Сортировка выбором(Selection sort) " << endl;