Quick Sort
| Visual C# Tutorials |
| C# Tutorials |
The quick sort is an in-place, divide-and-conquer, massively recursive sort. As a normal person would say, it's essentially a faster in-place version of the merge sort. The quick sort algorithm is simple in theory, but very difficult to put into code.
The recursive algorithm consists of four steps:
- If there are one or less elements in the array to be sorted, return immediately.
- Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
- Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
- Recursively repeat the algorithm for both halves of the original array.
The quick sort is by far the fastest of the common sorting algorithms. It is possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn't anything faster.
The quick sort is recursive, which can make it a bad choice for applications that run on machines with limited memory.
[edit]
Quick Sort Routine Code
public class QuickSort { // array of integers to hold values private int[] array = null; // number of elements in array private int x; // Quick Sort Algorithm public QuickSort() { array = new int[100]; x = array.Length; Random rand = new Random(5433); for (int i = 0; i < array.Length; i++) { array[i] = rand.Next(-100, 100); } PrintArray(); q_sort(0, x - 1); PrintArray(); } private void PrintArray() { for (int i = 0; i < array.Length - 1; i++) { Console.Write(array[i] + ", "); } Console.WriteLine(array[array.Length - 1]); } public void q_sort(int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = array[left]; while (left < right) { while ((array[right] >= pivot) && (left < right)) { right--; } if (left != right) { array[left] = array[right]; left++; } while ((array[left] <= pivot) && (left < right)) { left++; } if (left != right) { array[right] = array[left]; right--; } } array[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot) { q_sort(left, pivot - 1); } if (right > pivot) { q_sort(pivot + 1, right); } } }
|

