QuickSort

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Reflection;

using System.Linq.Expressions;

using System.Collections.ObjectModel;

namespace QuickSort

{

class QuickSort

{

public static void Main()

{

int[] intArray = new int[] { 6, 24, 80, 4, 19, 84, 1, 80, 10, 6, 5 };

intArray.QuickSort(0, intArray.Length - 1);

intArray.DisplayArray();

Console.ReadLine();

}

}

static class Utils

{

/// <summary>

/// 1. Choose the pivot: in this case it should be the first element

/// 2. Move elements that are smaller than the pivot to the left part of the array, and elements that are greater than the pivot to the right part of the array.

/// 3. Move the pivot element at the border between smaller and greater elements.

/// 4. Apply QuickSort recursively on the arrays situated on both sides of the pivot.

/// 5. When there are only 2 elements left compare them directly.

/// </summary>

/// <typeparam name="T">Elements of the array should implement <c>IComparable</c></typeparam>

/// <param name="array">The array to be sorted</param>

/// <param name="low">Low index of the array from where to start sorting</param>

/// <param name="high">High index of the array till where to sort</param>

public static void QuickSort<T>(this T[] array, int low, int high) where T : IComparable

{

int pivot;

if ((high - low) > 0)

{

pivot = array.partition(low, high);

array.QuickSort(low, pivot - 1);

array.QuickSort(pivot + 1, high);

}

}

/// <summary>

/// Move elements that are smaller than the pivot to the left part of the array, and elements that are greater than the pivot to the right part of the array.

/// Moves the pivot element at the border between smaller and greater elements.

/// </summary>

/// <typeparam name="T">type of elements</typeparam>

/// <param name="array">array to be sorted</param>

/// <param name="low">low index from where to start the partitioning operation</param>

/// <param name="high">High index of the array till where to partition</param>

/// <returns>Returns the position of the pivot in the array</returns>

private static int partition<T>(this T[] array, int low, int high) where T : IComparable

{

int pivot = low;

low++;

do

{

if (array[low].CompareTo(array[pivot]) > 0

&& array[high].CompareTo(array[pivot]) < 0)

{

swap(ref array[low], ref array[high]);

low++;

high--;

continue;

}

else

{

if (array[low].CompareTo(array[pivot]) <= 0)

{

low++;

}

if (array[high].CompareTo(array[pivot]) >= 0)

{

high--;

}

}

}

while (high > low);

if (high == low) high--;

swap(ref array[pivot], ref array[high]);

return high;

}

/// <summary>

/// Switch 2 elements in an array

/// </summary>

/// <typeparam name="T">type of elements of the array</typeparam>

/// <param name="t_1"></param>

/// <param name="t_2"></param>

private static void swap<T>(ref T t_1, ref T t_2)

{

T temp;

temp = t_1;

t_1 = t_2;

t_2 = temp;

}

public static void DisplayArray<T>(this T[] array)

{

foreach (var item in array)

{

Console.WriteLine(item);

}

}

}

}