Quick Sort

Quicksort or partition-exchange sort is aptly named because, when properly implemented, it is the fastest known general-purpose in-memory sorting algorithm in the average case. Quick sort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items.

In the worst case, it makes O(n2) comparisons, though this behaviour is rare. Quicksort is often faster in practice than other O(n log n) algorithms. It does not require the extra array. Quicksort is widely used, and is typically the algorithm implemented in a library sort routine such as the UNIX qsort function.

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

function quicksort(array)
    if length(array) > 1
        pivot = select any element of array
        left = first index of array
        right = last index of array
        while left <= right
            while array[left] < pivot
                left = left + 1
            while array[right] > pivot
                right = right - 1
            if left <= right
                swap array[left] with array[right]
                left = left + 1
                right = right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

Comments (0)

  • To add your comment please or

We use cookies to improve your experience on our site and to show you personalised advertising. Please read our cookie policy and privacy policy.

Got It!