sortowanie stooge-sort

[yaro84]

Witam. Mam taki algorytm sortujący:

STOOGE-SORT (A, i, j)
if A>A[j]
then zamień A A[j]
if i + 1 >= j
then return
k := "całość dolna" (j - i + 1)/3
STOOGE-SORT (A, i, j - k)
STOOGE-SORT (A, i + k, j)
STOOGE-SORT (A, i, j - k)


I mam prośbę. Może ktoś by wytłumaczył dokładniej jak ten algorytm działa, a mianowicie nie wiem za co odpowiada polecenie return, kiedy wywoływane są te ostatnie polecenia STOOGE-SORT (czy po kolei czy po zakończeniu czegoś).

Interesuje mnie również jaka jest złożoność tego algorytmu, a dokładniej jak ją wyznaczyć.

Wiem że jeśli trzeba to zamieniany jest 1szy element z ostatnim, jeśli tablica ma mniej niż 3 elementy to algorytm zostaje zakończony na początku i że sortowane jest na początku pierwsze 2/3 tablicy, później drugie 2/3 tablicy i na końcu ponownie 2/3 tablicy.

Proszę o pomoc i z góry dziękuję.

[kadiii]

Algorytm działa metodą dziel i zwyciężaj(nieefektywnie użytą). Słówko return to z angielskiego zwróć. Funkcja działa rekurencyjnie czyli funkcja wywołuje samą siebie, tyle, że dla różnych przedziałów. Przypuszczam, że zadanie z cormena albo z jego pochodnych, często używa sie bowiem określenia sortowanie stogowe zamiennie z sortowanie przez kopcowanie. Co do dalszych pytań ... solps3.pdf strona 5i 6. Proszę bardzo

[yaro84]

Dzięki wielkie, a może jeszcze jakiś przykład np dla tablicy:

A = (3, 2, 6, 4, 2, 5, 7, 8, 1)

Będę wdzięczny za jakiś opis

... a i co zwraca w tym przypadku to return ? (czy to zwraca zawsze tą samą wartość k czy po prostu kończy działanie algorytmu czy działanie poszczególnych wywołań ??)

[Dumel]

"całość górna" czyta się poprawnie "sufit"
"całość dolna" - "podłoga"

return zwraca sterowanie do poprzednio wywołanej rekurencyjnie funkji gdy podział dojdzie już do podzbiorów 2-elementowych (dalsze wywołania rekurencyjne nie mają już sensu)
w przypadku tablicy A = (3, 2, 6, 4, 2, 5, 7, 8, 1)
pierwsze wywołanie return zajdzie gdy podział dojdzie do podzbioru A'={1,2} (na początku 3 zamienia się z 1 stąd ten zbiór)

[yaro84]

tak, zgadzam się, następuje porównanie 2 >= 2 i wtedy jest return i "zwraca sterowanie do poprzednio wywołanej rekurencyjnie funkcji" - tzn do której ??

sorry za kłopot

[Dumel]

1.
STOOGE-SORT (A, i, j)
{
//coś tam
STOOGE-SORT (A, i, j - k)

[yaro84]

Zatem w takim przypadku ten algorytm nie działa, bowiem mamy dla tablicy
A = (3, 2, 6, 4, 2, 5, 7, 8, 1)

ST-ST (A,1,9)
3>1 zamiana i jest tablica A = (1, 2, 6, 4, 2, 5, 7, 8, 3)
2>=9 NIE
k=3

Pierwsze wywołanie
ST-ST (A,1,6) , rozważamy A = (1, 2, 6, 4, 2, 5)
1>5 NIE, 2>=6 NIE, k=2

ST-ST (A,1,4), rozważamy A=(1, 2, 6, 4)
1>4 NIE, 2>=4 NIE, k=1

ST-ST (A,1,3) rozważamy A=(1, 2, 6)
1>6 NIE, 2>=3 NIE, k=1

ST-ST (A,1,2) rozważamy A=(1, 2)
1>2 NIE, 2>=2 - RETURN Tutaj tablica ma postać : A=(1,2,6,4,2,5,7,8,3)


Drugie wywołanie:
ST-ST (A,4,9) rozważamy tablicę A=(4, 2, 5, 7, 8, 3) i postępując analogicznie jak w pierwszym wywołaniu otrzymamy ostatecznie tablicę
A= (1, 2, 6, 3, 2, 4, 5, 7, 8) Mamy bowiem:

ST-ST (A,4,9) tablica A=(4, 2, 5, 7, 8, 3)
4>3 TAK Zamiana i tablica A= (3, 2, 5, 7, 8, 4)
5>=9 NIE, k=2

ST-ST (A,6,9) tablica A=(5, 7, 8, 4)
5>4 TAK, tablica A=(4, 7, 8, 5)
7>=9 NIE, k=1

ST-ST(A,7,9) tablica A=(7, 8, 5)
7>5 TAK tablica A=(5, 8, 7)
8>=9 NIE, k=1

ST-ST(A,8,9) tablica A=(8, 7)
8>7 TAK, tablica A=(7, 8)
9>=9 Tak - RETURN - TRZECIE WYWOłANIE


Trzecie wywołanie:
ST-ST (A,1,6) tzn pierwsze 2/3 tablicy a liczba 6 na pewno nie znajdzie się na miejscu 5. Co robię źle?? Poza tym zawsze będę porównywał 1 z inną liczbą i zamiana nie nastąpi w ogóle.

[Dumel]

Zatem w takim przypadku ten algorytm nie działa, bowiem mamy dla tablicy
A = (3, 2, 6, 4, 2, 5, 7, 8, 1)

ST-ST (A,1,9)
3>1 zamiana i jest tablica A = (1, 2, 6, 4, 2, 5, 7, 8, 3)
2>=9 NIE
k=3

Pierwsze wywołanie
ST-ST (A,1,6) , rozważamy A = (1, 2, 6, 4, 2, 5)
1>5 NIE, 2>=6 NIE, k=2

ST-ST (A,1,4), rozważamy A=(1, 2, 6, 4)
1>4 NIE, 2>=4 NIE, k=1

ST-ST (A,1,3) rozważamy A=(1, 2, 6) (***)
1>6 NIE, 2>=3 NIE, k=1

ST-ST (A,1,2) rozważamy A=(1, 2)
1>2 NIE, 2>=2 - RETURN Tutaj tablica ma postać : A=(1,2,6,4,2,5,7,8,3)

sterowanie wraca do punktu (***) i dalej na tym poziomie rekursji wywołuje jeszcze rekurencyjnie STOOGE-SORT 2 razy

[yaro84]

"sterowanie wraca do punktu (***) i dalej na tym poziomie rekursji wywołuje jeszcze rekurencyjnie STOOGE-SORT 2 razy"


Które STOOGE-SORT wywołuje??

STOOGE-SORT (A, i + k, j)
STOOGE-SORT (A, i, j - k) Te?? Bo raczej chyba nie... Nie rozumiem tego...

[Dumel]

to może ogólniej:
niech będzie funkcja A,wywołująca B i C:
A()
{
B();
(*)
C();
return;
}
a B niech wywołuje E i F
B()
{
(***)
E();
(**)
F();
return;
}
i
C()
{coś tam; return;}
E()
{coś tam; return;}
F()
{coś tam; return;}

wywołujemy funkcję A() i teraz:
1. wywołuje się funkcja B() - sterowania przechodzi do punktu (***)
2. jest wywołanie E() i po zakończeniu jej wykonania idziemy do punktu (**)
3. wywołuje się F(). po zakończeniu działania F kończy działanie też B i sterowanie wraca do (*)
4. wywołanie C()
5. zakończenie pracy A

mam nadzieję że to już jest dość jasne

[yaro84]

No to mam jeszcze jedno pytanie:

Jak wracamy do punktu (*) to z jakimi wartościami, bo wartości się mogą zmienić podczas wykonywania E, F.
W przykładzie, który podałem jest tak właśnie z wartością k.
k ma wartość z wywołania z którego wracamy czy z wywołania do którego wracamy?

[Dumel]

to zależy od implementacji już w konkretnym języku programowania. w tym wypadku mamy wartość k z wywołania do którego wracamy, bo (w prawidłowo zaimplementowanym algorytmie STOOGE-SORT(A,i,j) ) argumenty i,j są (w C++) przekazywane przez wartość, a nie przez referencję, przez co tworzone są tylko lokalne kopie przekazywanych wartości. Zauważ że inaczej jest z tablicą A - przekazujemy ją przez wskaźnik co powoduje że operacje na niej wykonane zachowują się po zakończeniu wywołania.