#include <iostream>
#include <stdlib.h>
#include <ctime>
 
using namespace std;
 
void TabMirror(int tab1[], int tab2[], int s) //kopiowanie z tab1 do tab2
{
	for (int i = 0; i < s; ++i)
	{
		tab2[i] = tab1[i];
	}
}
 
void display(int tab1[], int tab2[], int s) //wyswietlanie tablic
{
	for (int i = 0; i < s; ++i)
	{
		cout << "tablica1: " << tab1[i] << "\t\ttablica2: " << tab2[i] << endl;
	}
}
 
void quicksort(int tab[], int left, int right){
     int i=left;
     int j=right;
     int x=tab[(left+right)>>1];
     do{
         while(tab[i]<x) i++;
         while(tab[j]>x) j--;
         if(i<=j){
             int temp=tab[i];
             tab[i]=tab[j];
             tab[j]=temp;
             i++;
             j--;
         }
     }while(i<=j);
     if(left<j) quicksort(tab,left,j);
     if(right>i) quicksort(tab,i,right);
}
 
void sortowanie_wstawianie( int tab2[], int s )
{
    int temp, k;
 
    for( int i = 1; i < s; i++ )
    {
        temp = tab2[ i ];
 
        for( k = i - 1; k >= 0 && tab2[ k ] > temp; k-- )
             tab2[ k + 1 ] = tab2[ k ];
 
        tab2[ k + 1 ] = temp;
    }
}
 
void sortowanie_wybor(int tab2[], int s)
{
        int j,k;
    for(int i = 0; i < s; i++ )
    {
        k = i;
        for( int j = i + 1; j < s; j++ )
        if( tab2[ j ] < tab2[ k ] )
        k = j;
        swap( tab2[ k ], tab2[ i ] );
    }
}
 
void sortowanie_babelkowe (int tab2[], int s)
 
{
    int k;
    for(int i = 0; i < s; i++ )
    {
        for(k = s;k>=0-1;k-- )
        {
            if( tab2[k]>tab2[k+1])
                 swap(tab2[k],tab2[k+1]);
        }
    }
}
int main()
{
    int s = 100; //size
    int tab1[s], tab2[s];
    cout << "Compare sorting algorythms effiency!" << endl << "Press ENTER to continue." << endl;
    cin.get();
 
        //dwie tablice z randomowymi liczbami
        srand((unsigned)time(0));
        for(int i=0; i<s; i++)
            {
            tab1[i] = (rand()%s)+1;
            tab2[i]=tab1[i];
            }
        //sortowanie przez wybor
        sortowanie_wybor(tab2,s);
        //kopiowanie tablicy
        TabMirror(tab1,tab2,s);
        //sortowanie babelkowe
        sortowanie_babelkowe(tab2,s);
        //kopiowanie tablicy
        TabMirror(tab1,tab2,s);
        //sortowanie szybkie
        quicksort(tab2,0,s);
        //kopiowanie tablicy
        TabMirror(tab1,tab2,s);
        //sortowanie przez wstawianie
        sortowanie_wstawianie(tab2,s);
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxjdGltZT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIFRhYk1pcnJvcihpbnQgdGFiMVtdLCBpbnQgdGFiMltdLCBpbnQgcykgLy9rb3Bpb3dhbmllIHogdGFiMSBkbyB0YWIyCnsKCWZvciAoaW50IGkgPSAwOyBpIDwgczsgKytpKQoJewoJCXRhYjJbaV0gPSB0YWIxW2ldOwoJfQp9Cgp2b2lkIGRpc3BsYXkoaW50IHRhYjFbXSwgaW50IHRhYjJbXSwgaW50IHMpIC8vd3lzd2lldGxhbmllIHRhYmxpYwp7Cglmb3IgKGludCBpID0gMDsgaSA8IHM7ICsraSkKCXsKCQljb3V0IDw8ICJ0YWJsaWNhMTogIiA8PCB0YWIxW2ldIDw8ICJcdFx0dGFibGljYTI6ICIgPDwgdGFiMltpXSA8PCBlbmRsOwoJfQp9Cgp2b2lkIHF1aWNrc29ydChpbnQgdGFiW10sIGludCBsZWZ0LCBpbnQgcmlnaHQpewogICAgIGludCBpPWxlZnQ7CiAgICAgaW50IGo9cmlnaHQ7CiAgICAgaW50IHg9dGFiWyhsZWZ0K3JpZ2h0KT4+MV07CiAgICAgZG97CiAgICAgICAgIHdoaWxlKHRhYltpXTx4KSBpKys7CiAgICAgICAgIHdoaWxlKHRhYltqXT54KSBqLS07CiAgICAgICAgIGlmKGk8PWopewogICAgICAgICAgICAgaW50IHRlbXA9dGFiW2ldOwogICAgICAgICAgICAgdGFiW2ldPXRhYltqXTsKICAgICAgICAgICAgIHRhYltqXT10ZW1wOwogICAgICAgICAgICAgaSsrOwogICAgICAgICAgICAgai0tOwogICAgICAgICB9CiAgICAgfXdoaWxlKGk8PWopOwogICAgIGlmKGxlZnQ8aikgcXVpY2tzb3J0KHRhYixsZWZ0LGopOwogICAgIGlmKHJpZ2h0PmkpIHF1aWNrc29ydCh0YWIsaSxyaWdodCk7Cn0KCnZvaWQgc29ydG93YW5pZV93c3Rhd2lhbmllKCBpbnQgdGFiMltdLCBpbnQgcyApCnsKICAgIGludCB0ZW1wLCBrOwoKICAgIGZvciggaW50IGkgPSAxOyBpIDwgczsgaSsrICkKICAgIHsKICAgICAgICB0ZW1wID0gdGFiMlsgaSBdOwoKICAgICAgICBmb3IoIGsgPSBpIC0gMTsgayA+PSAwICYmIHRhYjJbIGsgXSA+IHRlbXA7IGstLSApCiAgICAgICAgICAgICB0YWIyWyBrICsgMSBdID0gdGFiMlsgayBdOwoKICAgICAgICB0YWIyWyBrICsgMSBdID0gdGVtcDsKICAgIH0KfQoKdm9pZCBzb3J0b3dhbmllX3d5Ym9yKGludCB0YWIyW10sIGludCBzKQp7CiAgICAgICAgaW50IGosazsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzOyBpKysgKQogICAgewogICAgICAgIGsgPSBpOwogICAgICAgIGZvciggaW50IGogPSBpICsgMTsgaiA8IHM7IGorKyApCiAgICAgICAgaWYoIHRhYjJbIGogXSA8IHRhYjJbIGsgXSApCiAgICAgICAgayA9IGo7CiAgICAgICAgc3dhcCggdGFiMlsgayBdLCB0YWIyWyBpIF0gKTsKICAgIH0KfQoKdm9pZCBzb3J0b3dhbmllX2JhYmVsa293ZSAoaW50IHRhYjJbXSwgaW50IHMpCgp7CiAgICBpbnQgazsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzOyBpKysgKQogICAgewogICAgICAgIGZvcihrID0gcztrPj0wLTE7ay0tICkKICAgICAgICB7CiAgICAgICAgICAgIGlmKCB0YWIyW2tdPnRhYjJbaysxXSkKICAgICAgICAgICAgICAgICBzd2FwKHRhYjJba10sdGFiMltrKzFdKTsKICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgcyA9IDEwMDsgLy9zaXplCiAgICBpbnQgdGFiMVtzXSwgdGFiMltzXTsKICAgIGNvdXQgPDwgIkNvbXBhcmUgc29ydGluZyBhbGdvcnl0aG1zIGVmZmllbmN5ISIgPDwgZW5kbCA8PCAiUHJlc3MgRU5URVIgdG8gY29udGludWUuIiA8PCBlbmRsOwogICAgY2luLmdldCgpOwoKICAgICAgICAvL2R3aWUgdGFibGljZSB6IHJhbmRvbW93eW1pIGxpY3piYW1pCiAgICAgICAgc3JhbmQoKHVuc2lnbmVkKXRpbWUoMCkpOwogICAgICAgIGZvcihpbnQgaT0wOyBpPHM7IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICB0YWIxW2ldID0gKHJhbmQoKSVzKSsxOwogICAgICAgICAgICB0YWIyW2ldPXRhYjFbaV07CiAgICAgICAgICAgIH0KICAgICAgICAvL3NvcnRvd2FuaWUgcHJ6ZXogd3lib3IKICAgICAgICBzb3J0b3dhbmllX3d5Ym9yKHRhYjIscyk7CiAgICAgICAgLy9rb3Bpb3dhbmllIHRhYmxpY3kKICAgICAgICBUYWJNaXJyb3IodGFiMSx0YWIyLHMpOwogICAgICAgIC8vc29ydG93YW5pZSBiYWJlbGtvd2UKICAgICAgICBzb3J0b3dhbmllX2JhYmVsa293ZSh0YWIyLHMpOwogICAgICAgIC8va29waW93YW5pZSB0YWJsaWN5CiAgICAgICAgVGFiTWlycm9yKHRhYjEsdGFiMixzKTsKICAgICAgICAvL3NvcnRvd2FuaWUgc3p5YmtpZQogICAgICAgIHF1aWNrc29ydCh0YWIyLDAscyk7CiAgICAgICAgLy9rb3Bpb3dhbmllIHRhYmxpY3kKICAgICAgICBUYWJNaXJyb3IodGFiMSx0YWIyLHMpOwogICAgICAgIC8vc29ydG93YW5pZSBwcnpleiB3c3Rhd2lhbmllCiAgICAgICAgc29ydG93YW5pZV93c3Rhd2lhbmllKHRhYjIscyk7CiAgICByZXR1cm4gMDsKfQ==