A few days ago I had an interview on a c# programmer vacancy (already received a refuse letter ) On the interview I was asked to implement a

Here is the

That's enough for theory, here is

**QuickSort**algorithm and I couldn't do that, so now I want to help you not to repeat my mistake and get the understanding of this algorithm before you'll need it.### Simple Algorithm

- Pick an element from the list (usually the most left element is used). This element will serve as a
**pivot**point - Reorder the list so that all elements with values
**less**than the pivot come**before**the pivot, while all elements with values**greater**than the pivot come**after it**(equal values can go either way). This is called the**partition operation**. -
**Recursively**repeat the algorithm for both halves of the original array.

### Pseudo Code

Here is the

**Pseudo code**for better understanding:Code:

functionquicksort(array)varlistless, greateriflength(array) ≤ 1returnarray select and remove a pivot valuepivotfrom arrayfor eachxinarrayifx ≤ pivotthenappend x to lesselseappend x to greaterreturnconcatenate(quicksort(less), pivot, quicksort(greater))

### C# Implementation

That's enough for theory, here is

**my implementation**of this in C#:Code:

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace sortQuick { class quickSort { // this is our array to sort private int[] arr = new int[20]; // this holds a number of elements in array private int len; // Quick Sort Algorithm public void QuickSort() { sort(0, len - 1); } public void sort(int left, int right) { int pivot, l_holder, r_holder; l_holder = left; r_holder = right; pivot = arr[left]; while (left < right) { while ((arr[right] >= pivot) && (left < right)) { right--; } if (left != right) { arr[left] = arr[right]; left++; } while ((arr[left] <= pivot) && (left < right)) { left++; } if (left != right) { arr[right] = arr[left]; right--; } } arr[left] = pivot; pivot = left; left = l_holder; right = r_holder; if (left < pivot) { sort(left, pivot - 1); } if (right > pivot) { sort(pivot + 1, right); } } public static void Main() { quickSort q_Sort = new quickSort(); int[] arr = {4,3,1,4,6,7,5,4,3,5,6,87,8}; q_Sort.arr = arr; q_Sort.len = q_Sort.arr.Length; // Sort the array q_Sort.QuickSort(); for (int j = 0; j < q_Sort.len; j++) { Console.WriteLine(q_Sort.arr[j]); } Console.ReadKey(); } } }

shabbir
like this