#include <iostream>
#include <cstdlib>
#include <conio.h>
#include <time.h>

using namespace std;

int sort_1(int tab[],int ilosc) {  //przez wybor
    int s=0;
	int tymczas;
	for (int i=0;i<ilosc;i++)
      for (int j=0;j<ilosc;j++)
        if (tab[i]<tab[j]) {
			tymczas=tab[i];
			tab[i]=tab[j];
			tab[j]=tymczas;
			s++;
		}
	return s;
}

int sort_2(int tab[],int ilosc) {  //bombelkowe
    int s=0;
    int tymczas;
	int i=0;
	do {
		if 	(tab[i]>tab[i+1]) {
			tymczas=tab[i];
			tab[i]=tab[i+1];
			tab[i+1]=tymczas;
			s++;
			if (i>0) {
				i--; 
			}
			else i++;
		}
		else i++;
	} while (i!=ilosc);
	return s;
}

int podziel(int tab[], int p, int r) {  // fnkcja do sort_q
	int x = tab[p]; 
	int i = p, j = r, w; 
	while (true) { // powtarzam nieskonczenie wiele razy
		while (tab[j] > x) // dopoki elementy sa wieksze od x
			j--;
		while (tab[i] < x) // dopoki elementy sa mniejsze od x
			i++;
		if (i < j) {// zamieniamy miejscami gdy i < j
			w = tab[i];
			tab[i] = tab[j];
			tab[j] = w;
		i++;
		j--;
		}
	else 
		return j;
	}
}

void sort_q(int tab[], int p, int r) {  // sortowanie szybkie
int q;
if (p < r) {  
	q = podziel(tab,p,r); 
	sort_q(tab, p, q); 
	sort_q(tab, q+1, r); 
	}
}

int main() {     
    clock_t t;
	int ilosc=100000;
	int tab[ilosc];
    for (int i=0;i<ilosc;i++) tab[i]=rand()%10000;
    cout<<"przed sortowaniem"<<endl;
//	for (int i=0;i<ilosc;i++) cout<<tab[i]<<" ";
    cout<<endl;
    t = clock();

//	cout<<"Liczba uzycia tablicy: "<<sort_1(tab,ilosc)<<endl;
//	cout<<"Liczba uzycia tablicy: "<<sort_2(tab,ilosc)<<endl;
	sort_q(tab,0,ilosc-1);
    t = clock() - t;

    cout<<"po sortowaniu"<<endl;
//    for (int i=0;i<ilosc;i++) cout<<tab[i]<<" ";
    cout<<endl<<"Czas trwanie "<<t<<endl;
    
 	getch();			
	return 0;			
}