Sortowanie stogowe Benny: Nie wiem czemu, ale nie działa mi sortowanie stogowe. void Przesiewanie(int l, int p, int A[100]) { int x,i,j; x=A[l]; i=l; j=(2*i)+1; while(j<=p) { if(j<p && A[j]<A[j+1]) j++; if(x<A[j]) { A[i]=A[j]; i=j; j=(2*i)+1; } } A[i]=x; } void BudujStog(int n, int A[100]) { for(int i=(n−2)/2;i>=0;i−−) Przesiewanie(i,n−1,A); } void SortowanieStogowe(int n, int A[100]) { BudujStog(n,A); int x; for(int i=n−1;i>=1;i−−) { x=A[0]; A[0]=A[i]; A[i]=x; Przesiewanie(0,i−1,A); } }

Mariusz: Piszesz to na podstawie pseudokodu Cormena ? Jeśli tak to powinien działać Heapify(A,i) l←2i r←2i+1 if (l≤heapsize[A]) and (A[l]>A[i]) then largest←l else largest←i if(r≤heapsize[A])and (A[r]>A[largest]) then largest←r if largest ≠i then zamien A[i]↔A[largest] Heapify(A,largest) Buildheap(A) heapsize[A]←length[A] for i←length[A]/2 downto 1 do Heapify (A,i) Heapsort(A) Buildheap(A) for i←length[A] downto 2 do zamien A[1]↔A[i] heapsize[A]←heapsize[A]−1 Heapify(A,1) Jak napisałem według tego pseudokodu to sortowanie działa Przykładowy kod masz w numerical recipes in c

Benny: Szczerze to niczego nie zrozumiałem. Miałem taki program napisany na wykładzie przez prowadzącego, który twierdzi, że to powinno działać.

Mariusz: Sprawdzałeś czy nie masz gdzieś nieskończonej pętli ? np czy warunek w pętli while kiedykolwiek będzie fałszywy ? Prześledź zmienne przy użyciu debuggera

Mariusz: Do if(x<A[j]) zapomniałeś dopisać else w którym dajesz warunek kończący pętlę

Mariusz: Co gdyby p było największą liczbą możliwą do zapisania na 32 bitach ? Z tego co zauważyłem to j jest indeksem więc w C jest nieujemne Można zmodyfikować warunek pętli while z j<=p na j<=p&&j>=0 Wtedy w else z instrukcji warunkowej if(x<A[j]) można by było dać ulubioną liczbę ujemną Zastanawiam się też nad opakowaniem instrukcji A[i]=x; instrukcją warunkową if

jc: Mój dawny i działający kod poniżej. Sprawdzaj swój kod, aż znajdziesz usterkę. Albo zrób przerwę i napisz od nowa. Sugerowałbym indeksować tablicę od 1 zamiast od zera. Tak jest łatwiej. −−−−−−− /* sortowanie kopcowe */ #include<stdio.h> const int n = 10; int x[]={0,3,2,5,7,3,2,9,1,7,8}; void wdol(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; } int main(){ int t; for(int i=1; i<=n; i++) printf(" %d ", x[i] ); printf("\n"); for(int i = n/2; i >= 1; i−−) wdol(i,n); for(int i = n; i >= 2; i−−){ int t = x[1]; x[1] = x[i]; x[i] = t; wdol(1,i−1); } for(int i=1; i<=n; i++) printf(" %d ", x[i] ); printf("\n"); }

jc: Spojrzałem. Kiedy kończy Ci się pętla w Przesiewaniu? Wydaje się, że dopiero, gdy dojdziesz do krawędzi. A często powinna skończyć się wcześniej.

Mariusz: My na temat poprawiania pseudokodu Cormena już pisaliśmy https://matematykaszkolna.pl/forum/319451.html i z tego co zdążyłem zauważyć to w instrukcji warunkowej if(x<A[j]) zapomniał dać else Ciekawe czy już nie za późno i czy Benny jeszcze odpisze

Benny: Nigdy nie jest za późno. Z tym przesiewaniem to się właśnie zastanawiałem czy tam czegoś nie brakuje, bo robiłem symulacje w zeszycie i się pętla nigdy nie kończyła. Czy w Dev−C++ jest debugger?

jc: Jest debugger− polecenie gdb. Nigdy nie używałem debuggera. Mój kod działa, tylko trzeba zamienić and na &&. Gdybyś kopiował, to pamiętaj, aby zamienić minusy na prawdziwe minusy.

Benny: Jasne, ale pytam, bo może kiedyś się przydać. Gdzie to polecenie mam wklepać?

Mariusz: Benny twój kod też będzie się zatrzymywał w rozsądnym czasie gdy do instrukcji if(x<A[j]) dopiszesz else void Przesiewanie(int l, int p, int A[100]) { int x,i,j; x=A[l]; i=l; j=(2*i)+1; while(j<=p) { if(j<p && A[j]<A[j+1]) j++; if(x<A[j]) { A[i]=A[j]; i=j; j=(2*i)+1; } else j=p+1; //tej linijki kodu u ciebie zabrakło } A[i]=x; } void BudujStog(int n, int A[100]) { for(int i=(n−2)/2;i>=0;i−−) Przesiewanie(i,n−1,A); } void SortowanieStogowe(int n, int A[100]) { BudujStog(n,A); int x; for(int i=n−1;i>=1;i−−) { x=A[0]; A[0]=A[i]; A[i]=x; Przesiewanie(0,i−1,A); } } Oczywiście można warunek pętli while zmienić z j<=p na j<=p&&j>=0 Kod wyglądałby wtedy tak void Przesiewanie(int l, int p, int A[100]) { int x,i,j; x=A[l]; i=l; j=(2*i)+1; while((j<=p)&&(j>=0)) { if(j<p && A[j]<A[j+1]) j++; if(x<A[j]) { A[i]=A[j]; i=j; j=(2*i)+1; } else j=−1; //tej linijki kodu u ciebie zabrakło } A[i]=x; } void BudujStog(int n, int A[100]) { for(int i=(n−2)/2;i>=0;i−−) Przesiewanie(i,n−1,A); } void SortowanieStogowe(int n, int A[100]) { BudujStog(n,A); int x; for(int i=n−1;i>=1;i−−) { x=A[0]; A[0]=A[i]; A[i]=x; Przesiewanie(0,i−1,A); } } Zazwyczaj skorzystaj z debuggera piszą ci którzy nie umieją bądź nie chcą pomóc

Benny: Dzięki bardzo. Czyli po prostu dopisujemy ten warunek, żeby wyjść z pętli, tak?

Mariusz: Tak, dokładniej rozbudowujemy ten warunek który już masz o to co by było gdyby warunek się nie spełnił − wychodzimy wtedy z pętli

jc: Benny, pytasz gdzie to polecenie mam wklepać? Pytasz, jakbyś pierwszy raz dotykał komputera. W moim pierwszym komputerze faktycznie nie było gdzie wpisywać poleceń, ale były poza systemem odpowiednie programy. Skoro spytałeś o dev−c++, to pewnie używasz Windows. Polecenia możesz wpisywać w programie cmd (choć może się coś zmieniło, Windowsa używałem epizodycznie kilkanaście lat temu).

Benny: Pytam, bo ja nie odpalam programu prosto z cmd tylko poprzez deva.

jc: dev odpala cmd ... Nie musisz korzystać z pośrednika.

jc: Szukaj, może dev ma odpowiedni przycisk.

Mariusz: Na pasku menu między wykonuj a narzędzia Na dole tam gdzie informacje kompilatora (ostrzeżenia i błędy) między logiem kompilatora a znajdź wyniki U mnie na początku działał a teraz coś nie reaguje na próby uruchomienia

Mariusz: jc pisałeś kiedyś listę , przydałaby mi się do czytania małych plików (zwłaszcza jeśli jakiś algorytm wymaga abyśmy przeczytali go wiele razy) Jeśli chodzi o język to Pascal albo C chociaż w C występował mi błąd segmentation fault i nie wiem jak się go pozbyć Benny ty jak skończysz z sortowaniami to pewnie też zajmiesz się listami , stosami , kolejkami czy grafami Chociaż sortować można też listę czy plik lecz tam wygodniejsze jest sortowanie przez scalanie

Mariusz: Sortowanie listy polega na zamianie wskaźników

Mariusz: Na stack overflow widziałem procedurę przesiewającą napisaną zgodnie z pseudokodem Cormena ale iteracyjnie Instrukcji break najłatwiej się pozbyć wprowadzając zmienną logiczną i modyfikując warunek wejścia do pętli Na youtube widziałem całkiem ładnie napisany kod procedury przesiewającej

Mariusz: Tę procedurę przesiewającą można znaleźć np w książce Wirtha W kodzie zamieszczonym u Wirtha była jeszcze instrukcja skoku którą prowadzący usunął nie modyfikując warunku na wyjście z pętli Tak jak napisałem wcześniej jeżeli chcemy wyeliminować instrukcję skoku to najlepiej wprowadzić zmienną logiczną i zmodyfikować warunek dla pętli while Wirth napisał że ta procedura przesiewająca została zaproponowana przez Floyda

Mariusz: Benny "Szczerze to niczego nie zrozumiałem. Miałem taki program napisany na wykładzie przez prowadzącego, który twierdzi, że to powinno działać." Gdyby prowadzący dał specjalnie nie działający (imiesłów dlatego pisownia rozłączna) kod dla was do poprawienia to byłoby to zrozumiałe ale gdy podał ten kod jako przykład to powinien on działać , no ale w wielu skryptach widziałem błędne przykłady Myślę że prowadzący przepisał kod funkcji przesiewającej z książki Wirtha usuwając instrukcję skoku i nie proponując nic w zamian Gdybyś przeczytał kod funkcji przesiewającej linia po linii to sam doszedłbyś do tego kiedy i dlaczego otrzymujesz nieskończoną pętlę

Mariusz: Zaprezentowany algorytm można uogólnić na inne wskaźnikowe struktury danych np listy wykorzystując drzewo binarne (binarne drzewo poszukiwań) Mamy daną listę (dla listy jednokierunkowej jeden wskaźnik byłby wykorzystywany tylko przez drzewo) Dopóki nie przejdziemy całej listy wstawiamy jej węzły do drzewa zachowując przy tym warunek węzeł z mniejszym lub równym kluczem trafia do lewego poddrzewa Przechodzimy drzewo przeszukując je wgłąb Zapisujemy drzewo binarne w postaci listy Tutaj jc mógłby coś więcej napisać skoro chwalił się że wykłada i że drzewka pisał