Quicksort на списках

Нашло чего-то такое, декадентское сегодня... Наверное, заработался...

Все мы прекрасно знаем быструю сортировку -  quicksort, которая обычно применяется к массивам. Все мы также прекрасно знаем самые разные списки. А как насчет быстрой сортировки на списках? Я еще не понял, это изящество или извращение, но что-то такое этакое в этом есть...

В общем, получился вот такой "шедевр"...

using System;

using System.IO;

 

namespace ListQuickSort

{

    class List

    {

        static void Assert(bool cond, string message)

        {

            if (!cond) throw new Exception(message);

        }

 

        private class ListElem

        {

            public int value;

            public ListElem next;

        }

 

 

        public List()

        {

        }

 

        public void QuickSort()

        {

            QuickSort(ref head, ref end);

        }

 

        private int count;

 

        private void QuickSort(ref ListElem head, ref ListElem end)

        {

            if (head == null || head.next == null) return;

            int pivot = head.value;

            ListElem low = null;

            ListElem high = null;

            ListElem lowEnd = null;

            ListElem highEnd = null;

            if (pivot >= head.next.value)

            {

                high = head;

                highEnd = head;

                low = head.next;

                lowEnd = head.next;

            }

            else

            {

                low = head;

                lowEnd = head;

                high = head.next;

                highEnd = head.next;

            }

            head = head.next.next;

            low.next = null; high.next = null;

            while (head != null)

            {

                ListElem cur = head;

                head = head.next;

                cur.next = null;

                if (cur.value < pivot)

                {

                    cur.next = low;

                    low = cur;

                }

                else

                {

                    cur.next = high;

                    high = cur;

                }

            }

            QuickSort(ref high, ref highEnd);

            QuickSort(ref low, ref lowEnd);

            highEnd.next = low;

            head = high;

            end = lowEnd;

        }

 

        public void Insert(int v)

        {

            ListElem newElem = new ListElem();

            newElem.value = v;

            if (head == null)

            {

                head = current = end = newElem;

            }

            else

            {

                newElem.next = head;

                head = newElem;

            }

        }

 

        public bool Reset()

        {

            current = head;

            return current != null;

        }

 

        public bool Next()

        {

            if (current != null) current = current.next;

            return current != null;

        }

 

        public int Current { get { return current.value; } }

 

        ListElem head = null;

        ListElem current = null;

        ListElem end = null;

    }

 

 

    class Program

    {

        static List ReadList(string fileName)

        {

            List list = new List();

            FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read);

            StreamReader sr = new StreamReader(fs);

            while (!sr.EndOfStream)

            {

                string line = sr.ReadLine();

                list.Insert(Convert.ToInt32(line));

            }

            sr.Close();

            return list;

        }

 

        static void PrintList(List list)

        {

            bool f = list.Reset();

            while (f)

            {

                Console.Write("{0} ", list.Current);

                f = list.Next();

            }

            Console.WriteLine();

        }

 

        static void Main(string[] args)

        {

            if (args.Length < 1)

            {

                Console.WriteLine("Please, specify the file");

                return;

            }

            List list = ReadList(args[0]);

            PrintList(list);

            list.QuickSort();

            PrintList(list);

        }

    }

}

 

***


blog comments powered by Disqus