[Eli] Quicksort

paladin · Post autor: **paladin** » 29 gru 2011, o 23:50

Ha, tu jest pewne zderzenie poważnej algorytmiki (QuickSort) z niepoważnym ujęciem (Eli). Mało kto tłumaczy algorytmy w ten sposób.
Spróbowałbym z książką "Algorytmy" - Dasgupta, Papadimitriou, Vazirani. Nie jest aż tak prosto, żeby były schematy blokowe, ale jest po amerykańsku łopatologicznie
[edit] I zawsze można użyć Google - dla większości podstawowych algorytmów da się znaleźć miejsce w Internecie, gdzie będą wytłumaczone przystępnie.

menrva · Post autor: **menrva** » 30 gru 2011, o 11:12

Nie wiem, czy to dobrze będzie...

Od początku...

7 5 8 10 1 15 12 4 11 19 1 - biorę 7 i szukam mniejszej liczby od niej

5 1 4 1 7 |8 10 15 12 11 19 - biorę 5 z lewej i szukam mniejszej liczby od niej , biorę 8 z prawej i szukam mniejszej od niej (nie ma mniejszej od 8, czyli 8 stoi na właściwym miejscu)
1 4 5 1 7 |8 10 15 12 11 19 - biorę 4 z lewej, szukam, zamieniam z 1, 10 z prawej stoi na właściwym miejscu, biorę 15 i szukam
1 1 4 5 7 | 8 10 12 11 15 19 - lewa strona jest już posortowana, z prawej biorę 12 i szukam mniejszych od niej
1 1 4 5 7 | 8 10 11 12 19

Może być takie coś? Nic innego chyba nie wymyślę...

paladin · Post autor: **paladin** » 30 gru 2011, o 11:34

Mniej-więcej dobrze. Tylko jeszcze dwie rzeczy: trzeba zapisać algorytm przestawiania elementów, oraz zrozumieć, co to jest rekurencja

menrva · Post autor: **menrva** » 30 gru 2011, o 11:39

To znaczy co dokładnie?

paladin · Post autor: **paladin** » 30 gru 2011, o 11:58

Będziesz musiała w Eli zaimplementować rekurencję - wiesz, jak? Bo ja nie
Trzeba również dokładniej zapisać, w jaki sposób przestawiasz mniejsze elementy na lewo, większe na prawo - to jest dobrze zapisane np. na Wikipedii.

menrva · Post autor: **menrva** » 30 gru 2011, o 12:02

Po to tutaj napisałam, aby kto mi pomógł ze schematem blokowym w eli...

-- 1 sty 2012, o 16:19 --

Ponawiam prośbę... Czy mógłby mi ktoś pomóc uzupełnić te klocki?
http://imageshack.us/photo/my-images/403/alg.png/

Kod: Zaznacz cały

void quicksort(int tab[], int left, int right){
     int i=left;
     int j=right;
     int x=tab[(left+right)/2];
     do{
         while(tab[i]<x) i++;
         while(tab[j]>x) j--;
         if(i<=j){                  
             int temp=tab[i];
             tab[i]=tab[j];
             tab[j]=temp;
             i++;
             j--;
         }
     }while(i<=j);
     if(left<j) quicksort(tab,left,j);
     if(right>i) quicksort(tab,i,right);    
}

-- 2 sty 2012, o 22:20 --Może mi ktoś powiedzieć gdzie jest błąd?

... uzblz.png/