Forum
Użytkownicy
Kalendarz
Chat
Dodatki SourceMod
Temat jest zamknięty
Dlaczego te algorytmy są lepsze? Oto wykres zależności czasu trwania obliczeń od ilości elementów:
Wykres zależności czasu trwania obliczeń od ilości elementów z pominięciem sortowania bąbelkowego:
Sortowanie szybkie:
//------------------------------------------------------------------------------
//------------SORTOWANIE SZYBKIE -----------------------------------------------
//------------------------------------------------------------------------------
/**
Wywoływana rekurencyjnie funkcja szybkiego sortowania
tab - sortowana tablica
index_pierwszego elementu :)
index_ostatniego elementu :)
*/
void quick_alg(int index_pierwszego, int index_ostatniego, int* tab){
int i, i2, tmp, srodek;
i = (index_pierwszego + index_ostatniego) / 2;
srodek = tab[i];
tab[i] = tab[index_ostatniego];
for( i2 = index_pierwszego, i = index_pierwszego ; i < index_ostatniego; i++){
if( tab[i] < srodek){
tmp = tab[i];
tab[i] = tab[i2];
tab[i2] = tmp;
i2++;
}
}
tab[index_ostatniego] = tab[i2];
tab[i2] = srodek;
if( (i2 + 1) < index_ostatniego){
quick_alg(i2 + 1, index_ostatniego, tab); //rekurencyjne wykonanie quicksorta dla prawej partycji
}
if( index_pierwszego < (i2 - 1)){
quick_alg(index_pierwszego, (i2 - 1), tab); //rekurencyjne wykonanie quicksorta dla lewej partycji
}
}
/**
Funkcja zwraca wartość double, jest to czas wykonania operacji
Argument n jest ilością elementów w tablicy
Argument przyp jest przypadkiem ulozenia elementow 0-posortowane 1-losowo 2-posortowane wspak
*/
double quick(int n, short int przyp){
int *tab; // tablica na której będzie wykonywany algorytm
clock_t time_przed; // pomiar czasu prz sortowaniem
clock_t time_po; // pomiar czasu po sortowaniu
double time_roznica; // różnica czasu przed i po sortowaniu zwracana przez funkcję difftime
tab = new int [n];
wypelnij(tab, przyp, n, 0); // wypełnianie tablicy
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
time_przed = pobierz_czas(); // pomiar czasu przed sortowaniem
quick_alg(0,n-1, tab); // quicksort
time_po = pobierz_czas(); // pomiar czasu po sortowaniu
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
delete [] tab;
time_roznica = difft(time_po, time_przed);
cout << time_roznica;
return time_roznica;
}
Sortowanie przez scalanie:
//------------------------------------------------------------------------------
//------------SORTOWANIE PRZEZ SCALANIE ----------------------------------------
//------------------------------------------------------------------------------
/**
Wywoływana rekurencyjnie funkcja sortowania przez scalanie
tab - sortowana tablica
pom - tablica pomocnicza
index_pierwszego elementu :)
index_ostatniego elementu :)
*/
void scalanie_alg(int index_pierwszego, int index_ostatniego, int* tab, int* pom){
int podzial;
int j,k,i;
podzial = (1 + index_pierwszego + index_ostatniego) / 2; // przygotowanie podzialu zbioru na 2 czesci
if( index_ostatniego - podzial > 0){ // sortowanie rekurencyjne podzbioru drugiego
scalanie_alg(podzial, index_ostatniego, tab, pom);
}
if( podzial - index_pierwszego > 1){ // sortowanie rekurencyjne podzbioru pierwszego
scalanie_alg(index_pierwszego, podzial - 1, tab, pom);
}
j = index_pierwszego;
k = podzial;
for( i = index_pierwszego; i <= index_ostatniego; i++){ // scalanie
if(((index_ostatniego >= k) && (tab[k] < tab[j])) || ( j == podzial)){ // jezeli index pierwszego elementu z pierwszego zbioru jest rowny podzial tzn ze jestesmy
pom[i] = tab[k]; // na najnizszym poziomie rekurencji
k++;
}else{
pom[i] = tab[j];
j++;
}
}
for( i = index_pierwszego; i <= index_ostatniego; i++){ // przepisywanie z tablicy pomocniczej do tab juz po scaleniu
tab[i] = pom[i];
}
}
/**
Funkcja zwraca wartość double, jest to czas wykonania operacji
Argument n jest ilością elementów w tablicy
Argument przyp jest przypadkiem ulozenia elementow 0-posortowane 1-losowo 2-posortowane wspak
*/
double scalanie(int n, short int przyp){
int *tab; // tablica na której będzie wykonywany algorytm
clock_t time_przed; // pomiar czasu prz sortowaniem
clock_t time_po; // pomiar czasu po sortowaniu
double time_roznica; // różnica czasu przed i po sortowaniu zwracana przez funkcję difftime
int *pom; // tablica pomocnicza
tab = new int [n];
pom = new int [n];
wypelnij(tab, przyp, n, 0); // wypełnianie tablicy
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
time_przed = pobierz_czas(); // pomiar czasu przed sortowaniem
scalanie_alg(0,n-1, tab, pom);
time_po = pobierz_czas(); // pomiar czasu po sortowaniu
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
delete [] tab;
time_roznica = difft(time_po, time_przed);
cout << time_roznica;
return time_roznica;
}
Sortowanie przez kopcowanie:
//------------------------------------------------------------------------------
//------------SORTOWANIE PRZEZ KOPCOWANIE --------------------------------------
//------------------------------------------------------------------------------
/**
Funkcja zwraca wartość double, jest to czas wykonania operacji
Argument n jest ilością elementów w tablicy
Argument przyp jest przypadkiem ulozenia elementow 0-posortowane 1-losowo 2-posortowane wspak
*/
double kopcowanie(int n, short int przyp){
int *tab; // tablica na której będzie wykonywany algorytm
clock_t time_przed; // pomiar czasu prz sortowaniem
clock_t time_po; // pomiar czasu po sortowaniu
double time_roznica; // różnica czasu przed i po sortowaniu zwracana przez funkcję difftime
int a,b,tmp2,tmp;
tab = new int [n];
wypelnij(tab, przyp, n, 0); // wypełnianie tablicy
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
time_przed = pobierz_czas(); // pomiar czasu przed sortowaniem
// Kopcowanie
for( int i=2; i<=(n-1);i++){
a=i;
tmp=tab[i];
b=a/2;
while( (tmp>tab[b]) && (b>0)){
tab[a]=tab[b];
a=b;
b=a/2;
}
tab[a]=tmp;
}
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
//Odkopcowanie
for( int i = (n-1); i>1; i--){
tmp2 = tab[1];
tab[1] = tab[i];
tab[i] = tmp2;
a=1;
b=2;
while( b<i){
if( (b+1<i) &&(tab[b]<tab[b+1]) ){
tmp = 1 + b;
}
else{
tmp = b;
}
if( !( tab[tmp] > tab[a] ) ){
break;
}
tmp2 = tab[a];
tab[a] = tab[tmp];
tab[tmp] = tmp2;
a=tmp;
b=2*a;
}
}
time_po = pobierz_czas(); // pomiar czasu po sortowaniu
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
delete [] tab;
time_roznica = difft(time_po, time_przed);
cout << time_roznica;
return time_roznica;
}
Sortowanie Shell'a:
//------------------------------------------------------------------------------
//------------SORTOWANIE SHELL -------------------------------------------------
//------------------------------------------------------------------------------
/**
Funkcja zwraca wartość double, jest to czas wykonania operacji
Argument n jest ilością elementów w tablicy
Argument przyp jest przypadkiem ulozenia elementow 0-posortowane 1-losowo 2-posortowane wspak
*/
double shell(int n, short int przyp, int param){
int *tab; // tablica na której będzie wykonywany algorytm
clock_t time_przed; // pomiar czasu prz sortowaniem
clock_t time_po; // pomiar czasu po sortowaniu
double time_roznica; // różnica czasu przed i po sortowaniu zwracana przez funkcję difftime
int h,i,licz,a; // h -odległość
tab = new int [n];
wypelnij(tab, przyp, n, 0); // wypełnianie tablicy
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
time_przed = pobierz_czas(); // pomiar czasu przed sortowaniem
h = 1; //ustawianie parametru h
while( h < n){
h=1 + param*h;
}
h = h/9;
if(!h) h++; // istotne jedynie dla bardzo małych tablic
while( h){
for( licz = n - 1 - h; !(licz < 0); licz--){
i = licz + h;
a = tab[licz];
for( ;(n > i) && (tab[i] < a);){ //sortowanie przez wstawianie
tab[i - h] = tab[i];
i += h;
}
tab[i - h] = a;
}
h = h/3;
}
time_po = pobierz_czas(); // pomiar czasu po sortowaniu
wypisz(tab, n); // ewentualne wyswietlanie elementow tablicy dla sprawdzenia poprawnosci sortowania
delete [] tab;
time_roznica = difft(time_po, time_przed);
cout << time_roznica;
return time_roznica;
}
Funkcje pomocnicze:
/*
Pobiera czas metoda zalezna od globalnej flagi
*/
time_t pobierz_czas(){
if( fczas==1){
return clock ();
}
else{
return time(NULL);
}
}
/*
Oblicza czas wykonywania sie algorytmu dla metod clock() i time()
*/
double difft(time_t time_po, time_t time_przed){
if( fczas==1){
return (difftime(time_po, time_przed) / CLOCKS_PER_SEC);
}
else{
return difftime(time_po, time_przed);
}
}
//---------------------------------------
//------------WYPELNIANIE TABLICY--------
//---------------------------------------
void wypelnij(int* tab,short int przyp, int n, int zakres){
switch(przyp){
// posortowane
case 0:
for( int i=0; i<n;i++){
if(zakres!=0){
tab[i]= i%zakres;
}
else{
tab[i]= i;
}
}
break;
// losowo
case 1:
for( int i=0; i<n;i++){
if(zakres!=0){
tab[i]= rand()%zakres;
}
else{
tab[i]= rand();
}
}
break;
// wspak
case 2:
for( int i=0; i<n;i++){
if(zakres!=0){
tab[i]= (n-i)%zakres;
}
else{
tab[i]= (n-i);
}
}
break;
}
}
//----------------------------------------------------
//------------WYPISYWANIE POSORTOWANEJ TABLICY--------
//----------------------------------------------------
/**
Funkcja wypisujaca elementy posortowanej tablicy, spam do testowania poprawnosci sortowania
n -liczba elementow
tab - nasza tablica
*/
void wypisz(int* tab, int n){
if( wyswietl==1){
cout << endl << endl <<endl;
for( int i=0;i<n;i++){
cout<<tab[i];
if( (i%8)==0){
cout << "\n";
}
else{
cout << "\t";
}
}
cout << "czas: ";
}
}
