Pourquoi n'utilisons-nous pas le tri rapide sur une liste chaînée?

L'algorithme de tri rapide peut être divisé en étapes suivantes

1. Identifiez le pivot.

2. Partitionnez la liste liée en fonction du pivot.

3. Divisez la liste chaînée récursivement en 2 parties.

Maintenant, si je choisis toujours le dernier élément comme pivot, alors l'identification de l'élément pivot (1ère étape) prend du temps .$\mathcal O(n)$

Après avoir identifié l'élément pivot, nous pouvons stocker ses données et les comparer avec tous les autres éléments pour identifier le point de partition correct (2e étape). Chaque comparaison prendra fois que nous stockons les données de pivot et chaque swap prend O ( 1 ) . Donc, au total, il faut O ( n ) temps pour n éléments.$\mathcal O(1)$$\mathcal O(1)$$\mathcal O(n)$$n$

La relation de récurrence est donc:

qui est O ( n log n ) qui est le même qu'en tri par fusion avec une liste chaînée.$T(n) = 2T(n/2) + n$$\mathcal O(n \log n)$

Alors, pourquoi le tri par fusion est-il préféré au tri rapide pour les listes liées?

Le modèle d'accès à la mémoire dans Quicksort est aléatoire, l'implémentation prête à l'emploi est également en place, il utilise donc de nombreux swaps si les cellules pour obtenir le résultat ordonné.
En même temps, le tri par fusion est externe, il nécessite un tableau supplémentaire pour renvoyer le résultat ordonné. Dans le tableau, cela signifie une surcharge d'espace supplémentaire, dans le cas d'une liste liée, il est possible d'extraire de la valeur et de commencer la fusion des nœuds. L'accès est de nature plus séquentielle.

Pour cette raison, le tri rapide n'est pas un choix naturel pour la liste liée, tandis que le tri par fusion en tire un grand avantage.

La notation Landau pourrait (plus ou moins, car Quicksort est toujours ) d'accord, mais la constante est beaucoup plus élevée.$\mathcal O(n^2)$

Dans le cas moyen, les deux algorithmes sont en donc le cas asymptotique est le même, mais la préférence est strictement due à la constante cachée et parfois la stabilité est le problème (quicksort est intrinsèquement instable, mergsort est stable).$\mathcal O(n\log n)$

Vous pouvez trier rapidement les listes liées, mais vous serez très limité en termes de sélection de pivot, vous limitant aux pivots près du début de la liste, ce qui est mauvais pour les entrées presque triées, sauf si vous voulez faire une boucle sur chaque segment deux fois (une fois pour pivot et une fois pour la partition). Et vous devrez conserver une pile des limites de partition pour les listes que vous devez encore trier. Cette pile peut atteindre lorsque la sélection de pivot est mauvaise avec la complexité temporelle passant à O ( n 2 ) .$O(n)$$O(n^2)$

Le tri par fusion sur les listes liées peut être exécuté en utilisant uniquement $O(1)$

$2^{64}$$O(1)$ d'espace supplémentaire supplémentaire.

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;

C'est l'algorithme que le noyau Linux utilise pour trier ses listes chaînées. Cependant, avec quelques optimisations supplémentaires, comme ignorer le previouspointeur pendant toutes les opérations de fusion, sauf la dernière.

Vous pouvez écrire le tri par fusion, le tri par partition, le tri par arborescence et comparer les résultats
Il est assez facile de l' arbre d'écriture sorte si vous permettre un peu d' espace supplémentaire
pour l' arbre trier chaque nœud de liste chaînée doit avoir deux pointeurs , même si l' on liste chaînée sorte séparément
Dans liste chaînée je préfère insérer et supprimer au lieu d'échanger
la partition Hoare ne peut être effectuée que pour la liste doublement liée

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.

Ce code a besoin d'améliorations
Tout d'abord, nous devons limiter le stockage supplémentaire aux besoins de récursivité,
puis nous devons essayer de remplacer la récursivité par l'itération
Si nous voulons améliorer encore l'algorithme, nous devons utiliser un arbre d'auto-équilibrage

Tri rapide
Peut-être que je montrerai les étapes du quicksort

Si la liste contient plusieurs nœuds

1. Sélection de pivot
   
2. Liste des partitions en trois sous-listes La
   première sous-liste contient des nœuds avec des clés inférieures à la clé pivot La
   deuxième sous-liste contient des nœuds avec des clés égales à la clé pivot
   troisième sous-liste contient des nœuds avec des clés supérieures à la clé pivot
   
3. Appels récursifs pour les sous-listes qui contiennent des nœuds non égaux au nœud pivot
   
4. Concaténer les sous-listes triées en une seule liste triée
   

Annonce 1.
Si nous voulons choisir le pivot rapidement, le choix est limité
Nous pouvons choisir le nœud principal ou le nœud arrière
Notre liste doit avoir un pointeur sur le nœud si nous voulons que notre pivot
soit accessible rapidement sinon nous devons rechercher le nœud

Annonce 2.
Nous pouvons utiliser les opérations de file d'attente pour cette étape.
Fist, nous retirons le nœud de la liste chaînée d'origine,
comparons sa clé avec la clé pivot et le nœud de mise en file d'attente à la sous-liste correcte.
listes sont créées à partir des nœuds existants et il n'est pas nécessaire de
allouer de la mémoire pour les nouveaux nœuds.

Le pointeur vers le nœud de queue sera utile car les opérations de file d'attente
et la concaténation s'exécutent plus rapidement avec la présence de ce pointeur