sortowanie stooge-sort
-
- Użytkownik
- Posty: 56
- Rejestracja: 22 paź 2007, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: k-ce
- Podziękował: 4 razy
sortowanie stooge-sort
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ę.
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
- Użytkownik
- Posty: 642
- Rejestracja: 20 gru 2005, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 130 razy
sortowanie stooge-sort
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
-
- Użytkownik
- Posty: 56
- Rejestracja: 22 paź 2007, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: k-ce
- Podziękował: 4 razy
sortowanie stooge-sort
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ń ??)
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ń ??)
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
sortowanie stooge-sort
"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)
"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)
-
- Użytkownik
- Posty: 56
- Rejestracja: 22 paź 2007, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: k-ce
- Podziękował: 4 razy
sortowanie stooge-sort
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
sorry za kłopot
-
- Użytkownik
- Posty: 56
- Rejestracja: 22 paź 2007, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: k-ce
- Podziękował: 4 razy
sortowanie stooge-sort
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.
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.
Ostatnio zmieniony 25 maja 2008, o 18:37 przez yaro84, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
sortowanie stooge-sort
sterowanie wraca do punktu (***) i dalej na tym poziomie rekursji wywołuje jeszcze rekurencyjnie STOOGE-SORT 2 razyyaro84 pisze: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)
-
- Użytkownik
- Posty: 56
- Rejestracja: 22 paź 2007, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: k-ce
- Podziękował: 4 razy
sortowanie stooge-sort
"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...
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...
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
sortowanie stooge-sort
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
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
-
- Użytkownik
- Posty: 56
- Rejestracja: 22 paź 2007, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: k-ce
- Podziękował: 4 razy
sortowanie stooge-sort
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?
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?
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
sortowanie stooge-sort
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.