@margaret

Вот пример реализации сортировки Хоара для связанного списка в C#:

using System;

class LinkedListNode
{
    public int Value;
    public LinkedListNode Next;
}

class LinkedList
{
    public LinkedListNode Head;

    public void Add(int value)
    {
        var newNode = new LinkedListNode { Value = value };

        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            var current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    public void Sort()
    {
        if (Head == null || Head.Next == null)
        {
            return; // Already sorted or empty list
        }

        Head = Sort(Head);
    }

    private LinkedListNode Sort(LinkedListNode head)
    {
        if (head == null || head.Next == null)
        {
            return head; // Sorted list
        }

        LinkedListNode pivot = head;
        LinkedListNode lesserHead = null;
        LinkedListNode lesserTail = null;
        LinkedListNode greaterHead = null;
        LinkedListNode greaterTail = null;
        LinkedListNode current = head.Next;

        while (current != null)
        {
            LinkedListNode next = current.Next;

            if (current.Value < pivot.Value)
            {
                if (lesserHead == null)
                {
                    lesserHead = current;
                    lesserTail = current;
                }
                else
                {
                    lesserTail.Next = current;
                    lesserTail = current;
                }
            }
            else
            {
                if (greaterHead == null)
                {
                    greaterHead = current;
                    greaterTail = current;
                }
                else
                {
                    greaterTail.Next = current;
                    greaterTail = current;
                }
            }

            current = next;
        }

        if (lesserTail != null)
        {
            lesserTail.Next = null;
        }

        if (greaterTail != null)
        {
            greaterTail.Next = null;
        }

        LinkedListNode sortedLesser = Sort(lesserHead);
        LinkedListNode sortedGreater = Sort(greaterHead);

        if (sortedLesser == null)
        {
            head = pivot;
        }
        else
        {
            head = sortedLesser;
            LinkedListNode tail = head;
            while (tail.Next != null)
            {
                tail = tail.Next;
            }
            tail.Next = pivot;
        }

        pivot.Next = sortedGreater;

        return head;
    }
}

class Program
{
    static void Main()
    {
        var list = new LinkedList();
        list.Add(10);
        list.Add(5);
        list.Add(7);
        list.Add(3);
        list.Add(8);

        Console.WriteLine("Before sorting:");
        PrintList(list);

        list.Sort();

        Console.WriteLine("After sorting:");
        PrintList(list);
    }

    static void PrintList(LinkedList list)
    {
        var current = list.Head;
        while (current != null)
        {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

В данном примере класс LinkedList представляет связанный список, а класс LinkedListNode представляет узел списка. Метод Sort реализует сортировку Хоара (быструю сортировку) для связанного списка.

Пример вывода:

Before sorting:
10 5 7 3 8 
After sorting:
3 5 7 8 10

#translation