Лабораторная работа №3

Добрый вечер, гвардейцы. Хотел сделать красивый пост с описанием работы всех сортировок, но, увы, не успел, потому выкладываю просто файл со всеми реализованными сортировками. Проверки все достаточно топорные, так что перепишете под себя, если захотите =) По всем вопросам писать сюда под тему

• Bubble sort
• Merge sort
• Radix LSD
• Selection sort
• HeapSort
• Counting sort
• Shell Sort
• Quick Sort

Ctrl+F и вводим нужную сортировку.

Сортировки

Пузырек (Bubble sort)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>
using namespace std;
void BubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n – 1 - j; j++)
        {
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
}

int main()
{
    const int n = 10000; //Вводим длину массива
    int a[n];
    /*
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    */

    freopen("input10k.txt", "r", stdin); // Для конечного тестирования на скорость 

    unsigned int start_time = clock();

    BubbleSort(a, n);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;

    cout << "Sorted:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
}

Cлияние (merge sort)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;
void Merge(int arr[], long int left, long int right, long int mid)
{
    long int i, j = 0, k = left, nleft = mid - left + 1, nright = right - mid;
    int* LeftArr = new int[nleft], * RightArr = new int[nright];

    for (i = 0; i < nleft; i++)
        LeftArr[i] = arr[left + i];
    for (i = 0; i < nright; i++)
        RightArr[i] = arr[mid + i + 1];
    i = 0;
    while (i < nleft && j < nright) {
        if (LeftArr[i] <= RightArr[j]) {
            arr[k] = LeftArr[i];
            i++;
        }
        else {
            arr[k] = RightArr[j];
            j++;
        }
        k++;
    }
    while (i < nleft) {
        arr[k] = LeftArr[i];
        i++;
        k++;
    }
    while (j < nright) {
        arr[k] = RightArr[j];
        j++;
        k++;
    }
}
void MergeSort(int arr[], long int left,long int right)
{
    if (left < right) {
        long int mid = (left + right - 1) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, right, mid);
    }
}


int main()
{
    const long int n = 10; //Вводим длину массива
    int *a=new int[n];
    
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    
     
    /*
    freopen("input10k.txt", "r", stdin); // Для конечного тестирования на скорость 
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    */
    unsigned int start_time = clock();

    MergeSort(a, 0, n-1);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;

    
    cout << "Sorted:" << endl; //Вывод массива
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    
}

Разрядная (Radix LSD)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;
int Rad(int x, int n)
{
    return (x / int(pow(10, n))) % 10;
}
void RadixSort(int arr[], long int n)
{
    for (int j = 0; j <= 4; j++)
    {
        long int k=0;
        int** R = new int* [10];
        int nR[10];
        for (int i = 0; i <= 9; i++)
        {
            R[i] = new int[n];
            nR[i] = 0;
        }

        for (int i = 0; i < n; i++)
        {
            int num = Rad(arr[i], j);
            R[num][nR[num]] = arr[i];
            nR[num]++;
        }

        for (int i = 0; i <= 9; i++)
        {
            for (int l = 0; l < nR[i]; l++)
            {
                arr[k] = R[i][l];
                k++;
            }
        }

        for (int i = 0; i <= 9; i++)
            delete[]R[i];
    }
}


int main()
{
    const long int n = 90000; //Вводим длину массива
    int *a=new int[n];
    /*
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    */
     
    
    freopen("input90k.txt", "r", stdin); // Для конечного тестирования на скорость 
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    
    unsigned int start_time = clock();

    RadixSort(a, n);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;
    
    /*
    cout << "Sorted:" << endl; //Вывод массива
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    */
    delete[]a;
}

Выбором (Selection Sort)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

void SelectionSort(int arr[], long int n)
{
    for (long int i = 0; i < n; i++)
    {
        int minx = arr[i];
        long int minc = i;
        for (long int j = i+1; j < n; j++)
        {
            if (arr[j] < minx) { minx = arr[j]; minc = j; }
        }
        swap(arr[i], arr[minc]);
    }
}


int main()
{
    const long int n = 30000; //Вводим длину массива
    int *a=new int[n];
    /*
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    */
     
    
    freopen("input30k.txt", "r", stdin); // Для конечного тестирования на скорость 
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    
    unsigned int start_time = clock();

    SelectionSort(a, n);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;
    
    
    cout << "Sorted:" << endl; //Вывод массива
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    
    delete[]a;
}

Пирамидальная сортировка (HeapSort/ сортировка кучей)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

void DoubleHeap(int arr[], long int n, long int root)
{
    long int Big = root, n1 = 2 * root + 1, n2 = 2 * root + 2;
    if (arr[Big] < arr[n1] && n1 < n) Big = n1;
    if (arr[Big] < arr[n2] && n2 < n) Big = n2;
    if (Big != root) { swap(arr[root], arr[Big]); if(Big<=n/2-1) DoubleHeap(arr, n, Big); }
}
void HeapSort(int arr[], long int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        DoubleHeap(arr, n, i);
    for (int i = n - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        DoubleHeap(arr, i, 0);
    }
}

int main()
{
    const long int n = 810000; //Вводим длину массива
    int* a = new int[n];
    /*
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    */

    
    freopen("input810k.txt", "r", stdin); // Для конечного тестирования на скорость
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    
    unsigned int start_time = clock();

    HeapSort(a, n);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;

    /*
    cout << "Sorted:" << endl; //Вывод массива
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    */
    return 0;
}

Подсчетом (Counting sort)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

void CountingSort(int arr[], long int n)
{
    int maxel = arr[0];
    for (int i = 0; i < n;i++)
        if (arr[i] > maxel) maxel = arr[i];
    int* a = new int[maxel + 1];
    for (int i = 0; i <= maxel;i++)
        a[i] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = arr[i];
        a[t]=a[t]+1;
    }
        
    for (int i = 0; i <= maxel; i++)
        for (int j = 1; j <= a[i]; j++)
            cout << i << " ";
    cout << endl;
}

int main()
{
    const long int n = 10; //Вводим длину массива
    int *a=new int[n];
    /*
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    */
     
    
    freopen("input810k.txt", "r", stdin); // Для конечного тестирования на скорость 
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    
    unsigned int start_time = clock();

    CountingSort(a, n);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;
    
    /*
    cout << "Sorted:" << endl; //Вывод массива
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    */
    return 0;
}

Shell Sort (взяты базовые промежутки Шелла)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;
void ShellSort(int arr[], long int n)
{
    for (int d=n/2;d>0;d=d/2)
    {
        for (int i = d; i < n; i++)
            for (int j = i; j > 0 && arr[j - d] > arr[j]; j-=d)
                swap(arr[j - d], arr[j]);
    }
}

int main()
{
    const long int n = 10; //Вводим длину массива
    int* a = new int[n];
    
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    

    /*
    freopen("input30k.txt", "r", stdin); // Для конечного тестирования на скорость 
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    */
    unsigned int start_time = clock();

    ShellSort(a, n);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;
    

    cout << "Sorted:" << endl; //Вывод массива
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }

    return 0;
}

Quick Sort
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;
void QuickSort(int arr[], long int left, long int right)
{
    int i = left;
    int j = right;
    int x = arr[(i + j) / 2];
    do
    {
        while (arr[i] < x)
            i++;
        while (arr[j] > x)
            j--;
        if (i <= j) {swap(arr[i], arr[j]); i++; j--;}
        
    } while (i <= j);
        





    if (left < j) QuickSort(arr,left, j);
    if (i < right) QuickSort(arr,i, right);


}

int main()
{
    const long int n = 810000; //Вводим длину массива
    int *a=new int[n];
    /*
    int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % mod;
        cout << a[i] << " ";
    }
    cout << endl;
    */
     
    
    freopen("input810k.txt", "r", stdin); // Для конечного тестирования на скорость 
    for (long int i = 0; i < n; i++)
        cin >> a[i];
    
    unsigned int start_time = clock();
    
    QuickSort(a, 0, n-1);

    unsigned int end_time = clock();
    unsigned int search_time = end_time - start_time;
    cout << "Time in seconds: " << double(search_time) / double(1000) << endl;
    
    /*
    cout << "Sorted:" << endl; //Вывод массива
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    */
    return 0;
}