728x90 AdSpace

Latest Article

How to use Quick sort / Partition Exchange Sort effecient algorithms for sorting?


Quick sort is one of the most effecient algorithms for sorting. It is also called as Partition Exchange Sort. We are given an array of integers arr consisting of n elements which is desired to be sorted. Now an element of the array x is selected (any element of the array may be selected) and its position is adjusted in a way that all elements smaller than the selected are to the left of the array and all elements greater to the selected element are on its right side. This means that in a completely sorted version of the array, x will be in the same position as the one we have chosen for it. Let us call this position i. Now if we sort the subarrays (arr [0] to arr [i-1]) and (arr [i+1] to arr [n-1]) are sorted we will get a full sorted array. We can use the same technique to sort the two subarrays. Thus quick sort can also be easily viewed as a recursive algorithm. The breaking condition will again be a subarray having a single element.
Let us consider a case, that we have to sort an array whose lower bound is lower and upper bound is upper. Now an algorithm to sort this array using merge sort will be:
          If( lower > = upper)
                       array is already sorted
           else {
i) select the element to be placed in its proper position
ii) perform the partitioning operation that positions the selected element properly
iii)quick sort the subarray from lower to i-1
iv)quick sort the subarray from i+1 to upper

Now we use an example to illustrate the above algorithm. We have an array 23, 44, 9, 3, 89, 32. Let us assume that we always select the first element that has to be positioned properly.
Now original array is                       23 44 9 3 89 32
After positioning 23 in its proper place, we get   (9 3) 23 (44 89 32)
Now repeating the process for subarray1, we select 9 and partition the array. We get
(3) 9 23 (44 89 32)
and then a single element array is already sorted, we have     3 9 23 44 89 32
Now repeating the process for subarray2, we select 44 and partition the array. We get
3 9 23 (32) 44 (89)
Now as single element array is considered sorted, we get the entire array sorted in two more steps:
3 9 23 32 44 (89)
and      3 9 23 32 44 89
So all we need is to find a mechanism that performs the partition operation. One way to do this is by using two pointers up and down which are initialized to the upper and lower values. Let pivot be the value of the element that has to be positioned properly. Now following algorithm results in the partition of the array:
  1. While(arr[down]<= pivot), increment the pointer down
  2. While(arr[up]>= pivot), decrement the pointer down
  3. If (up > down), swap arr[down] and arr[up] and repeat steps i to iii
  4. else swap x[up] with pivot, and the operation is completed. 
no image
  • Title : How to use Quick sort / Partition Exchange Sort effecient algorithms for sorting?
  • Posted by :
  • Date : 07:03
  • Labels :

  • Blogger Comments
  • Facebook Comments


Post a Comment