Файл: Сортировка слиянием.pdf

radix_sort(arr + last, size - last, bit >> 1);

}

int main(int argc, char* argv[])

{

// Первая часть программы

// демонстрирует работоспособность наших функций для сортировки

// массива из 10 элементов, заполненного случайными двухзначными числами.

const int sz = 10; // размер массива

int a[sz]; // исходный неотсортированный массив

int b[sz]; // массив для сортировки

int c[sz]; // буфер для функции merge_sort

int* r; // переменная для получения результата работы функции merge_sort

//заполняем массив a случайными числами от -99 до 99

//и выводим на экран

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

{

a[i] = rand() % 100 * (rand() % 2 ? -1 : 1);

cout << a[i] << " ";

}

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

selection_sort(b, sz); // сортируем массив b

cout << "\n" << "selection_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

insertion_sort(b, sz); // сортируем массив b

cout << "\n" << "insertion_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

bubble_sort(b, sz); // сортируем массив b

cout << "\n" << "bubble_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

shells_sort(b, sz); // сортируем массив b

cout << "\n" << "shells_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

quick_sort(b, 0, sz - 1); // сортируем массив b

cout << "\n" << "quick_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

r = merge_sort(b, c, 0, sz - 1); // сортируем массив b

cout << "\n" << "merge_sort: ";

for (int i = 0; i < sz; i++) cout << r[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

heap_sort(b, sz); // сортируем массив b

cout << "\n" << "heap_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

memcpy(b, a, sz * sizeof(int)); // копируем массив а в b

radix_sort(b, sz); // сортируем массив b

cout << "\n" << "radix_sort: ";

for (int i = 0; i < sz; i++) cout << b[i] << " "; // выводим массив на экран

cout << "\n";

// Вторая часть программы измеряет и выводит на экран время выполнения

// каждой из наших функций сортировки при сортировке сначала массива из 1000000

// случайных чисел, а затем сортировке уже отсортированного массива.

const int SZ = 1000000; // размер массива

int* A = new int[SZ]; // исходный неотсортированный массив

int* B = new int[SZ]; // массив для сортировки

int* C = new int[SZ]; // буфер для функции merge_sort

int* R; // переменная для получения результата работы функции merge_sort

unsigned t; // переменная для сохранения текущего времени перед началом сортировки

// заполняем массив А случайными числами

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

{

A[i] = rand();

}

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

selection_sort(B, SZ); //сортируем массив B

cout << "\n" << "selection_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

selection_sort(B, SZ); //сортируем уже отсортированный массив B

cout << ", " << clock() - t; //выводим время выполнения

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

insertion_sort(B, SZ); //сортируем массив B

cout << "\n" << "insertion_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

insertion_sort(B, SZ);//сортируем уже отсортированный массив B

cout << ", " << clock() - t; //выводим время выполнения

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

bubble_sort(B, SZ); //сортируем массив B

cout << "\n" << "bubble_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

bubble_sort(B, SZ);//сортируем уже отсортированный массив B

cout << ", " << clock() - t; //выводим время выполнения

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

shells_sort(B, SZ); //сортируем массив B

cout << "\n" << "shells_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

shells_sort(B, SZ); //сортируем уже отсортированный массив B

cout << ", " << clock() - t; //выводим время выполнения

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

quick_sort(B, 0, SZ - 1); //сортируем массив B

cout << "\n" << "quick_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

quick_sort(B, 0, SZ - 1); //сортируем уже отсортированный массив B

cout << ", " << clock() - t; //выводим время выполнения

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

R = merge_sort(B, C, 0, SZ - 1); //сортируем массив B

cout << "\n" << "merge_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

R = merge_sort(R, R == C ? B : C, 0, SZ - 1); //сортируем уже отсортированный массив R

cout << ", " << clock() - t; //выводим время выполнения

memcpy(B, A, SZ * sizeof(int)); // копируем массив A в B

t = clock(); // запомниаем исходное время

heap_sort(B, SZ); //сортируем массив B

cout << "\n" << "heap_sort: " << clock() - t; //выводим время выполнения

t = clock(); // запомниаем исходное время

heap_sort(B, SZ); //сортируем уже отсортированный массив B