Quick Sort :
Quick Sort is a Divide and conquer algorithm, It divides the collection int to two sub sets based on the pivot element selected, one subset is a collection elements which is smaller than pivot, another subset is collection of elements consists of larger than pivot.then each subsets are undergoes following steps again.Entire sort can be done in O(log n)
Steps :
1. Consider a element as Pivot from the List.
2. ReOrder the list so the elements which are lesser than pivot arrange previous in the order of the pivot and the elements which are higher than pivot arrange next in the order of the pivot.
3. Recursively apply the above steps to each two subsets individually.
Algorithm :
function quicksort('array')
if length('array') ≤ 1
return 'array'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), list('pivot'), quicksort('greater'))
Now Let we see this implementation in C#
First Derive a Generic List<T> which is comparable, Then add collection to it ,Add a additional method to it as Order to order a collection based on the Quick Sort by implementing the algorithm. Following type in Generic so any data type can be sorted using this.
class Quicksort<T>:List<T> where T : IComparable
{
public List<T> Order()
{
return SortList(this.ToList<T>());
}
public List<T> SortList(List<T> values)
{
List<T> _left = new List<T>();
List<T> _right = new List<T>();
if (values.Count() > 1)
{
T pivot = values[values.Count - 1];
values.RemoveAt(values.Count - 1);
foreach (T each in values)
{
if (each.CompareTo(pivot) == 1)
{
_right.Add(each);
}
else
{
_left.Add(each);
}
}
return MergeList(SortList(_left), pivot, SortList(_right));
}
return values;
}
private List<T> MergeList(List<T> left, T pivot, List<T> right)
{
left.Add(pivot);
left.AddRange(right);
return left;
}
}
class Program
{
static void Main(string[] args)
{
Quicksort<int> _sorting = new Quicksort<int>();
_sorting.AddRange(new int[] { 3,1,8,45,2,5,7});
Console.WriteLine("Ordering the numbers using Quick Sort");
foreach (int s in _sorting.Order())
{
Console.WriteLine(s);
}
Quicksort<string> _names = new Quicksort<string>();
_names.AddRange(new string[]{"Rajesh","Suresh","Pavi","Anna","Ganesh","Sathish","Kani","Hanish","Babu","Dilli"});
Console.WriteLine();
Console.WriteLine("Ordering the names using Quick Sort");
foreach (string s in _names.Order())
{
Console.WriteLine(s);
}
Console.Read();
}
}
Output :
From this article you can learn the Generic Quick Sorting algorithm in C# and the process of algorithm.
No comments:
Post a Comment