sortowanie listy dwukierunkowej

Witam, zwracam się z prośbą o radę, mianowicie, jaką metodą najlepiej/najefektywniej posortować listę dwukierunkową?

W przypadku pesymistycznym merge sort. W średnim/optymistycznym quick sort (ew tzw quicker sort).

Ok, ale problem w tym, że nie mam tablicy obiektów, a chyba nie opłaca się jej tworzyć, na potrzeby w/w sortowań (bo później musiałbym jeszcze przepisywać elementy z tablicy do listy). Da się to zrobić bez tablicy? hmmm, szczerze ja nie mam pomysłu jak by tego dokonać. Napisałem sobie kod, odnośnie sortowania tablicy, wygląda on tak:

void szybkie_sort(int tab[], int x, int y)                                      //sortowanie szybkie
{
     int i, j, v;
     i=x;
     j=y;
     v=tab[x];
     do
     {
         while(v>tab[i]) i++;
         while(v<tab[j]) j--;
         if(i<=j)
         {
             swap(tab[i], tab[j]);
             i++;
             j--;
         }
     }
     while(i<=j);
     if(x<j) szybkie_sort(tab,x,j);     
     if(i<y) szybkie_sort(tab,i,y);
} 

Oczywiście podajemy adres tablicy, index początku, końca.

Oczywiście z indexami, to przerabiając to na sortowanie listy, to można by podać GLOWE i OGON z listy i zlikwidować tablicę z parametrów, ale czy da się to przerobić? hmmm, nie mam pewności...Prosze o rady.

A jaki widzisz problem w zrobieniu qicksorta listy? Jako element podziału bierzesz sobie np. pierwszy element (żeby nie marnować czasu przechodząc po liście) a następnie tworzysz sobie dwie listy (tzn wypinasz element z tej początkowej listy i wpinasz do jednej z tych nowych list, oczywiście jeśli lista ma 1 element to nie robisz nic):

• na jednej elementy < pivota
• na drugiej >= pivota
  następnie te listy rekurencyjnie sortujesz quicksortem a potem łączysz je w jedną.

Wybranie pivota na każdym poziomie to O(1) lub O(n). Podział list na każdym poziomie na 2 części to O(n), składanie tak samo O(n). Optymistycznie i średnio będziemy mieli w sumie logn poziomów (pesymistycznie n), co da nam w sumie O(nlogn) (lub O(n^2)).

Możesz też trochę to przyspieszyć dzieląc listę na 3 części: mniejsze, równe i większe od pivota. Jeśli elementów równych pivotowi będzie dużo to może sie opłacać.

Możesz też zrobić zwykłego merge-sorta. Przelatujesz po liście i połowę elementów przepinasz do jednej listy, połowę do drugiej (jeśli lista na długość 1 to nie robisz oczywiście nic). Rekurencyjnie robisz to samo dla tych nowych list. Następnie składasz te posortowane listy, co robi się w czasie liniowym, w jedną listę. Daje nam to zawsze O(nlogn).

Dzięki, poradziłem sobie.