The QuickSort Algorithm

QuickSort is a particularly effective and popular sorting algorithm. It is a divide-and-conquer algorithm, working by splitting the data into two parts and then sorting them recursively. Being recursive, it is often hard to visualise what the algorithm is doing.

Here is the pseudocode algorithm for QuickSort:

 
 quicksort(a[], p, r)
           if r>p then
      j=partition(a[], p, r)
      quicksort(a[], p, j-1)
           quicksort(a[], j+1, r)


      partition(a[], p, r)
          i=p
          j=r+1
          pivot=a[p]
          do { 
               do i=i+1 while (a[i]<pivot)
               do j=j-1 while (a[j]>pivot)
               if (i<j) exchange(a[i], a[j])
             }while (i<j)
          exchange(a[p], a[j])
          return j

The Partition method receives a list or sublist, and places the first element in its correct position within the list. It also ensures that all elements to the left of this are smaller, and all to the right are larger.

The best and average cases of Quicksort take O(nlogn) time.

Go to QuickSort demonstration