Today, I will show well-known sorting algorithm that is called Quick Sort.
Normally, On adverage, it uses Θ(nlogn) when compare to n items that usually better than other Θ(nlogn) algorithm but it's not stable.
Quicksort, like merge sort, is based on the divide and conquer paradigm.
Divide: Patition array into two arrays from A[p..r] into A[p..q-1] and A[q+1..r]
Conquer: Sort the two sub arrays in the recursive quick sort.
Combine: Sub arrays are sorted in place, so, no need to combine them.
In this algorothm, there are 4 regions to maintain subarray in the partition zone.
pivot || value < pivot || value > pivot || unrestricted [From left to right of subarray]
and it use pivot to compare the appropriate place to swap the pivot from the both side left and right.
For example: 3,2,6,5
pivot = 3 [index 0]
From the left : Find the first place that value is greater than pivot
left index = 1
3 > 2 move index by one
3 < 6 stop loop
-> left index = 2
From the right : Find the first plae that value is smaller than pivot
right index = 3
3 < 5 move index by minus one
3 < 6 move index by minus one
3 > 2 stop loop
-> right index = 1
You can see that if we sort in ascending order, we should swap pivot with the position of 1 in the array. Then it get 2,3,6,5.
Next, it go to recursion procedure of quicksort. From index 0-1, 2-3.
and do this again until thay can't be partitioned.
using System;
namespace Sorting
{
class Sort
{
//swap in place
private static void Swap<T>(T[] arr, int m, int n)
{
T temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
}
//normal quick sort
public static void QuickSort<T>(T[] arr) where T : IComparable
{
QuickSort(arr, 0, arr.Length-1);
}
//recursive quick sort
public static void QuickSort<T>(T[] arr, int start, int end) where T : IComparable
{
//based case
if (end <= start)
return;
//---------------- Partition ---------------------------
T pivot = arr[start]; //pivot
int i = start; //starting index
int j = end + 1; //ending index
while (i<j)
{
//searching for data that is less than pivot
while (i < end && arr[++i].CompareTo(pivot) < 0) ;
//searching for data that is greater than pivot
while (j > start && arr[--j].CompareTo(pivot) > 0) ;
//exchange data at i and j only if i < j
if (i < j)
Swap(arr, i, j);
}
//restore pivot
arr[start] = arr[j];
arr[j] = pivot;
//-----------------------------------------------------
QuickSort(arr, start, j - 1);//sort left side
QuickSort(arr, j + 1, end); //sort right side
}
static void Main(string[] args)
{
int[] a = {5,1,2,4,6,8,100,56,23,55,75,34,84,76,97,56 };
QuickSort<int>(a);
foreach (int x in a)
{
Console.WriteLine(x);
}
Console.ReadLine();
}
}
}
b2895552-7762-4a10-ad6f-cf6d08ff34bb|2|5.0