🚀 go-pugleaf

Dnia Wed, 16 Nov 2005 16:04:31 +0100, Miroo skrobie:
> Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
> napisał(a):
> > Istnieje taka możliwa sytuacja, że dla danego elementu tablicy
> > zostanie porównana tylko ze szczytem stosu, a następnie
> > zaakceptowana lub odrzucona. Jeśli zostanie zaakceptowana, to
> > spycha pozostałe w dół. Nie widzę tu żadnego innego porównania
> > (poza ewentualnie sprawdzeniem, czy doszliśmy do końca zbiornika).
> > Ani, szczerze mówiąc, innych możliwych sytuacji. Poza tym nie
> > miałem racji w poprzednim poście (tak mnie tylko tknęło dla
> > bezpieczństwa), że trzeba będzie pilnować sortowania. Jeśli liczba
> > dostanie się na szczyt kolejki, to znaczy, że jest większa od
> > szczytu, więc liczby będą tak czy siak posortowane.

> Chyba cię wcześniej źle zrozumiałem - czy liczba "na szczycie"
> stosu jest największą w tym stosie czy najmniejszą?
> Bo jeśli największą to źle, bo "zgubisz" liczby mniejsze niż
> ta największa a większe niż któraś z pozostałych.
> Jeśli "na szczycie" jest najmniejsza liczba ze stosu to
> nie ma z kolei mowy o spychaniu pozostałych ale o wejściu
> na jej miejsce (a potem porównywaniu z następnymi liczbami
> w kopcu i ewntualnym przesuwaniu, żeby zachować sortowanie).

Aha, czyli w efekcie mój sposób jest całkiem do chrzanu ;) To oznacza, że
trzeba wrzucać każdą liczbę do kolejki i w ogóle nie porównywać.

A minimalna liczba porównań jest taka, jakiej potrzebuje kolejka do utrzymania
sortowności.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"