rendered paste body#include <iostream>
#include <ctime>
#include <windows.h>
using namespace std;
inline void swap(int &a, int &b) {
int t ;
t=a;
a=b;
b=t;
}
int wybieranie(int tab[], int rozmiar, long int &porownan, long int &zamiany, int odwrot){
int temp;
int max, mediana;
for(int i=1;i<rozmiar;i++) {
max=i;
for(int j=i+1;j<rozmiar;j++) {
if(odwrot==1) {if(tab[max]>tab[j]) max=j;}
else {if(tab[max]>tab[j]) max=j;}
porownan++;
}
if(max!=i) {swap(tab[i],tab[max]); zamiany++;} ;
if(i == (rozmiar / 2)) mediana=tab[i];
};
return mediana ;
};
int wstawianie(int a[], int rozmiar, long int &porownan, long int &zamiany, int odwrot) {
int t, j , mediana;
for(int i = 1; i < rozmiar - 1; i++)
{
t = i;
for (j = i + 1; j < rozmiar; j++){
if(odwrot==1) {if (a[j] > a[t]) {t = j;}}
else { if (a[j] < a[t]) {t = j;}}
porownan++;
}
swap(a[t],a[i]); zamiany++;
if(i == (rozmiar / 2)) mediana = a[i] ;
}
return mediana ;
}
int babelki(int a[], int rozmiar, long int &porownan, long int &zamiany, int odwrot) {
int temp, mediana ;
for(int i=1;i<rozmiar;i++)
{
for(int j=i+1;j<rozmiar;j++) {
if(odwrot==1) {if(a[i] < a[j]) {swap(a[i],a[j]); zamiany++;};}
else {if(a[i]> a[j]) {swap(a[i],a[j]); zamiany++;};}
porownan++;
}
if(i == (mediana / 2)) mediana = a[i] ;
}
return mediana ;
};
void quicksort(int a[], int lewe, int prawe, long int &porownan, long int &zamiany, int odwrot, int rozmiar) {
int mediana ;
if(lewe < prawe ) {
int m=lewe ;
for(int i=lewe+1;i<=prawe;i++)
{
if(a[i]<a[lewe])
{
swap(a[++m],a[i]);
zamiany++;
}
porownan++;
}
swap(a[lewe],a[m]);
if(m == (rozmiar / 2)) cout << "\nMediana:" << a[m] << endl ;
zamiany++;
quicksort(a,lewe,m-1,porownan,zamiany,odwrot,rozmiar);
quicksort(a,m+1,prawe,porownan,zamiany,odwrot,rozmiar);
}
} ;
int kopcowanie(int d[], int N, long int &porownan, long int &zamiany, int odwrot) {
int i, j,m,k,x, mediana;
for(i = 2; i <= N; i++)
{
j = i; k = j / 2;
x = d[i];
while((k > 0) && (d[k] < x))
{
porownan++;
d[j] = d[k];
j = k; k = j / 2;
}
d[j] = x;
zamiany++;
}
// Rozbieramy kopiec
for(i = N; i > 0; i--)
{
swap(d[1], d[i]);
j = 1; k = 2;
while(k < i)
{
porownan+=2;
if((k + 1 < i) && (d[k + 1] > d[k]))
{m = k + 1;}
else
m = k;
if(d[m] <= d[j]) break;
swap(d[j], d[m]); zamiany++;
j = m; k = j + j;
}
if(i == (N / 2) ) mediana = d[i] ;
}
return mediana ;
}
void wypisz(int t[],int rozmiar) {
// system("cls");
cout << "\n\n\n\tTablica:\n\t\t" ;
for(int i=1;i<rozmiar;i++) cout << t[i] << ", " ;
cout << "\n" <<endl ;
};
void kopiuj(int a[],int b[],int rozmiar) { //pierwsza do drugiej
for(int i=0;i<rozmiar;i++)
b[i]=a[i];
};
long double getTime() {
LARGE_INTEGER pc, freq;
pc.QuadPart = 0;
freq.QuadPart = 0;
QueryPerformanceCounter(&pc);
QueryPerformanceFrequency(&freq);
if(freq.QuadPart == 0)
return -1;
return (long double)pc.QuadPart/(long double)freq.QuadPart;
} ;
void generuj(int t[],int rozmiar) {
for(int i=1;i<rozmiar;i++) t[i]=(int) rand() % 20 +1;
}
int main()
{
srand((unsigned)time(NULL));
int rozmiar = 20;
int tablica[rozmiar];
int pamiec[rozmiar];
int dd;
int mediana ;
long int licznik ;
long double czas1 , czas2 ;
long double roznica ;
long int zamian ;
int kolej=0;
generuj(tablica,rozmiar);
// wypisz(tablica,rozmiar);
do {
system ("cls");
cout << "\tMenu:" << endl;
cout << "\t\t1 - losuj tablice" << endl;
cout << "\t\t2 - wypisz tablice" << endl;
cout << "\t\t3 - sortowanie przez wstawianie" << endl;
cout << "\t\t4 - sortowanie przez wybor" << endl;
cout << "\t\t5 - sortowanie babelkowe" << endl;
cout << "\t\t6 - sortowanie przez kopcowanie" << endl;
cout << "\t\t7 - sortowanie metoda Quick sort" << endl;
cout << "\t\t8 - zapamietaj tablice" << endl;
cout << "\t\t11 - zamien kierunek sortowania" << endl;
cout << "\t\t9 - przywroc zapamietana" << endl;
cin >> dd ;
switch(dd) {
case 1:
generuj(tablica,rozmiar);
break;
case 2:
system("cls");
wypisz(tablica,rozmiar);
system("Pause");
break;
case 3:
system("cls");
licznik = 0;
zamian = 0 ;
cout << "Przed: ";wypisz(tablica,rozmiar);
czas1=getTime() ; // za czas1 zostanie wstawiony czas w milisekundach od momentu wlaczenia programu
// tutaj wstawic algorytm
mediana=wstawianie(tablica,rozmiar, licznik, zamian, kolej);
czas2=getTime() - czas1;
cout << "Po: ";wypisz(tablica,rozmiar);
cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << ", mediana: " << mediana <<endl ;
system("Pause");
break;
case 4:
system("cls");
licznik = 0;
zamian = 0 ;
cout << "Przed: ";wypisz(tablica,rozmiar);
czas1=getTime() ;
mediana=wybieranie(tablica,rozmiar, licznik, zamian, kolej);
czas2=getTime() - czas1;
cout << "Po: ";wypisz(tablica,rozmiar);
cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << " mediana: " << mediana << endl ;
system("Pause");
break;
case 5:
system("cls");
cout << "Przed: ";wypisz(tablica,rozmiar);
licznik = 0;
zamian = 0 ;
czas1=getTime() ;
mediana=babelki(tablica,rozmiar, licznik, zamian, kolej);
czas2=getTime() - czas1;
roznica=czas2-czas1;
cout << "Po: ";wypisz(tablica,rozmiar);
cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << ", mediana: "<< mediana <<endl ;
system("Pause");
break;
case 6:
system("cls");
cout << "Przed: ";wypisz(tablica,rozmiar);
licznik = 0;
zamian = 0 ;
czas1=getTime() ;
mediana=kopcowanie(tablica,rozmiar-1, licznik, zamian, kolej);
czas2=getTime() - czas1;
cout << "Po: ";wypisz(tablica,rozmiar);
cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << ", mediana: " << mediana << endl ;
system("Pause");
break;
case 7:
system("cls");
cout << "Przed: ";wypisz(tablica,rozmiar);
licznik = 0;
zamian = 0 ;
czas1=getTime(); //=getTime() ;
quicksort(tablica,1,rozmiar, licznik, zamian, kolej,rozmiar);
czas2=getTime() ; //=getTime() - czas1;
roznica = czas2 - czas1;
cout << "Po: ";wypisz(tablica,rozmiar);
cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << roznica << endl ;
system("Pause");
break;
case 8:
kopiuj(tablica,pamiec,rozmiar);
cout << "Skopiowane";
system("Pause");
break ;
case 11:
kolej=abs(kolej-1);
break;
case 9:
kopiuj(pamiec,tablica,rozmiar);
cout << "przywrocone" << endl;
system("Pause");
break;
default:
break;
}
}
while(dd!=0);
return 0 ;
}