c# - リンクされたリストの並べ替え

Question

C# で基本的なリンク リスト クラスを作成しました。リスト内のすべてのノードを (明らかに) 表す Node オブジェクトがあります。

このコードでは IEnumerable を使用していませんが、並べ替え機能を実装できますか? 使用言語はC#です。C#でこれの例はありますか?

私はこのサンプルから作業しています:

ありがとう

Answer 1

機能的なクイックソートとマージソート

これは、機能的なスタイルで書かれたクイックソートとマージソートのメソッドを含むリンクされたリストです:

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);
    }
}

ペアリング ヒープを使用した関数型ヒープソート

おまけ: ヒープソート (機能的なペアリング ヒープを使用)。

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)));
    }
}

実際に使用するには、再帰を使用せずにヘルパー メソッドを書き直し、組み込みリストのような変更可能なリストを使用することをお勧めします。

使い方：

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)));

リンクされたリストの命令型インプレース クイックソート

インプレース バージョンが要求されました。これは非常に迅速な実装です。私はコードを改善する機会を探すことなく、このコードを上から下に書きました。つまり、すべての行が頭に浮かんだ最初の行です。null を空のリストとして使用したため、非常に醜いです:)インデントに一貫性がないなど。

さらに、このコードを 1 つの例だけでテストしました。

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

魔法のように初めてうまくいきました！ただし、このコードにはバグが含まれていると確信しています。私に責任を負わせないでください。

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);
    }
}

Answer 2

もちろん、単純なリンク リストを使用して並べ替え関数を実装することもできます。マージ ソートは試してみるのに適したアルゴリズムかもしれません。かなり単純です。

Answer 3

これは最善の解決策ではないかもしれませんが、思いつく限り簡単です。誰かがもっとシンプルで高速なものを思いつくことができたら、ぜひ聞いてみたいです.
申し訳ありませんが、翻訳する必要があるのは C++ です。

List * SortList(List * p_list)
{
     if(p_list == NULL || p_list->next == NULL) 
          return p_list;

     List left, right;
     List * piviot = p_list;
     List * piviotEnd = piviot;
     List * next = p_list->next;
     do
     {
              p_list = next;
              next = next->next;
              //FIGURE OUT WHICH SIDE I'M ADDING TO.
              if(p_list->data > piviot->data ) 
                  right.InsertNode(p_list);
              else if(p_list->data < piviot->data)
                  left.InsertNode(p_list);
              else
              {   //we put this in it's own list because it doesn't need to be sorted
                  piviotEnd->next = p_list;
                  piviotEnd= p_list;
              }  
     }while(next);

     //now left contains values < piviot and more contains all the values more
     left.next = SortList(left.next);
     right.next = SortList(right.next);

     //add the piviot to the list then add the rigth list to the full list
     left.GetTail()->next = piviot;
     piviotEnd->next = right.next;

     return left.next;
}

Answer 4

for(int i=0; i<counter;i++)
{
  while(current.next!=null)
  {
    if(current.elemen>current.next.element)
    {
      Swap(current.elment,current.next.element);
    }
    current=current.next;
  }
}

リンクリストに要素を追加または挿入するときにカウンターをインクリメントする

Answer 5

リンクされたリストを回避するのではなく、リンクされたリストを使用しているという事実を実際に利用したい場合は、挿入ソートをお勧めします。

通常、挿入ソートはあまり効率的ではありませんO(n^2)。最悪の場合、リンク リストを使用すると、これを改善できます。O(n log n)

擬似：

for i in range (1,n):
    item = arr[i]
    location = binary_search(l=root, r=i, value=item.val)  // O(log i)
    insert_item_before(arr[location], item) // O(1)

通常のアルゴリズムO(i)では、より大きなすべてのアイテムをシフトする必要があるため、挿入部分がかかりますitem。リンクされたリストを使用すると、シフトせずに挿入できるため、バイナリ検索で場所を検索できるため、挿入部分はO(log i)

注: 通常、挿入ソートはO(n)最良の場合 (配列がソートされている場合) にパフォーマンスを発揮します。O(log n)残念ながら、バイナリ検索は常にステップを踏むため、ここではそうではありません。

Answer 6

public LinkedListNode<int> Sort2(LinkedListNode<int> head, int count)
    {
        var cur = head;
        var prev = cur;
        var min = cur;
        var minprev = min;

        LinkedListNode<int> newHead = null;
        LinkedListNode<int> newTail = newHead;

        for (int i = 0; i < count; i++)
        {
            cur = head;
            min = cur;
            minprev = min;

            while (cur != null)
            {
                if (cur.Value < min.Value)
                {
                    min = cur;
                    minprev = prev;
                }
                prev = cur;
                cur = cur.Next;
            }

            if (min == head)
                head = head.Next;
            else if (min.Next == null)
                minprev.Next = null;
            else
                minprev.Next = minprev.Next.Next;

            if (newHead != null)
            {
                newTail.Next = min;
                newTail = newTail.Next;
            }
            else
            {
                newHead = min;
                newTail = newHead;
            }
        }
        return newHead;
    }