QUICK SORT

Like Merge Sort ,Quick-sort is a divide and conquer algorithm.it picks an element as pivot and partitions the given array around the picked pivot. 
There are a number of ways to pick the pivot element for example,we will use the 1st element in the array as pivot.

1. Move left index until we find an element > pivot.
2. Move right index until we find an element < pivot.
3. If indexes have not crossed, swap values and repeat step1 & step2.
4. If indexes have crossed swap pivot & left index.

If array  only contains one element,return
else

• Pick one element to use pivot.
• partition element into two sub-arrays.

              1. Elements less than or equal to pivot.

            2. Elements greater than pivot.

• Quick-sort two sub-arrays.
• Return result.

EXAMPLE

Consider the following example.

        

Pass 1:

      

swap(i,j)

      

swap(i,j)

      

swap (i,j)

      

swap (i,j)

     

'i' and 'j' cross over ,in this type we swap(p,j)  

         

if 'i' >= 'j' then break,

Result of pass 1:Three sub-blocks.

             

    This block of elements are processed in the same fashion and eventually all the elements are placed at appropriate position. Then we get the answer like this.

            

Worst case time complexity[Big-O]:O(n^2)

Best case time complexity[Big-omega]:O(n*log n)

Average time complexity[Big-theta]:O(n*log n)

Advantages:

• It is one of the fastest sorting algorithm.
• Its implementation does not require any additional memory.

Disadvantages:

• The worst case efficiency of O(n^2) is not well suited for large sized list.
• Its algorithm is considered as a little more complex in comparison to some other sorting technique. 

                                   *****