Quick Sort

Quick Sort is an efficient divide and conquer algorithm performed in two phases – partition and sorting phase.

Here are few pointers to remember about Quick Sort:

  • Partitioning places all the elements less than the pivot in the left part of the array and greater elements in the right part
  • Pivot element stays in its place
  • After partitioning no element moves to the other side, of the pivot
    • This allows you to sort the elements, to the left or right of the pivot, independent of the other side
  • Complexity is O(n log n)
  • Often fast for small arrays with a few distinct values, repeated many times
  • It is a conquer-and-divide algo; with most of the work happening during partitioning phase
  • If you had to choose the optimum pivot then it should the median of the given array
  • Not a stable sort

Testing Notes

  • Currently we have only one version of the code. We may try to do another version that is not recursive because putting the functions on stack will take up some memory and time
  • Another version could be trying to use the pivot from the middle and then compare how do the random numbers compare against the sorted numbers

Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

Numbers

# of Items in Array Time Taken Average for 100 numbers
Random 10 0.072972 0.72972
1K 2.74698 0.274698
1M 4640.77 0.464077
Sorted 10 0.042773 0.42773
1K 1.84335 0.184335
1M 2473.42 0.247342
Advertisements

One thought on “Quick Sort

  1. Pingback: Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort |

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s