🚀 go-pugleaf

Dnia Thu, 10 Jan 2008 19:47:02 +0100, Maciej Piechotka skrobie:
> On Thu, 10 Jan 2008 16:31:12 +0000, Sektor van Skijlen wrote:

> >> > Z ciekawości, zajrzałem co ma Java. Java posiada algorytm
> >> > java.util.Collections.sort() (w dwóch wersjach, jedna z
> >> > komparatorem). Pierwszym argumentem jest LISTA (nie zakres
> >> > elementów). W żadnej klasie dziedziczącej po *.Collections nie jest
> >> > ona przesłonięta.
> >> > 
> >> > Co więcej, *.Collections.sort() ma gwarancję, że jest stabilny.
> >> > Ciekawe, dlaczego?
> > 
> >> Bo nie dawali wersji niestabilnej?
> > 
> > Zgadza się. A dlaczego nie dali wersji niestabilnej?

> Jeśli mnie pamięć nie myli to java.util.Collections.sort() kopjuje całą 
> listę do tablicy, sortuje tablicę i wstawia do listy.

> Uniwersalny stable sort:
> template <class iterator>
> void my_sort(iterator from, iterator to) {
>         typename iterator::difference_type distance = std::distance(from, 
> to);
>         typename iterator::value_type *refs = new typename 
> iterator::value_type[distance];
>         std::copy(from, to, refs);
>         std::stable_sort(&refs[0], &refs[distance]);
>         std::copy(&refs[0], &refs[distance], from);
>         delete[] refs;
> }

> Problem - kopiuje wszystko do osobnej tablicy

To jest akurat żaden problem. Prawdziwy problem jest w pierwszej linijce.
std::distance dla zbiorników dwukierunkowych posiada liniowy koszt w długość
ciągu.

Oczywiście można to zamortyzować stosując vector zamiast tablicy i kazać mu
się rozrastać w miarę dodawania elementów. Wtedy nie musisz liczyć elementów
distance'm. Natomiast jeśli już i tak przekopiowałeś elementy do wektora, to
po cholerę stosować stable_sort - zastosuj normalne sort.

> (dodatkowy narzut + > dodatkowa pamięć), ale da się.

Bąbelkowo też się da, ale nie o to nam chyba chodzi, nie? Ten sposób, który
pokazałeś jest jedynie obejściem problemu, bo tam sortowanie odbywa się już z
użyciem iteratorów swobodnego dostępu, na zapasowym zbiorniku.

A właśnie po to lista ma swoją metodę sort, bo ma wtedy możliwość dobrania się
do wewnętrznej reprezentacji i podczas sortowania obywa się bez jakichkolwiek
przydziałów pamięci, poza tym jednym, jednorazowym na martwe elementy list
używanych jako zapasów (btw. na bazie tej listy zrobiłem kiedyś listę
intruzyjną i ta mimo podobnej budowy posiada martwy element jako zwykłe pole i
jest ono typu bazowego węzła, więc tam to już w ogóle obywam się bez żadnych
przydziałów pamięci). Tam całe sortowanie odbywa się poprzez przepinanie
węzłów. Cały myk więc polega na tym: jak przepinać węzły tak, żeby sam węzeł
wystarczył do wykonania operacji.

Nie mówię, że się nie da. Tylko z jakiegoś powodu - przykładowo - metoda
splice nawet ta, która "wyplata" jedynie zakres elementów z jednej listy do
drugiej, potrzebuje nie tylko iteratorów granicznych zakresu, ale również
referencji do listy, z której je wyplata. Dlaczego?


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"Java is answer for a question that has never been stated"