Dlaczego nie używamy szybkiego sortowania na połączonej liście?

Algorytm szybkiego sortowania można podzielić na następujące kroki

1. Zidentyfikuj oś przestawną.

2. Podziel listę połączoną na partycje na podstawie przestawnej.

3. Podziel listę połączoną rekurencyjnie na 2 części.

Teraz, jeśli zawsze wybieram ostatni element jako oś przestawną, wówczas identyfikacja elementu przestawnego (1. krok) zajmuje czas.$\mathcal O(n)$

Po zidentyfikowaniu elementu przestawnego możemy przechowywać jego dane i porównać je ze wszystkimi innymi elementami, aby zidentyfikować prawidłowy punkt podziału (drugi krok). Każde porównanie zajmie ponieważ przechowujemy dane przestawne, a każda zamiana zajmuje . Tak więc w sumie zajmuje dla elementów.$\mathcal O(1)$$\mathcal O(1)$$\mathcal O(n)$$n$

Tak więc relacja powtarzalności jest następująca:

$T(n) = 2T(n/2) + n$ który jest który jest taki sam jak w sortowaniu scalonym z listą połączoną.$\mathcal O(n \log n)$

Dlaczego więc sortowanie według scalania jest lepsze niż szybkie sortowanie w przypadku list połączonych?

Wzorzec dostępu do pamięci w Quicksort jest losowy, a także implementacja gotowa do użycia, więc używa wielu zamian, jeśli komórki osiągają uporządkowany wynik.
Jednocześnie sortowanie scalające jest zewnętrzne, wymaga dodatkowej tablicy, aby zwrócić uporządkowany wynik. W tablicy oznacza to dodatkowy narzut miejsca, w przypadku, gdy lista połączona, jest możliwe wyciągnięcie wartości i rozpoczęcie scalania węzłów. Dostęp ma charakter bardziej sekwencyjny.

Z tego powodu szybkie sortowanie nie jest naturalnym wyborem dla listy połączonej, podczas gdy sortowanie po scaleniu ma wielką zaletę.

Notacja Landaua może (mniej więcej, ponieważ Quicksort wciąż jest ) zgadzać się, ale stała jest znacznie wyższa.$\mathcal O(n^2)$

W przeciętnym przypadku oba algorytmy są w więc przypadek asymptotyczny jest taki sam, ale preferencja jest ściśle spowodowana ukrytą stałą, a czasem problemem jest stabilność (szybkie sortowanie jest z natury niestabilne, scalanie jest stabilne).$\mathcal O(n\log n)$

Możesz szybko sortować połączone listy, jednak będziesz bardzo ograniczony pod względem wyboru osi przestawnych, ograniczając się do osi przestawnych na początku listy, co jest złe dla prawie posortowanych danych wejściowych, chyba że chcesz zapętlić dwa segmenty dwa razy (raz dla osi przestawnej i raz na partycję). Będziesz musiał zachować stos granic partycji dla list, które nadal musisz posortować. Stos ten może wzrosnąć do gdy wybór przestawny jest zły wraz ze złożonością czasową rosnącą do O ( n 2 ) .$O(n)$$O(n^2)$

Sortowanie korespondencji na połączonych listach można wykonać tylko przy użyciu dodatkowej spacji jeśli zastosujesz podejście oddolne, licząc, gdzie znajdują się granice partycji i odpowiednio scalając.$O(1)$

Jednak dodając pojedynczą 64-elementową tablicę wskaźników, możesz uniknąć dodatkowej iteracji i posortować listy do elementów w dodatkowej spacji O ( 1 ) .$2^{64}$$O(1)$

head = list.head;
head_array = array of 64 nulls

while head is not null
    current = head;
    head = head.next;
    current.next = null;
    for(i from 0 to 64)
        if head_array[i] is null
            head_array[i] = current;
            break from for loop;
        end if
        current = merge_lists(current, array[i]);
        head_array[i] = null;
     end for
end while

current = null;
for(i from 0 to 64)
    if head_array[i] is not null
        if current is not null
            current = merge_lists(current, head_array[i]);
        else
            current = head_array[i];
        end if
     end if
 end for

 list.head = current;

Jest to algorytm używany przez jądro Linuksa do sortowania połączonych list. Chociaż z kilkoma dodatkowymi optymalizacjami, takimi jak ignorowanie previouswskaźnika podczas wszystkich operacji scalania oprócz ostatniej.

Możesz napisać sortowanie według scalania, sortowanie według partycji, sortowanie według drzewa i porównywanie wyników.
Łatwo jest napisać sortowanie według drzewa, jeśli pozwalasz na dodatkowe miejsce.
Do sortowania według drzewa każdy węzeł połączonej listy musi mieć dwa wskaźniki, nawet jeśli sortujemy pojedynczo połączoną listę
Na połączonej liście Wolę wstawianie i usuwanie zamiast zamiany
Partycji Hoare można wykonać tylko dla podwójnie połączonej listy

program untitled;


type TData = longint;
     PNode = ^TNode;
     TNode = record
                data:TData;
                prev:PNode;
                next:PNode;
             end;

procedure ListInit(var head:PNode);
begin
  head := NIL;
end;

function ListIsEmpty(head:PNode):boolean;
begin
  ListIsEmpty := head = NIL;
end;

function ListSearch(var head:PNode;k:TData):PNode;
var x:PNode;
begin
  x := head;
  while (x <> NIL)and(x^.data <> k)do
     x := x^.next;
  ListSearch := x;
end;

procedure ListInsert(var head:PNode;k:TData);
var x:PNode;
begin
  new(x);
  x^.data := k;
  x^.next := head;
  if head <> NIL then
     head^.prev := x;
   head := x;
   x^.prev := NIL;
end;

procedure ListDelete(var head:PNode;k:TData);
var x:PNode;
begin
   x := ListSearch(head,k);
   if x <> NIL then
   begin
     if x^.prev <> NIL then
        x^.prev^.next := x^.next
      else 
        head := x^.next;
     if x^.next <> NIL then
        x^.next^.prev := x^.prev;
     dispose(x);
   end;
end;

procedure ListPrint(head:PNode);
var x:PNode;
    counter:longint;
begin
  x := head;
  counter := 0;
  while x <> NIL do
  begin
    write(x^.data,' -> ');
    x := x^.next;
    counter := counter + 1;
  end;
  writeln('NIL');
  writeln('Liczba elementow listy : ',counter);
end;

procedure BSTinsert(x:PNode;var t:PNode);
begin
  if t = NIL then
    t := x
  else
    if t^.data = x^.data then
            BSTinsert(x,t^.prev)
        else if t^.data < x^.data then
            BSTinsert(x,t^.next)
        else
            BSTinsert(x,t^.prev);
end;

procedure BSTtoDLL(t:PNode;var L:PNode);
begin
   if t <> NIL then
   begin
     BSTtoDLL(t^.next,L);
     ListInsert(L,t^.data);
     BSTtoDLL(t^.prev,L);
   end;
end;

procedure BSTdispose(t:PNode);
begin
   if t <> NIL then
   begin
    BSTdispose(t^.prev);
    BSTdispose(t^.next);
    dispose(t);
   end; 
end;

procedure BSTsort(var L:PNode);
var T,S:PNode;
    x,xs:PNode;
begin
  T := NIL;
  S := NIL;
  x := L;
  while x <> NIL do
  begin
    xs := x^.next;
    x^.prev := NIL;
    x^.next := NIL;
    BSTinsert(x,t);
    x := xs;
  end;
  BSTtoDLL(T,S);
  BSTdispose(T);
  L := S;
end;

var i : byte;
    head:PNode;
    k:TData;
BEGIN
  ListInit(head);
  repeat
     writeln('0. Wyjscie');
     writeln('1. Wstaw element na poczatek listy');
     writeln('2. Usun element listy');
     writeln('3. Posortuj elementy drzewem binarnym');
     writeln('4. Wypisz elementy  listy');
     readln(i);
     case i of
     0:
     begin
       while not ListIsEmpty(head) do
            ListDelete(head,head^.data);
     end;
     1:
     begin
       writeln('Podaj element jaki chcesz wstawic');
       readln(k);
       ListInsert(head,k);
     end;
     2:
     begin
       writeln('Podaj element jaki chcesz usunac');
       readln(k);
       ListDelete(head,k);
     end;
     3:
     begin
       BSTsort(head);
     end;
     4:
     begin
        ListPrint(head);    
     end
     else
        writeln('Brak operacji podaj inny numer');
     end;
  until i = 0;  
END.

Ten kod wymaga pewnych ulepszeń.
Po pierwsze powinniśmy ograniczyć dodatkową pamięć do potrzeb rekurencyjnych,
a następnie powinniśmy spróbować zastąpić rekurencję iteracją.
Jeśli chcemy dalej ulepszać algorytm, powinniśmy użyć drzewa równoważenia

Quicksort
Może pokażę kroki do szybkiego sortowania

Jeśli lista zawiera więcej niż jeden węzeł

1. Wybór osi obrotu
   
2. Lista podziału na trzy listy
   podrzędne Pierwsza lista zawiera węzły z kluczami mniejszymi niż klucz przestawny
   Druga lista zawiera węzły z kluczami równymi kluczowi przestawnemu
   Trzecia lista zawiera węzły z kluczami większymi niż klucz przestawny
   
3. Rekurencyjne wezwania do list podrzędnych, które zawierają węzły nie równe węzłowi przestawnemu
   
4. Połącz posortowane listy podrzędne w jedną posortowaną listę
   

Ad 1.
Jeśli chcemy szybko wybrać pivot, wybór jest ograniczony.
Możemy wybrać węzeł główny lub węzeł ogonowy.
Nasza lista musi zawierać poiner do węzła, jeśli chcemy, aby nasz pivot
był dostępny szybko, w przeciwnym razie musimy wyszukać węzeł

Ad 2.
Możemy użyć operacji kolejki dla tego kroku. Najpierw usuwamy
węzeł z oryginalnej listy połączonej,
porównujemy jego klucz z kluczem przestawnym i kolejkujemy węzeł do właściwej listy
podrzędnej. Listy podrzędne są tworzone z istniejących węzłów i nie ma potrzeby
przydzielania pamięci dla nowych węzłów

Wskaźnik do węzła ogonowego będzie przydatny, ponieważ operacje kolejek
i konkatenacja przebiegają szybciej przy obecności tego wskaźnika