Quick Sort

Visual C# Tutorials

C# Tutorials

Sort Routines Bubble Sort Heap Sort Insertion Sort Merge Sort Quick Sort Selection Sort Shell Sort

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:

1. If there are one or less elements in the array to be sorted, return immediately.
2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
4. 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.

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);
            }
        }
    }