Chinese Yellow Pages | Classifieds | Knowledge | Tax | IME

Quick sort

High level code are quite simple ( divide/conque, recursively partition the array):

void quickSort(int arr[], int low, int high)
    if (low < high)
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);

The key is how to partition in-place?

Here a  pretty good quick sort ( random pivot ) video , keep l, r index

There are some other partition strategy like always choose the last or first element.

Leave a Reply

Your email address will not be published. Required fields are marked *