wizard utworzono 16 marca 2011 utworzono 16 marca 2011 (edytowane) [code]procedure quick_sort_skrajny(low_indeks,max_indeks:integer); var temp,temp2,i,l,k:integer; begin if low_indeks<max_indeks then begin temp:=elementy[max_indeks]; l:=low_indeks-1; for k:=low_indeks to max_indeks-1 do if elementy[k]<=temp then begin l:=l+1; temp2:=elementy[l]; elementy[l]:=elementy[k]; elementy[k]:=temp2; end; temp2:=elementy[l+1]; elementy[l+1]:=elementy[max_indeks]; elementy[max_indeks]:=temp2; i:=l+1; quick_sort_skrajny(low_indeks,i-1); quick_sort_skrajny(i+1,max_indeks); end; end;[/code] Witam Dlaczego przy danych wejściowych posortowanych (ilosc>25000) rosnąco lub malejąco program się rozsypuje - przepełnienie a dla danych losowych dziala jak nalezy? Elementy - zmienna globalna.
rafalluz komentarz 17 marca 2011 komentarz 17 marca 2011 Z tego, co pamiętam, po prostu algorytm degeneruje się wtedy do O(n^2) i ilość wywołań rekurencyjnych powoduje przepełnienie sterty. Temu w praktyce stosuje się introsorta, bo jak dojdzie do tego przypadku, po prostu zmienia się sortowanie na takie, które zawsze ma O(n*lg(n)).
Wciąż szukasz rozwiązania problemu? Napisz teraz na forum!
Możesz zadać pytanie bez konieczności rejestracji - wystarczy, że wypełnisz formularz.