Trier une liste chaînée

J'ai écrit une classe de liste liée de base en C#. Il a un objet Node, qui (évidemment) représente chaque nœud de la liste.

Le code n'utilise pas IEnumerable, cependant, puis-je implémenter une fonction de tri? Le langage que j'utilise est C#. Existe-t-il un exemple de cela en C #?

Je travaille à partir de cet échantillon:

Merci

Solution du problème

Quicksort fonctionnel et Mergesort

Voici une liste chaînée avec des méthodes de tri rapide et de tri par fusion écrites dans un style fonctionnel :

class List
{
 public int item;
 public List rest;
 public List(int item, List rest)
 {
 this.item = item;
 this.rest = rest;
 }
 // helper methods for quicksort
 public static List Append(List xs, List ys)
 {
 if (xs == null) return ys;
 else return new List(xs.item, Append(xs.rest, ys));
 }
 public static List Filter(Func<int,bool> p, List xs)
 {
 if (xs == null) return null;
 else if (p(xs.item)) return new List(xs.item, Filter(p, xs.rest));
 else return Filter(p, xs.rest);
 }
 public static List QSort(List xs)
 {
 if (xs == null) return null;
 else
 {
 int pivot = xs.item;
 List less = QSort(Filter(x => x <= pivot, xs.rest));
 List more = QSort(Filter(x => x > pivot, xs.rest));
 return Append(less, new List(pivot, more));
 }
 }
 // Helper methods for mergesort
 public static int Length(List xs)
 {
 if (xs == null) return 0;
 else return 1 + Length(xs.rest);
 }
 public static List Take(int n, List xs)
 {
 if (n == 0) return null;
 else return new List(xs.item, Take(n - 1, xs.rest));
 }
 public static List Drop(int n, List xs)
 {
 if (n == 0) return xs;
 else return Drop(n - 1, xs.rest);
 }
 public static List Merge(List xs, List ys)
 {
 if (xs == null) return ys;
 else if (ys == null) return xs;
 else if (xs.item <= ys.item) return new List(xs.item, Merge(xs.rest, ys));
 else return new List(ys.item, Merge(xs, ys.rest));
 }
 public static List MSort(List xs)
 {
 if (Length(xs) <= 1) return xs;
 else
 {
 int len = Length(xs) / 2;
 List left = MSort(Take(len, xs));
 List right = MSort(Drop(len, xs));
 return Merge(left, right);
 }
 }
 public static string Show(List xs)
 {
 if(xs == null) return "";
 else return xs.item.ToString() + " " + Show(xs.rest);
 }
}

Tri en tas fonctionnel à l'aide d'un tas d'appariement

Bonus : tri en tas (utilisant le tas d'appariement fonctionnel).

class List
{
 //...
 public static Heap List2Heap(List xs)
 {
 if (xs == null) return null;
 else return Heap.Merge(new Heap(null, xs.item, null), List2Heap(xs.rest));
 }
 public static List HSort(List xs)
 {
 return Heap.Heap2List(List2Heap(xs));
 }
}
class Heap
{
 Heap left;
 int min;
 Heap right;
 public Heap(Heap left, int min, Heap right)
 {
 this.left = left;
 this.min = min;
 this.right = right;
 }
 public static Heap Merge(Heap a, Heap b)
 {
 if (a == null) return b;
 if (b == null) return a;
 Heap smaller = a.min <= b.min? a: b;
 Heap larger = a.min <= b.min? b: a;
 return new Heap(smaller.left, smaller.min, Merge(smaller.right, larger));
 }
 public static Heap DeleteMin(Heap a)
 {
 return Merge(a.left, a.right);
 }
 public static List Heap2List(Heap a)
 {
 if (a == null) return null;
 else return new List(a.min, Heap2List(DeleteMin(a)));
 }
}

Pour une utilisation réelle, vous souhaitez réécrire les méthodes d'assistance sans utiliser la récursivité, et peut-être utiliser une liste modifiable comme celle intégrée.

Comment utiliser:

List xs = new List(4, new List(2, new List(3, new List(1, null))));
Console.WriteLine(List.Show(List.QSort(xs)));
Console.WriteLine(List.Show(List.MSort(xs)));
Console.WriteLine(List.Show(List.HSort(xs)));

Tri rapide sur place impératif pour les listes liées

Une version sur place a été demandée. Voici une mise en œuvre très rapide. J'ai écrit ce code de haut en bas sans chercher d'opportunités pour améliorer le code, c'est-à-dire que chaque ligne est la première qui me vient à l'esprit. C'est extrêmement moche parce que j'ai utilisé null comme liste vide:) L'indentation est incohérente, etc.

De plus, j'ai testé ce code sur un seul exemple :

 MList ys = new MList(4, new MList(2, new MList(3, new MList(1, null))));
 MList.QSortInPlace(ref ys);
 Console.WriteLine(MList.Show(ys));

Comme par magie, cela a fonctionné la première fois ! Je suis à peu près sûr que ce code contient des bogues cependant. Ne me tenez pas responsable.

class MList
{
 public int item;
 public MList rest;
 public MList(int item, MList rest)
 {
 this.item = item;
 this.rest = rest;
 }
 public static void QSortInPlace(ref MList xs)
 {
 if (xs == null) return;
 int pivot = xs.item;
 MList pivotNode = xs;
 xs = xs.rest;
 pivotNode.rest = null;
 // partition the list into two parts
 MList smaller = null; // items smaller than pivot
 MList larger = null; // items larger than pivot
 while (xs!= null)
 {
 var rest = xs.rest;
 if (xs.item < pivot) {
 xs.rest = smaller;
 smaller = xs;
 } else {
 xs.rest = larger;
 larger = xs;
 }
 xs = rest;
 }
 // sort the smaller and larger lists
 QSortInPlace(ref smaller);
 QSortInPlace(ref larger);
 // append smaller + [pivot] + larger
 AppendInPlace(ref pivotNode, larger);
 AppendInPlace(ref smaller, pivotNode);
 xs = smaller;
 }
 public static void AppendInPlace(ref MList xs, MList ys)
 {
 if(xs == null){
 xs = ys;
 return;
 }
 // find the last node in xs
 MList last = xs;
 while (last.rest!= null)
 {
 last = last.rest;
 }
 last.rest = ys;
 }
 public static string Show(MList xs)
 {
 if (xs == null) return "";
 else return xs.item.ToString() + " " + Show(xs.rest);
 }
}