AMXX.pl: Support AMX Mod X i SourceMod

Widzę, że powstał temat na temat sortowania bąbelkowego. Jest to prosty, ale niestety wyjątkowo mało wydajny algorytm dlatego zaprezentuję tutaj alternatywne, o wiele szybsze metody. Algorytmy zostały umieszczone w osobnych funkcjach, do każdej z nich przekazywane są takie parametry jak ilość elementów oraz sposób ułożenia elementów sortowanych. Są tam też funkcje wypełniające tablice, wypisujące je na ekranie oraz mierzące czas (gdyż wszystko pochodzi z mojego programu do pomiaru wydajności tych algorytmów). Uwaga! nie jest to czysty program, są to funkcje gotowego programu z pozostałościami po jego elementach.


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: ";                
        }
     }
     

Bardzo fajne, czuję że kiedyś może mi się przydać

poprostu sortowanie babelkowe jest metoda o slabej zlozonosci obliczeniowej.
Fajne porownanie

O(n^2) i O(n log(n)) to spora różnica choć oczywiście przy małej ilości elementów niezauważalna. Kiedyś jednak zdarzyło mi się sortować większe tablice, w większości przypadków nie ma to dużego znaczenia, ale czasami kolosalne.

Kajt, na wykresach masz literówkę: "sella"
Ale prof Janiak pewnie i tak nie zauważył

Dobrze przedstawiłeś poszczególne rodzaje sortowań na wykresie, lecz strasznie utrudniasz sobie życie tymi kodami C++'owymi. Dobrym wyjaśnieniem tego będzie kod od algorytmu QiuckSort, który u Ciebie zajmuje około 100 linijek i jest strasznie chaotyczny. Są takie biblioteki jak <windows.h>, które zdecydowanie ułatwiają życie programistom. Dla porównania pokaże Twój i mój kod.

/////////////////TWÓJ/////////////////

//------------------------------------------------------------------------------
//------------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;
     }

/////////////////MÓJ/////////////////

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

using namespace std;

void qsort(int *tab, int left, int right)
{
 if (left < right)
 {     
 int m=left;
 for (int i=left;i<=right;i++)
 if (tab[i]<tab[left])
    swap(tab[++m],tab[i]);
    swap(tab[left],tab[m]);
   qsort(tab,left,m-1);
   qsort(tab,m+1,right);    
 }
}  
int main()
{
    int n;
    cout<<"\nIle liczb chcesz posortowac?\n\n";
    cin>>n;
    int tabl[n];
    float start = GetTickCount(); 
    cout <<endl << "Wlaczam pomiar czasu dzialania programu!" << endl;
    for (int i=0;i<n;i++)
    {
        cout<<"\nPodaj " << i+1 <<" liczbe: ";
        cin >> tabl[i];
    }
    cout << "\n\n"; qsort(tabl,0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<< tabl[i]<<" ";
    }    
    float stop = GetTickCount(); 
    cout <<endl <<endl << "Koncze pomiar czasu!" << endl << endl;
    cout << "Czas dzialania programu to: " << (stop - start) / 100 <<" s" << endl;
}

Choć obydwa są tak samo wydajne, to mój program jest o wiele mniej chaotyczny i oszczędza sporo czasu w porównaniu do Twojego.
Tyle z mojej strony.
Użytkownik MaDaFaKa edytował ten post 29.11.2010 21:00

czyżby nie można było usunąć swojego postu?
Użytkownik kajt edytował ten post 19.12.2010 19:30

bezużyteczne kody podajecie, jak chcecie by ktoś z tego mógł skorzystać to napisz klase qsort

Sz. P Jacku, Adaś tego nie czytał

Sz. P Jacku, Adaś tego nie czytał

To wiadomo Tak przecież żartowałem