Opisanie działania funkcji.

Witam!

Potrzebuję dokładnego opisu działania takiej oto funkcji:

 split(int tab[], int b, int e)
        {
                int p, t, j, i;
                i = (b+e) / 2;
                p = tab[i];
                t = tab[i]; tab[b] = p; tab[i] = t;
                i = b+1; j=e;
 
                        while(i<j)
                                {
                                        while((tab[i] <= p) && (i<j)) i++;
                                        while((tab[j] <= p) && (j>i)) j--;
                                        if(i<j){
                                        t = tab[i]; tab[i] = tab[j]; tab[j] = t;
                                }
                if(tab[i]>p) j--;
                t = tab[i]; tab[i] = tab[b]; tab[b] = t;
                        return i;
        }

Potrzebuję dokładnego opisu co robią poszczególne linijki kodu.

Pozdrawiam i dziękuję.

Dział praca jest trochę niżej.

Proszę.

Jeżeli chcesz, żebyśmy ci pomogli (a nie zrobili coś zupełnie za ciebie) to wskaż, z czym konkretnie masz problem.

Więc tak:

 split(int tab[], int b, int e)
        {
                int p, t, j, i;                    
                i = (b+e) / 2;
                p = tab[i];                                                 // << Nie rozumiem tych podstawień
                t = tab[i]; tab[b] = p; tab[i] = t;                  // << Nie rozumiem tych podstawień
                i = b+1; j=e;                                             // << Nie rozumiem tych podstawień
 
                        while(i<j)
                                {
                                        while((tab[i] <= p) && (i<j)) i++;
                                        while((tab[j] <= p) && (j>i)) j--;
                                        if(i<j){
                                        t = tab[i]; tab[i] = tab[j]; tab[j] = t;   // << Nie rozumiem tych podstawień
                                }
                if(tab[i]>p) j--;
                t = tab[i]; tab[i] = tab[b]; tab[b] = t;             // << Nie rozumiem tych podstawień
                        return i;
        }

A wiesz w ogóle co ta funkcja robi? Na oko to jest partition z quicksorta w wersji Hoara. Poszukaj opisu tego algorytmu i będziesz wszystko wiedział.

Powiedzcie mi jeszcze dlaczego w tym kodzie dokładnie w 7 linijce zmienna i deklarujemy jako b+1, a nie można byłoby samo b jako początek tablicy?

i = b+1; j=e;

Pozdrawiam.

Ten kod jest niepoprawny. Bo wcześniejsze przypisania powodują:

p = tab[i]; //zapamiętujemy sobie tab[i] czyli naszego pivota
t = tab[i];  //znów zapamiętujemy sobie tab[i] czyli naszego pivota, a myśle że chodziło tu o zapamiętanie tab[b]...
tab[b] = p; //na początek tablicy wpisujemy sobie naszego pivota i bezpowrotnie tracimy pierwszy element
tab[i] = t; //bo tutaj wpisujemy kolejny raz pivota zamiast początku...
i = b+1; j=e;   

Tak więc powinno tam być:

t = tab[b];

I co nam to daje? Otóż ktoś tutaj chciał sobie pomieszać algorytm Hoara z Lomuto i sprytnie zamienić sobie element środkowy ze skrajnym a potem puścić Lomuto. Lomuto charakteryzuje się tym że elementem podziału jest element skrajny i stkąd potem b+1, bo element b to element podziału i jest pomijany w czasie podziałów.