Dyskusja:Sortowanie przez kopcowanie

Ten artykuł jest pod opieką Wikiprojektu Informatyka, którego celem jest rozwijanie artykułów z dziedziny informatyki. Jeśli chcesz współuczestniczyć w projekcie, odwiedź jego stronę, gdzie można przyłączyć się do dyskusji i zobaczyć listę otwartych zadań.

Ten artykuł został oceniony jako zalążkowy na skali jakości.

Temu artykułowi przypisano niskie znaczenie na skali ważności.

Zalążek

Niskie

Nie podoba mi się użyta terminologia :] Na przykład słowo liść - czy zostało użyte zgodnie z powszechnie przyjętym znaczeniem? Nie ma również chyba potrzeby robienia linka np. z tablicy wszędzie, gdzie wystąpi --severson 20:21, 2 lis 2004 (CET)[odpowiedz]

jest jeszcze

musi zaczynać się od indeksu równego 1 - nie 0, ze względu na poprawność działania wzorów)

co jest nieprawda (wystarczy zmienic wzory). nic nie trzeba zmieniac na kopiec itd. ogolnie mnostwo niedorobek. Kbsc 20:33, 2 lis 2004 (CET)[odpowiedz]

Zrobiłem od nowa opis działania (mam nadzieję, że teraz jest lepiej). Pozwoliłem sobie także zmienić knot na node w przykładowej implementacji. --filu 19:22, 21 maj 2005 (CEST)[odpowiedz]

Warto byłoby jeszcze wspomnieć o różnych usprawnieniach tego algorytmu, chociażby rozróżnić pokazaną tu metodę zstępującą od efektywniejszej wstępującej.

"a pamięciowa – O ( n ) , {\displaystyle \scriptstyle \mathrm {O} (n),} \scriptstyle \mathrm O(n), " Tak rozumując to każdy algorytm będzie miał złożoność pamięciowa – O ( n ) i nie rozróżnia się wtedy tego że np standardowa implementacja sortowania przez podział potrzebuje O(n) dodatkowej pamięci na rekurencję lub stos
czy sortowania przez scalanie które w standardowej implementacji potrzebuje O(n) pamięci na scalanie Rekurencję w sortowaniu przez scalanie można usunąć bez stosu W porównaniu z nimi sortowanie przez kopcowanie sortuje w miejscu

Wydaje mi się, że w procedurze shift-down jest błąd.

shift-down (T[1..n], i)
   k ← i
   repeat
       j ← k
       if 2j <= n and T[2j] > T[k]
           k ← 2j
       if 2j+1 <= n and T[2j+1] > T[k]
           k ← 2j+1
       swap (T[j], T[k])
   until j = k

Procedura nie zapewnia przywrócenia własności kopca. Jeśli T[j]<T[2j+1]<T[2j] to k zostanie ustawione na 2j+1, w wyniku czego zostaną podmienione T[j] z T[2j+1], tak więc T[2j+1] znajdzie w T[j] mimo, że jest mniejsze od T[2j]. Problem można rozwiązać na co najmniej 2 sposoby:

shift-down (T[1..n], i)
   k ← i
   repeat
       j ← k
       if 2j <= n and T[2j] > T[k]
           k ← 2j
       if 2j+1 <= n and T[2j+1] > T[k] and T[2j+1] > T[2j]
           k ← 2j+1
       swap (T[j], T[k])
   until j = k

lub gdy priorytetem jest ograniczenie ilości porównań:

shift-down (T[1..n], i)
   k ← i
   repeat
       j ← k
       if 2j <= n and T[2j] > T[k]
           k ← 2j
           if 2j+1 <= n and T[2j+1] > T[2j]
               k ← 2j+1
       else
           if 2j+1 <= n and T[2j+1] > T[k] and T[2j+1] > T[2j]
               k ← 2j+1
       swap (T[j], T[k])
   until j = k

co ogranicza liczbę porównań do 2 na jedną zamianę (zamiast 3 w pierwszym przypadku). Ze względu na czytelność pozwoliłem sobie umieścić pierwszą wersję na stronie.--Schizofrenikh (dyskusja) 19:40, 12 sie 2008 (CEST)[odpowiedz]

wydaje mi się, że kolega Schizofrenikh się myli. Jeśli T[j] < T[2j+1] < T[2j], to w pierwszym if za k zostanie podstawione 2j, więc w drugim zostanie sprawdzony warunek T[2j+1] > T[k], czyli T[2j+1] > T[2j] (bo k jest teraz równe 2j, a nie j), co jest nieprawdą i zamienione zostaną poprawnie T[j] i T[2j].

Można to zilustrować przyjmując, że T[j] to ojciec, T[2j] to lewy syn, a T[2j+1] to prawy syn. Mamy ojciec < prawy syn < lewy syn. T[k] ma wskazywać na najwyższego. Na początku k jest rowne j, czyli T[k] wskazuje na ojca. W pierwszym if sprawdzamy, czy lewy syn jest wyższy od ojca. Tak w rzeczywistości jest, zatem k jest teraz równe 2j i T[k] wskazuje na lewego syna. Ponieważ w kodzie są dwie instrukcje if, a nie instrukcja if-else, program przechodzi do sprawdzania warunków drugiego if. Po sprawdzeniu, czy prawy syn istnieje, program sprawdza, czy prawy syn, jest wyższy od T[k], które wskazuje teraz na lewego syna. Ponieważ prawy syn jest niższy, T[k] wskazuje wciąż na lewego syna.

Mam nadzieję, że wyjaśniłem to jasno i nie popełniłem jakiegoś błędu. Myślę, że poprzedni kod był poprawny i dodatkowy warunek T[2j+1] > T[2j] jest niepotrzebny. Pozwoliłem sobie na edycję, osobę przeglądającą edycje proszę o weryfikację tego myślenia, nie chciałbym wprowadzać tysięcy studentów w błąd :P --jaczula (dyskusja) 19:08, 21 paź 2012 (CEST)[odpowiedz]

Napisałem program w Pascalu. W obu przypadkach buduje kopiec dobrze, oznacza to że należy przyjąć prostszą i szybszą wersję bez dodatkowego warunku. Po przejrzeniu zatwierdziłem wersję Jaczuli. Borneq (dyskusja) 00:35, 30 paź 2012 (CET)[odpowiedz]