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