Quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than merge sort and about two or three times faster than heapsort. see the Wikipedia article.
The solution of this algorithm can be found on the web and I add it because I want to have it here.
I add some comments for a better understanding of this algorithm.
You can test this algorithm with a matrix with distinct numbers, otherwise, it blocks with the error: Fatal Error: Execution time limit was exceeded
Let’s see the source code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | using System; public class Program { // Divides array into two partitions static public int Partition(int[] arr, int left, int right) { int pivot; pivot = arr[left]; while (true) { while (arr[left] < pivot) { left++; } while (arr[right] > pivot) { right--; } if (left < right) { int temp = arr[right]; arr[right] = arr[left]; arr[left] = temp; } else { return right; } } } // Sorts a (portion of an) array, divides it into partitions, then sorts those static public void quickSort(int[] arr, int left, int right) { int pivot; if (left < right) { pivot = Partition(arr, left, right); if (pivot > 1) { quickSort(arr, left, pivot - 1); } if (pivot + 1 < right) { quickSort(arr, pivot + 1, right); } } } public static void Main() { Console.WriteLine("QuickSort algorithm"); int[] arr = {76, 1, 33, 4, 44, 3, 2, 0}; int n = 8, i; Console.WriteLine("Quick Sort"); Console.Write("Initial array is: "); for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); } quickSort(arr, 0, 7); Console.Write("\nSorted Array is: "); for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); } } } |
The result of this program is:
1 2 3 4 | QuickSort algorithm Quick Sort Initial array is: 76 1 33 4 44 3 2 0 Sorted Array is: 0 1 2 3 4 33 44 76 |