Heapsort rekurencja ogonowa Mariusz: W pseudokodzie Cormena dla sortowania stogowego występuje rekurencja ogonowa Jak się jej pozbyć Heapify(A,i,heapsize) l←2i r←2i+1 if((l≤heapsize)∧(A[l]>A[i])) then largest←l else largest←i if((r≤heapsize)∧(A[r]>A[largest])) then largest←r if largest ≠ i then A[i]↔A[largest] Heapify(A,largest,heapsize) BuildHeap(A,length) for i←[length/2] downto 1 do Heapify(A,i,length) HeapSort(A,length) BuildHeap(A,length) for i←length downto 2 do A[1]↔A[i] Heapify(A,1,i−1)

jc: Naprawianie kopca z góry w dół. Nie wiem, skąd Cormenowi wzięla się rekurencja. Zasada jest prosta. pomyśl i napisz sam. Uwaga − wygodnie numerować od 1, a nie od zera. A poniżej mój kod sprzed lat. x[ ] − tablica globalna w_dol(int k, int n){ int m = 2*k; int t = x[k]; while(m <= n){ if ( n > m and x[m] < x[m+1] ) m++; if ( t >= x[m] ) break; x[k] = x[m]; k = m; m = 2*k; } x[k] = t; } // A tu już sortowanie for(int i = n/2; i >= 1; i−−) w_dol(i,n); for(int i = n; i >= 2; i−−){ swap(x[1],x[i]); down(1,i−1); }

Mariusz: Ja próbowałem blok z if largest≠i zastąpić pętlą while ale wtedy program się nie zatrzymywał Cormen ogólnie ma dziwne pseudokody np w przypadku sortowania przez scalanie używa wartowników

jc: Mariusz Cormen nie potrafi opisywać algorytmów, za to kody podaje poprawne i łatwe do przepisania. A co do sortowania. Potrzebujesz funkcji naprawiajacej kopiec począwszy od jakiegoś miejsca. Schodzisz w dół. Kończysz, elementy poniżej są większe, bądź ich w ogóle nie ma. W przeciwnym wypadku zamieniasz element z miejsca, w którym się znajdujesz z mniejszym z dwóch poniżej (lub jedynym poniżej). Przechodzisz wraz z zaminianianym elementem niżej. Jak to mozna zrobić? Zaczynasz od miejsca wskazanego jako argument funkcji. Czy jest coś poniżej? Jeśli nie, to koniec. Czy są dwa elementy poniżej? Jesli tak, to wybierz mniejszy. Jeśli wybrany element jest większy od elementu, przy którym stoisz, zakończ pracę. Zamień miejscami wybrany element z tym, przy którym stałeś, przjedź do nowego miejsca. Napisz, jak Ci się uda poprawnie zapisać.

Mariusz: Znalazłem pewną propozycję na anglojęzycznym forum chociaż pewnie można by dać lepsze warunki logiczne bo koleś używa instrukcji łamiącej pętle Gdybym przeanalizował kod tej rekurencyjnej funkcji Cormena linia po linii to może sam bym coś wymyślił

Trivial: Pozbywanie sie rekurencji ogonowej jest bardzo proste. Wystarczy ustawić argumenty i zrobić goto na początek funkcji, np.: int tailrec(int x) { something(x); if (x < 5) { return tailrec(x+10); } else { return x; } } Zamieniamy na int tailrec(int x) { start: something(x); if (x < 5) { x = x + 10; goto start; } else { return x; } }

jc: W opisie odwróciłem uporządkowanie kopca. Na górze mam najmniejszy element. W opisanym sortowaniu potrzebujemy na odwrót. W procedurze Cormena razi mnie nazwa indeksu: przecież to element ma być większy, nie indeks! Czy chcesz zmienić kod Cormena − Trivial napisał, jak to zrobić − czy chcesz zrozumieć algorytm? O kopcu dowiedziałem się z książki Perełki oprogramowania Bentleya − na prawdę z przyjemnością się czyta.

Mariusz: No tak ale wolałbym aby wyjście z pętli było sterowanie warunkiem logicznym a nie instrukcją złamania pętli void heapify(double*A,int i,int heapsize) { bool s; double temp; s=(i<=heapsize); while(s) { l=2*i; r=2*r+1; if((l<=heapsize)&&(A[l]>A[i])) largest=l; else largest=i if((r<=heapsize)&&(A[r]>A[largest])) largest=r; if(largest!=i) { temp=A[i]; A[i]=A[largest]; A[largest]=temp; i=largest; } else s=false; } } Ostatnio widziałem całkiem ładny kod sortowania przez kopcowanie chociaż nie przypominał on tego z Cormena

jc: W czym przeszkadza Ci wyskoczenie z pętli? W każdym języku masz odpowiednią instrukcję (break). Możesz też opusćić procedurę (return). Jak inaczej zakonczysz pracę?

Mariusz: Warunek logiczny w pętli powinien o tym decydować Ja tutaj spróbowałem wprowadzić zmienną logiczną do sterowania pętlą

Mariusz: Z instrukcjami break to nie jest tak jak z przytoczonym przez Triviala goto

jc: A taki kod Ci odpowida? (Twoje nazwy w mojej procedurze) void heapify(double* A, int i, int heapsize){ int m = 2*i; double t = A[i]; while(m <= heapsize){ if ( m < heapsize && A[m] < A[m+1] ) m++; if ( t >= A[m] ) break; A[i] = A[m]; k = m; m = 2*i; } A[i] = t; }

jc: W jednym miejscu nie zmieniłem literki; poniżej poprawiony tekst. void heapify(double* A, int i, int heapsize){ int m = 2*i; double t = A[i]; while(m <= heapsize){ if ( m < heapsize && A[m] < A[m+1] ) m++; if ( t >= A[m] ) break; A[i] = A[m]; i = m; m = 2*i; } A[i] = t; }

Mariusz: jc jeśli nie da się lepszego warunku na pętlę dać to niech będzie chociaż ja bym dał zmienną logiczną do sterowania pętlą w takim przypadku Co zrobić aby sortował malejąco

jc: Mariusz. Można trochę ładniej zakończyć pętlę, ale z pewną stratą. Zwróć uwagę na liczbę podstawień: u mnie jest jeden cykl, a w Cormena i u Ciebie złożenie pewnej liczby transpozycji. W przypadku cyklu o długości n, u mnie jest n+1 podstawień, u Ciebie 3n. Przy okazji: nie byłoby ładniej pisać a→b (a wkładamy do b) zamiast b←a (do b wkładamy a)? lub po prostu b = a.

Mariusz: Tak uważasz no to może być jakiś argument za twoim kodem Ostatnio widziałem kod w którym koleś budował kopiec i przywracał własność kopca w jednej funkcji i pętle miał jakoś ładnie zakończone Nadal Jakub ma problemy ze stroną więc zapytam o procedurę scalania przedstawioną u Cormena Merge(A,p,q,r) n₁←q−p+1 n₂←r−q for i←p to q do B[i−p+1]←A[i] for i←q+1 to r do C[i−q]←A[i] B[n₁+1]←∞ C[n₂+1]←∞ i←1 j←1 for k←p to r do if(B[i]<=C[j]) then A[k]←B[i] i←i+1 else A[k]←C[j] j←j+1 MergeSort(A,p,r) if(p<r) q←[p+r/2] MergeSort(A,p,q) MergeSort(A,q+1,r) Merge(A,p,q,r) Po co tutaj Cormen dał wartowników ? Wydaje mi się że lepiej by było z nich nie korzystać Podobno tutaj także da się napisać kod bez rekurencji

Laura: ∫x2 * cos( x3 ) dx

Mariusz: Co do pętli to taka pętla będzie się wykonywać n log n razy (heapsort i mergesort wykonuje się O(n log n) razy) for i:=1 to n do begin j:=n; while(j>0) then begin (*Tutaj mamy instrukcje wykonywane w pętli instrukcje te muszą być jednak wykonane w stałym czasie *) j:=j div 2; end end;

jc: Mariusz Kody umieściłem tutaj. https://matematykaszkolna.pl/forum/319599.html

Mariusz: void heapify(double* A, int i, int heapsize){ int m = 2*i; double t = A[i]; int isheap=0; while((m <= heapsize)&&(!isheap)) { if ( m < heapsize && A[m] < A[m+1] ) m++; if ( t >= A[m] ) isheap=1; else { A[i] = A[m]; i = m; m = 2*i; } } A[i] = t; } Coś takiego mogłoby być ok chociaż na stack overflow znalazłem kod bliższy pseudokodowi Cormena Może napisałbyś coś o złożoności czasowej tego kodu oraz o przypadkach brzegowych (np co jeśli gdzieś w kodzie nastąpi przekroczenie zakresu typu int)