Показаны сообщения с ярлыком QSort. Показать все сообщения
Показаны сообщения с ярлыком QSort. Показать все сообщения

вторник, 7 апреля 2009 г.

Экономим байты исходного кода. Реализация алгоритма QSort

Однажды, когда я проходил трейнинг по C#, нам было задано домашние задание, одним из пунктов которого было реализовать алгоритм быстрой сортировки(QSort) на C#. По достаточно хорошему описанию алгоритма на страницах Википедии, я все-таки реализовал алгоритм по-своему, но решил продолжить поиск наиболее «короткого» решении. И я его нашел. Следующий код написан на языке Perl, и это то, к чему нужно стремиться:

sub qsort {
return () if !@_;
return (qsort(grep { $_ < $_[0] } (@_)[1..$#_]), $_[0],
qsort(grep { $_ >= $_[0] } (@_)[1..$#_]));
}


Превосходно! Реализация алгоритма наглядна и прекрасно запоминается. Я попытался переписать исходный код с Perl на C#, и вот что у меня получилось:

public static List<T> QSort<T>(List<T> sourceArray)
where T : IComparable<T>
{
if ( sourceArray.Count == 0 )
{
return new List<T>();
}
T firstItem = sourceArray[0];
sourceArray.RemoveAt(0);

List<T> greaterList = new List<T>();
List<T> lessList = new List<T>();
List<T> sortedArray = new List<T>();


foreach (T item in sourceArray)
{
if (item.CompareTo(firstItem) < 0) lessList.Add(item);
}

foreach (T item in sourceArray)
{
if (item.CompareTo(firstItem) >= 0) greaterList.Add(item);
}

sortedArray.AddRange(QSort(lessList));
sortedArray.Add(firstItem);
sortedArray.AddRange(QSort(greaterList));

return sortedArray;
}


Вроде бы ничего, по крайней мере, задание сдал. Но, вот недавно я увидел следующее решение на C#:

public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list)
where T : IComparable
{
if (!list.Any())
{
return Enumerable.Empty<T>();
}
var pivot = list.First();
var smaller = list.Where(item => item.CompareTo(pivot) <= 0).QuickSort();
var larger = list.Where(item => item.CompareTo(pivot) > 0).QuickSort();

return smaller.Concat(new[] {pivot}).Concat(larger);
}


Кто короче?! ;)
 

.NET ate my MOSK;. Powered By Blogger © 2009 Bombeli | Theme Design: ooruc