x-kom hosting

QS - przepełnienie

wizard
utworzono
utworzono (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
komentarz

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.

×
×
  • Dodaj nową pozycję...

Powiadomienie o plikach cookie

Strona wykorzystuje pliki cookies w celu prawidłowego świadczenia usług i wygody użytkowników. Warunki przechowywania i dostępu do plików cookies możesz zmienić w ustawieniach przeglądarki.