quick sort

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.


Please rate this

Leave a Reply

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


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>