A quick analysis about Quicksort

Standard

If you are a computer scientist or a computer science student and you are studying Introduction to Algorithms you may have talked about Quicksort. A lot of people has talked about this sorting algorithm or maybe you professor has taught to you. With this post I’ll do some interesting things about this algorithm and We will think about how the persons does like so much Quicksort.

As like MergeSort(maybe i will talk about MergeSort in other posts) Quicksort is a divider and conquer algorithm. Maybe the main difference between them it’s about the divide phase. In MergeSort a recursive merging  is called, when We run Quicksort the divide phase can be translated for the Partition Algorithm, that can produce two subarrays in relation a pivot, ie, a recursive partition is called. The combine phase in quicksort is trivial, because when the partition algorithm has been called it combines itself. Since the subarrays are sorted in place, no work is needed to combine them.

 

The partition algorithm can divide the array A[p…r] in two subarrays as you can see on the above picture. The partition has a linear Time Ο(n). A[p…q-1] and A[q+1…r] such that each element of  A[p…q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q+1…r]. Compute the index q as part of this partitioning procedure.

With the partition routine the Quicksort is easy.

If we will analyse the quicksort, what is your worst-case time ?

  • Input sorted or Reverse sorted
  • One side of partition has no elements.
T(n) =  T(0) + T(n-1) + θ(n)
         =  θ(1) + T(n-1) + θ(n)
         =  T(n-1)+ θ(n)
          = θ(n²)
Best-case analysis (intuition):
If we’re really luck, partition slipts the array on the middle.  We have:
T(n) = 2.T(n/2) + θ(n)
         = θ(n lg n)
Suppose, for example, that the partitioning routine always produce 9-to-1 proportional split. At first blush seems quite unbalanced. What do you think? Does the partition has lucky ? Or not ? We can analyze the recursion tree:
Thus, with a 9-to-1 proportional split at every level of recursion, which intuitively seems quite unbalanced, quicksort runs O(n lg n) time-assymptotically the same as if the splt were right down the middle.
You can see the lecture from Charles E. Leiserson – MIT  .

Advertisements