Quick Sort

Algorithm :
QUICK SORT (A,p,r)
1 if p < r
2 then q<-- PARTITION(A,p,r)
3 QUICK SORT(A,p,q)
4 QUICK SORT(A,q + 1,r)
Notice that we only examine elements by comparing them to other elements. This makes quicksort a comparison sort. Divide and Conquer Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved. in place In place sorting algorithms don't require additional temporary space to store elements as they sort; they use the space originally occupied by the elements. Analysis : The best-case behavior of the quicksort algorithm occurs when in each recursion step the partitioning produces two parts of equal length. In order to sort n elements, in this case the running time is in Θ(n log(n)). This is because the recursion depth is log(n) and on each level there are n elements to be treated (Figure 2 a). The worst case occurs when in each recursion step an unbalanced partitioning is produced, namely that one part consists of only one element and the other part consists of the rest of the elements (Figure 2 c). Then the recursion depth is n-1 and quicksort runs in time Θ(n2). The choice of the comparison element x determines which partition is achieved. Suppose that the first element of the sequence is chosen as comparison element. This would lead to the worst case behavior of the algorithm when the sequence is initially sorted. Therefore, it is better to choose the element in the middle of the sequence as comparison element. Even better would it be to take the n/2-th greatest element of the sequence (the median). Then the optimal partition is achieved. Actually, it is possible to compute the median in linear time [AHU 74]. This variant of quicksort would run in time O(n log(n)) even in the worst case. However, the beauty of quicksort lies in its simplicity. And it turns out that even in its simple form quicksort runs in O(n log(n)) on the average. Moreover, the constant hidden in the O-notation is small. Therefore, we trade this for the (rare) worst case behavior of Θ(n2).

Java Code :

void quicksort(int[] a, int low, int high) {

   if (low > high)
 return;

  int i = low;
  int j = high;
  int h;
  // comparision element
  int x = a[(low + high) / 2];
  // partition
  do {
   while (a[i] < x)
    i++;
   while (a[j] > x)
    j--;
   if (i <= j) {
    h = a[i];
    a[i] = a[j];
    a[j] = h;
    i++;
    j--;
   }
  } while (i <= j);
   quicksort(a, low, j);
   quicksort(a, i, high);
 }