sortowanie

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>

#define N 10000
#define NUM 13
using namespace std;
void wstaw(int tab[], int low, int high)
{
    for (int i = low + 1; i <= high; i++)
    {
        int value = tab[i];
        int j = i;

        // Znajdujemy element j w posortowanym podzbiorze
        // w którym znajduje się element tab[i]
        while (j > low && tab[j - 1] > value)
        {
            tab[j] = tab[j - 1];
            j--;
        }
        // tablica przesuwa się o jedną pozycje w prawo

        tab[j] = value;
    }
}

int Partition (int tab[], int low, int high)
{
    // za q przyjmujemy ostatni element tablicy
    int q = tab[high];

    // elementy mniejsze od q przesuwaja sie na lewo,
    // a elementy większe od q przesuwaja sie na prawo
    // równe elementy mogą iść i tu i tu
    int p = low;

    // Za każdym razem, gdy znajdziemy element mniejszy lub równy q, p jest zwiększany i element zostanie umieszczony przed q
    for (int i = low; i < high; i++)
    {
        if (tab[i] <= q)
        {
            swap(tab[i], tab[p]);
            p++;
        }
    }
    // zamieniamy p i q
    swap (tab[p], tab[high]);

    // zwracamy element łączący
    return p;
}

void quicksort(int tab[], int low, int high)
{
    // podstawowy warunek
    if (low >= high)
        return;

    // przestawiamy elementy względem q
    int q = Partition(tab, low, high);

    // rekurencyjnie dzielimy elementy które są mniejsze od q na coraz mniejsze podzbiory
    quicksort(tab, low, q - 1);

    // rekurencyjnie dzielimy elementy któe są większe od q na coraz mniejsze podzbiory
    quicksort(tab, q + 1, high);
}
void hybrid(int tab[], int low, int high)
{
    while (low < high)
    {
        // dla zbiorów mniejszych od 10 odrazu wykonujemy sortowanie przez wstawianie
        if (high - low < 10)
        {
            wstaw(tab, low, high);
            break;
        }
        else
        {
            int q = Partition(tab, low, high);

            if (q - low < high - q) {
                hybrid(tab, low, q - 1);
                low = q + 1;
            } else {
                hybrid(tab, q + 1, high);
                high = q - 1;
            }
        }
    }
}
//sprawdzenie czy tablica jest posortowana, jeżeli nie to wyskoczy error
bool isSorted(int tab[])
{
    int prev = tab[0];
    for (int i = 1 ; i < N; i++)
    {
        if (prev > tab[i])
        {
            cout << "QuickSort Failed!!";
            return false;
        }
        prev = tab[i];
    }

    return true;
}
int main()
{
	srand(time(NULL));
	clock_t s, f;
	double czas = 0.0, czas2 = 0.0;
	int tablica[N], tablica2[N];
	for(int j=0; j<NUM;j++)
	{
		for (int i = 0; i < N; i++) // wczytywanie liczb do tablicy
			tablica[i]=tablica2[i]=rand()%N;
		s=clock();
		quicksort(tablica,0,N-1);
		f=clock();
		czas+=(double)(f-s)/CLOCKS_PER_SEC;
		s=clock();
		hybrid(tablica2, 0, N-1);
		f=clock();
		czas2+=(double)(f-s)/CLOCKS_PER_SEC;
		if (!isSorted(tablica))
		{
			cout << "ERRROR";
		}
		if (!isSorted(tablica2))
		{
			cout << "ERRROR2";
		}
	}
	cout<<endl;
	cout<<"quicksort: "<<czas/NUM<<endl;
	cout<<"hybrid: "<<czas2/NUM<<endl;
	system("pause");
}