BRZO SORTIRANJE(QUICK - SORT ENGL.)
|
Algoritam sortiranja koji se pokazao najbržim. Sastoji se u rekurzivnom ponavljanju razdvajanja elemenata niza oko neke vrednosti koja je usvojena za "srednju". Ovaj element se naziva PIVOT i postoje različit način da se odabere. U ovo tekstu za PIVOT je odabran krajnji element podniza u tekućoj iteraciji. Ako se npr. vrši sortiranje niza u rastućem redosledu, onda se prolaskom kroz niz, s leva na desno vrši razdvajanje tako da posle završetka iteracije na levoj strani od PIVOT-a budu vrednosti koje su manje ili jednake od PIVOT-a, a na desnoj veće. Proces se ponavlja sve dok se ne ispitaju svi elementi do PIVOT-a. Na kraju se PIVOT stavlja na pravo mesto, tj. na mesto posle levo raspoređenih elemenata, onih čije su vrednosti bile manje od PIVOT-a.
Posmatrajmo npr. sledeći nesortiran niz: |
VIDEO: Brzo sortiranje postupak |
Slika 1: Brzo sortiranje. Početni niz
Za PIVOT-a je usvojen element na kraju niza, tj. na poziciji 9, čija je vrednost 14. Narandžastim okvirom je obeležen tekući element niza čija se vrednost poredi sa PIVOT-om. Na slici iznad se vidi stanje u drugom prolazu. Ta vrednost se poredi sa pivotom i ako je manja, vrši se zamena sa elementom uokvirenim isprekidanom crvenom linijom. Crveni okvir pokazuje u stvari prvu sledeću poziciu desno od poslednjeg zamenjenog elementa. Sa leve strane od te pozicije svi elementi moraju biti manji od PIVOTA, u ovom primeru manji od 14.
Dakle, ukoliko je došlo do zamene tekućeg elementa(narandžasto) i elementa(crveno), pozicija za sledeću eventualnu zamenu se pomera za jedno mesto u desno. Ukoliko je tekući element niza veći od pivota nema zamene već se prelazi na ispitivanje sledećeg elementa na desno, tj narandžasti okvir se premešta. U prvom prolazu se poredio broj 25 sa 14, i s obzirom da je veči, nije bilo zamene. U drugom prolazu, koji je prikazan na prethodnoj slici, poredi se broj 13 sa PIVOT-om i s obzirom da je manji izvršiće se zamena broja 13 i 25, tj. brojeva na poziciji 0 i 1(vidi sledeću sliku)
Dakle, ukoliko je došlo do zamene tekućeg elementa(narandžasto) i elementa(crveno), pozicija za sledeću eventualnu zamenu se pomera za jedno mesto u desno. Ukoliko je tekući element niza veći od pivota nema zamene već se prelazi na ispitivanje sledećeg elementa na desno, tj narandžasti okvir se premešta. U prvom prolazu se poredio broj 25 sa 14, i s obzirom da je veči, nije bilo zamene. U drugom prolazu, koji je prikazan na prethodnoj slici, poredi se broj 13 sa PIVOT-om i s obzirom da je manji izvršiće se zamena broja 13 i 25, tj. brojeva na poziciji 0 i 1(vidi sledeću sliku)
Slika 2: Brzo sortiranje(Quick-Sort). Zamena elemenata
Element 13 se posle toga nalazi na početku niza a sledeće pozicija za eventualnu zamenu je desno na poziciji br. 1. U sledećem prolazu poredi se broj 10 sa 14(PIVOT-om), a zatim i -2. Obe ove vrednosti su manje od 14 pa će se i one zameniti i naći sa leve strane od sledeće pozicije za zamenu koja se sada premešta na poziciju 3(Crveni pravougaonik na slici 3). Sledeći član niza, 16 je veći od 14 pa se samo prelazi na sledeći element na poziciji 5, vidi sliku 3:
Slika 3: Brzo sortiranje(Quick-Sort). Premeštanje pozicije
Na kraju posmatrane iteracije, kada se uporede svi elementi niza levo od PIVOT-a, PIVOT se stavlja na odgovarajuće mesto desno od svih premeštenih članova na levoj strani. Ta pozicija je ona obeležena crvenim pravougaonikom, vidi sliku 4:
Slika 4: Brzo sortiranje(Quick-Sort). Premeštanje PIVOT-a
Kod koji vrši gore prikazana razdvajanja je prikazan pomoću funkcije prikazane ispod:
/*Metoda koja vrši razdvajanje elemenata niza. Niz je metodi prosleđen kao parametar a[ ].
Takođe se prosleđuju krajnja leva pozicija posmatranog niza(podniza) "l" i krajnja desna pozicija "d"*/
void deljenjeNiza(int a[ ], int l,int d)
{
Takođe se prosleđuju krajnja leva pozicija posmatranog niza(podniza) "l" i krajnja desna pozicija "d"*/
void deljenjeNiza(int a[ ], int l,int d)
{
int p = a[ d ];// Pivot je element na krajnjoj poziciji
int i, j;
i=l-1;
for(j=l; j<=d-1; j++)
{
}int i, j;
i=l-1;
for(j=l; j<=d-1; j++)
{
if(a[j] < p)
{
}{
if(i != j)
{
}{
zamena(&a[i+1],&a[j]);
i++;
}i++;
Pozicija koja je na slici predstavljena crvenim pravougaonikom, tj. pozicija elementa poslednjeg premeštenog, je u kodu predstavljena slovom "i", dok je pozicija tekućeg elementa niza koji se poredi sa PIVOT-om, označena sa "j". Dakle, crveni pravougaonik na slikama je na poziciji "i+1".
Prolazi kroz sve elemente niza od početne "l" do krajnje "d", pozicije u tekućoj iteraciji. Ovo je predstavljeno for petljom. Vrši se dalje provera da li je tekući element veći od pivota, pomoću if naredbe unutar for petlje. Ukoliko jeste vrši se zamena i pomera pozicija "i" za jedno mesto, a ukoliko nije samo se premešta se pozicija "j" za jedno mesto da bi se uzeo sledeći element niza za razmatranje.
Na kraju se premešta PIVOT na poziciju "i+1" i ta vrednost je povratna iz funkcije.
Prolazi kroz sve elemente niza od početne "l" do krajnje "d", pozicije u tekućoj iteraciji. Ovo je predstavljeno for petljom. Vrši se dalje provera da li je tekući element veći od pivota, pomoću if naredbe unutar for petlje. Ukoliko jeste vrši se zamena i pomera pozicija "i" za jedno mesto, a ukoliko nije samo se premešta se pozicija "j" za jedno mesto da bi se uzeo sledeći element niza za razmatranje.
Na kraju se premešta PIVOT na poziciju "i+1" i ta vrednost je povratna iz funkcije.
|
Po izlasku iz iteracije pivot se nalazi na poziciji
pi= i+1 i deli niz na levi (l, pi) i desni deo niza (pi+1, d). Treba uočiti da su sa leve strane svi elementi manji od pivota, a sa desne veći, vidi sliku 5. Postupak se dalje ponavlja pozivom iste funkcije "deljenjeNiza( )" jednom sa poslatim vrednostima (l, pi), a drugi put sa parametrima početne i krajnje pozicije (pi+1, d). |
Slika 5: Brzo sortiranje(Quick-Sort). Deljenje niza pomoću PIVOT-a
|
Funkcija koja se rekurzivno poziva:
/*Metoda koja pokreće rekurzivno sortiranje početnog niza. */
void brzoSortiranje(int a[ ], int l,int d)
{
brzoSortiranje( a,l,pi-1);
brzoSortiranje( a,pi+1,d);
}
void brzoSortiranje(int a[ ], int l,int d)
{
if(l >= d)
{
int pi=deljenjeNiza(a,l,d);{
return
}brzoSortiranje( a,l,pi-1);
brzoSortiranje( a,pi+1,d);
}
|
Rekurzija se završava kada se početna i krajnja pozicija niza koji se ispituje ne poklope(uslov l>= d). U pokazanom primeru završna iteracija levog dela niza(slika 5) se završava kada veličina za sortiranje bude jednaka 1, kao što je prikazano na slici 6.
Slika 6: Brzo sortiranje(Quick-Sort). Završna iteracija levog dela niza
|
Slika 7: Brzo sortiranje(Quick-Sort). Završna iteracija desnog dela niza
Na završetaku sortiranja desnog dela sortiran je i kompletan niz. U nastavku je prikazana glavna metoda, kao i pomoćne metoda za zamenu kao i za štampanje elemenata niza
|
#include < stdio.h >
void stampajNiz(int a[], int n){
void zamena(int *a, int* b){
int main()
{
void stampajNiz(int a[], int n){
for(int i = 0; i < n; i++)
}
printf("%d ",a[ i ]);
printf("\n");void zamena(int *a, int* b){
int temp=(*a);
(*a)=(*b);
(*b)=temp;
}(*a)=(*b);
(*b)=temp;
int main()
{
int n;
int niz[ ]=24, 18, 38,43,14,40,1,54};
n = sizeof(niz) / sizeof(niz[ 0 ]);
brzoSortiranje( niz,0,n-1);;
stampajNiz(niz, n);
return 0;
}int niz[ ]=24, 18, 38,43,14,40,1,54};
n = sizeof(niz) / sizeof(niz[ 0 ]);
brzoSortiranje( niz,0,n-1);;
stampajNiz(niz, n);
return 0;
Kompletan kod je prikazan ispod sa dodatim "printf" komandama za otklanjanje grešaka:
#include < stdio.h >
#include < stdlib.h >
/*Metoda koji štampa niz*/
void stampajNiz(int a[ ], int n){
/*Metoda koja menja vrednosti dva elementa nekog niza*/
void zamena(int *a, int* b){
/*Metoda koja razdvaja elemente niza. Niz se prosleđuje metodu kao parametar a [] . The first left position of the observed array(subarray) "l" and the last right position "r" also are passed.*/
void deljenjeNiza(int a[ ], int l,int r)
{
/* Metoda koja pokreće rekurzivno sortiranje početnog niza. */
void brzoSortiranje(int a[ ], int l,int d,int n)
{
int main()
{
#include < stdlib.h >
/*Metoda koji štampa niz*/
void stampajNiz(int a[ ], int n){
for(int i = 0; i < n; i++)
}
printf("%d ",a[ i ]);
printf("\n");/*Metoda koja menja vrednosti dva elementa nekog niza*/
void zamena(int *a, int* b){
int temp=(*a);
(*a)=(*b);
(*b)=temp;
}(*a)=(*b);
(*b)=temp;
/*Metoda koja razdvaja elemente niza. Niz se prosleđuje metodu kao parametar a [] . The first left position of the observed array(subarray) "l" and the last right position "r" also are passed.*/
void deljenjeNiza(int a[ ], int l,int r)
{
int p = a[ r ];// Pivot is element at last position
int i, j;
i=l-1;
for(j=l; j<=r-1; j++)
{
}int i, j;
i=l-1;
for(j=l; j<=r-1; j++)
{
if(a[j] < p)
{
}{
if(i != j)
{
else
{
}{
zamena(&a[i+1],&a[j]);
printf("TRUE,i=%d, j=%d; i++, j++, zamena %3d sa %3d\n",i,(j+1),a[i],a[j]);
i++;
}printf("TRUE,i=%d, j=%d; i++, j++, zamena %3d sa %3d\n",i,(j+1),a[i],a[j]);
i++;
else
{
printf("FALSE,i=%d, j=%d; j++, nema zamene\n",i,(j+1));
}/* Metoda koja pokreće rekurzivno sortiranje početnog niza. */
void brzoSortiranje(int a[ ], int l,int d,int n)
{
if(l >= d)
{
int pi=deljenjeNiza(a,l,d);
printf("Pivot %d je na poziciji %d\n",a[pi],pi);
brzoSortiranje( a,l,pi-1,n);
printArray(a,n);
brzoSortiranje( a,pi+1,d,n);
}{
return;
}int pi=deljenjeNiza(a,l,d);
printf("Pivot %d je na poziciji %d\n",a[pi],pi);
brzoSortiranje( a,l,pi-1,n);
printArray(a,n);
brzoSortiranje( a,pi+1,d,n);
int main()
{
int n;
int A[ ] = { 24, 18, 38,43,14,40,1,54};
n = sizeof(A) / sizeof(A[ 0 ]);
brzoSortiranje( A,0,n-1,n);
stampajNiz(a, n);
return 0;
}int A[ ] = { 24, 18, 38,43,14,40,1,54};
n = sizeof(A) / sizeof(A[ 0 ]);
brzoSortiranje( A,0,n-1,n);
stampajNiz(a, n);
return 0;
Nakon pokretanja ove aplikacije u konzoli:
Slika 7: Izvršenje aplikacije za brzo sortiranje
|
Sledeće
Binarna pretraga>| |