Quick Sort (optimized partition algorithm)

Home           Algorithms Home

This is a optimized version of the partition algorithm which moves the PIVOT to its correct position (between the 2 logical halves) after partitioning, and then sorts the remaining elements of the array (not including the pivot), since the pivot is already is in its correct position!!! Thus, avoiding unnecessary comparisons for the pivot, once partition has taken place. So, after every call to partition ( ), 1 element (namely PIVOT) finds its correct position in the array. The efficiency gain has still to be computed mathematically, and also experimentally using a large set of random data. And help would be appreciated gratefully.


You can copy the code between the 2 HORIZONTAL LINES, paste it and save it as ASCII test, and compile it with a standards compliant C++ compiler such as g++.

template<typename T> void exchange(T& a, T& b)
{
  T temp = a;
  a = b;
  b = temp;
}


int partition(int* list, const int first, const int last)
{
  int x = list[first];
  int i = first;
  int j = last + 1;

  while (true)
    {
        while (list[--j] > x) { }
        while (list[++i] < x){ }

        if (i<j) exchange(list[i], list[j]);
        else
        {
              exchange (list[first], list[j]);
              return j;
        }
  }
}


void qsort(int* list, int first, int last)
{
  if (last > first)
 {
    int bound = partition(list, first, last);
    qsort(list, first, bound - 1);
    qsort(list, bound + 1, last);
  }
}


int main()
{
  int a[]= {5,2,5,4,3,7,8,5,0,5};
  qsort(a, 0, 9);
  for (int i = 0; i<10; i++)
    std::cout<<a[i]<<' ';
  std::cout<< std::endl;

  return 0;
}




Hosted by www.Geocities.ws

1