Skocz do zawartości

  • Zaloguj korzystając z Facebooka Zaloguj korzystając z Twittera Zaloguj przez Steam Zaloguj poprzez Google      Logowanie »   
  • Rejestracja

Witamy w Nieoficjalnym polskim support'cie AMX Mod X

Witamy w Nieoficjalnym polskim support'cie AMX Mod X, jak w większości społeczności internetowych musisz się zarejestrować aby móc odpowiadać lub zakładać nowe tematy, ale nie bój się to jest prosty proces w którym wymagamy minimalnych informacji.

  • Rozpoczynaj nowe tematy i odpowiedaj na inne
  • Zapisz się do tematów i for, aby otrzymywać automatyczne uaktualnienia
  • Dodawaj wydarzenia do kalendarza społecznościowego
  • Stwórz swój własny profil i zdobywaj nowych znajomych
  • Zdobywaj nowe doświadczenia

Dołączona grafika Dołączona grafika

Guest Message by DevFuse
 

Zdjęcie
C++

Wydajniejsze sortowaniasortowanie szybkie, przez scalanie, przez kopsowanie, Shell'a

C++

  • Zamknięty Temat jest zamknięty
9 odpowiedzi w tym temacie

#1 kajt

    Życzliwy

  • Użytkownik

Reputacja: 17
Początkujący

  • Postów:27
  • GG:
  • Lokalizacja:Wrocław
Offline

Napisano 08.07.2010 11:49

*
Popularny

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:
Dołączona grafika

Wykres zależności czasu trwania obliczeń od ilości elementów z pominięciem sortowania bąbelkowego:
Dołączona grafika


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

  • +
  • -
  • 7

Lord Of Destruction Mod 100%

TES Mod 100%
New Lord Of Destruction Mod 100%

 

www.cs-lod.com.pl


#2 Miczu

    Godlike

  • Przyjaciel

Reputacja: 646
Wszechmogący

  • Postów:2862
Offline

Napisano 08.07.2010 12:59

Bardzo fajne, czuję że kiedyś może mi się przydać :>
  • +
  • -
  • 0

#3 G[o]Q

    I'm G[o]Q

  • Przyjaciel

Reputacja: 1339
Godlike

  • Postów:3556
  • Steam:steam
  • Imię:Krzysiek
  • Lokalizacja:C: / program Files / Valve / Cstrike / G[o]Q.dem
Offline

Napisano 08.07.2010 13:46

poprostu sortowanie babelkowe jest metoda o slabej zlozonosci obliczeniowej.
Fajne porownanie :D
  • +
  • -
  • 0
Manual ponad wszystko, konsola ponad manual :D :&

Chcesz wysłać do mnie PW ? użyj nazwy GoQ zamiast G[o]Q
Chcesz Kupić moduł płatności via Pukawka,Tserwery, Gamesol, Zabijaka do mojego sklepu? napisz PW cena to tylko 10 zł/sztuka

GG:6022845 (nie pomagam za free osobom ponizej rangi MoD) :D

#4 kajt

    Życzliwy

  • Autor tematu
  • Użytkownik

Reputacja: 17
Początkujący

  • Postów:27
  • GG:
  • Lokalizacja:Wrocław
Offline

Napisano 08.07.2010 13:49

O(n^2) i O(n log(n)) to spora różnica :D 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.
  • +
  • -
  • 0

Lord Of Destruction Mod 100%

TES Mod 100%
New Lord Of Destruction Mod 100%

 

www.cs-lod.com.pl


#5 JSokol

    Życzliwy

  • Użytkownik

Reputacja: 5
Nowy

  • Postów:31
  • Lokalizacja:JG | Wro
Offline

Napisano 12.10.2010 05:57

Kajt, na wykresach masz literówkę: "sella" :D
Ale prof Janiak pewnie i tak nie zauważył ;)
  • +
  • -
  • 0
Banid.pl - sprawdź z kim grasz! Nie graj z cheaterami!

#6 MaDaFaKa

    Zaawansowany

  • Zbanowany

Reputacja: 59
Pomocny

  • Postów:96
  • Imię:Damian
  • Lokalizacja:Warszawa
Offline

Napisano 29.11.2010 18:23

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


#7 kajt

    Życzliwy

  • Autor tematu
  • Użytkownik

Reputacja: 17
Początkujący

  • Postów:27
  • GG:
  • Lokalizacja:Wrocław
Offline

Napisano 19.12.2010 18:07

czyżby nie można było usunąć swojego postu?

Użytkownik kajt edytował ten post 19.12.2010 19:30

  • +
  • -
  • 0

Lord Of Destruction Mod 100%

TES Mod 100%
New Lord Of Destruction Mod 100%

 

www.cs-lod.com.pl


#8 -PainKiller-

    Wszechobecny

  • Zbanowany

Reputacja: 66
Pomocny

  • Postów:498
  • GG:
  • Steam:steam
  • Imię:Kamil
  • Lokalizacja:Kraków
Offline

Napisano 19.12.2010 22:45

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

#9 kajt

    Życzliwy

  • Autor tematu
  • Użytkownik

Reputacja: 17
Początkujący

  • Postów:27
  • GG:
  • Lokalizacja:Wrocław
Offline

Napisano 16.04.2011 10:48

Sz. P Jacku, Adaś tego nie czytał :D
  • +
  • -
  • 0

Lord Of Destruction Mod 100%

TES Mod 100%
New Lord Of Destruction Mod 100%

 

www.cs-lod.com.pl


#10 JSokol

    Życzliwy

  • Użytkownik

Reputacja: 5
Nowy

  • Postów:31
  • Lokalizacja:JG | Wro
Offline

Napisano 16.04.2011 13:47

Sz. P Jacku, Adaś tego nie czytał :D


To wiadomo ;) Tak przecież żartowałem :D
  • +
  • -
  • 0
Banid.pl - sprawdź z kim grasz! Nie graj z cheaterami!





Również z jednym lub większą ilością słów kluczowych: C++

Użytkownicy przeglądający ten temat: 0

0 użytkowników, 0 gości, 0 anonimowych