Problem ze zrozumieniem kodu quicksort

Question

void quicksort(int *tablica, int lewy, int prawy)
{
int v=tablica[(lewy+prawy)/2];
int i,j,x;
i=lewy;
j=prawy;
do{
while (tablica[i]<v) i++;
while (tablica[j]>v) j--;
if (i<=j){
       x=tablica[i];
       tablica[i]=tablica[j];
       tablica[j]=x;
       i++; j--;
         }
}while(i<=j);

if (j>lewy) quicksort(tablica,lewy, j);
if (i<prawy) quicksort(tablica, i, prawy);
}
  

 

Witam, jest to kod z odcinka 14 z kursu c++ przedstawiający sortowanie quicksort zaznaczyłem na czerwono linijki kodu ktorych nie rozumiem, mógłby mi je ktoś wyjaśnić. Dziekuje z góry za pomoc.

Answer 1

Do funkcji przekazujesz: 

int *tablica, int lewy, int prawy

tablica - tablica do posortowania,

lewy - indeks elementu  od którego chcesz sortować (jeżeli dasz 0 to będzie sortować od początku, jednakże istnienie tej zmiennej jest  istotne w przypadku rekurencji)

prawy -indeks  elementu do którego chcesz sortować ,

Jeżeli np. tablica ma 10 elementów o indeksach 0,1,2,...,8,9 i wywołasz funkcję quicksort(t[], 3,7)  to posortowane będą elementy od 3 do 7 a tych o indeksach 0,1,2,8,9 funkcja nie ruszy

int v=tablica[(lewy+prawy)/2]; 

tutaj sobie robisz zmienną v i przypisujesz jej wartość środkowego elementu w tablicy ((lewy+prawy)/2 zwraca część całkowitą liczby, więc (1+4)/2 = 2)

while (tablica[i]<v) i++; 
while (tablica[j]>v) j--; 

tutaj i jest indeksem lewego elementu, idziesz od lewej szukając pierwszego elementu który będzie miał wartość większą niż v (while wykonuje się dopóki warunek tablice[i[<v jest prawdziwy, jeżeli napotka na element gdzie tablica[i] > v to się przerwie), następnie to samo robisz z j (j idzie od prawej) - szukasz pierwszego elementu który będzie miał wartość mniejszą od v (od środkowego wyrazu tablicy) potem zamieniasz te dwa elementy miejscami itd. (dalej mniemam że już rozumiesz )

Comments

O karwa kawka wielkie dzięki, już zrozumiałem, miałem zły tok rozumowanie. Już rozumiem ten quicksort. Wielkie dzięki jeszcze raz.

---

Mam jeszcze 1 pytanie co jeżeli:

Mam taki ciąg liczb:

5 9 7 2 0 1 4 8 6 3

i        v               j

i zostaje na miejscu bo jest mniejsze od 2

j dochodzi do 4 bo 1 juz nie jest wieksza od 2

I co teraz ma się stać kod jest taki:

do{
while (tablica[i]<v) i++;
while (tablica[j]>v) j--;
if (i<=j)
    {

     x=tablica[i];
     tablica[i]=tablica[j];
     tablica[j]=x;
      i++; j--;
    }
}
while(i<=j);

 

---

YYYY nie 

 

Generalnie zakładając że sortujesz całą tablicę, czyli i=0 j=9 (na początku) to

v=t[(0+9)/2] = t[4] = 0

więc startują while 5 > 0 więc i = 0

3 > 0 j-- // j=8

6 > 0 j--  //j=7

....

aż wkońcu dochodzimy do sprzeczności przy 0 > 0 j=4

następnie if(i <= j)  <=>  if(0 <=4) //co jest prawdą

to w środku if'a to po prostu zamienienie dwóch liczb w tablicy miejscami, czyli od teraz t[0] = 0   i t[4] = 5

 

ponieważ to wszystko zamknięte jest w do while to teraz sprawdzany jest warunek i<=j co jest prawdą, więc wraca do początku pętli czyli v = 0 (dalej, bo tego nie zmienialiśmy) i=0 (też nie zmienialiśmy j=4 (bo przesunęliśmy j na 4 przy poprzednim obiegu pętli), dalej sam rozkmiń co się dzieje