Difference between revisions of "Interview Preparation Quick Sort"

Latest revision as of 11:13, 1 December 2016

Algorithm for implementation of quick sort is as follows

a. Any element can be marked as a pivot but in this algorithm, I am using the starting index as a pivot.

b. Divide the array such that, All the element that are less than pivot are kept in one part and other are kept in another part.

c. Now pivot can be placed at its position between two parts.

d. consider only left part and repeat the steps a, b and c until only one element is left.

e. consider right part and repeat step a, b ,c ,d and e until all the elements are sorted.

Code snippet

 if (start < end)
    {
        pivot = start;
        i = start;
        j = end;
        while (i < j) 
        {
            while (array[i] <= array[pivot] && i <= end)
            {
                i++;
            }
            while (array[j] > array[pivot] && j >= start)
            {
                j--;
            }
            if (i < j)
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        temp = array[j];
        array[j] = array[pivot];
        array[pivot] = temp;
        quicksort(array, start, j - 1);
        quicksort(array, j + 1, end);
}

For an array with n number of elements,

Best case complexity = Average case complexity = O(n log n).

Worst case complexity = O(n^2).