Quick Sort (traditional implementation)

Home           Algorithms Home

This is a simplistic implementation of the famous Quick Sort algorithm invented by C.A.R Hoare. As its name suggests, it is one of the quickest sorting algorithms around today. Its basic principle is the divide-and-conquor theory, by virtue of which, it breaks up the original array into logical halves, after partitioning it in such a way that all elements less than (or greater than) a PIVOT element are on one side of the array, and the elements greater than  (or less than) the pivot are on the other logical half. The equality check is not performed so that elements equal to the pivot are distributed equally in both the logical halves to reduce unnecessary data movement and ensure that each logical half is approximately equal in size to the other logical half. This code has been written by Apurva Mehta.


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 - 1;
  int j = last + 1;

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

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


void qsort(int* list, int first, int last)
{
  if (last > first)
 {
    int bound = partition(list, first, last);
    qsort(list, first, bound);
    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