Nov
28
2008

C++ Program for QUICK SORT

C++ Program for QUICK SORT.

/**************************************************************	
	Author: Arun Vishnu M V
	Web: www.arunmvishnu.com
	Description: C++ Program for QUICK SORT.
***************************************************************/
#include<conio.h>  	
#include<iostream.h> 
#include<process.h>  
 
void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);
 
int numbers[150];
 
int main()
{
   clrscr();
   int i,n;
   cout<<"How many numbers you want to sort: ";
   cin>>n;
   cout<<"Enter "<<n<<" numbers.\n";
   for (i = 0; i<n; i++)
      cin>>numbers[i];
//perform quick sort on array
   q_sort(numbers,0,n-1);
 
   cout<<"Numbers are sorted\n";
   for (i = 0; i<n; i++)
      cout<<numbers[i]<<"   ";
   getch();
   return(0);
}
 
// Function to sort
void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
	 numbers[left] = numbers[right];
	 left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
	 left++;
      if (left != right)
      {
	  numbers[right] = numbers[left];
	  right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}
 
 
//---------------------- END--------------------

Related Posts

Author: Arun Vishnu

7 Comments + Add Comment

  • Hi.
    I need to find out a bug in the partition function of the quick sort in following program but i am not able to find it out.Can you help me.

    void partition (int a[ ], int n) {
    int pivot = a[0];
    left = 0;
    right = n-1;
    while (left = pivot) right–;
    if (left != right)
    {
    a[left] = a[right];
    left++;
    }
    while (a[left] < pivot) left++;
    if (left != right)
    {
    a[right] = a[left];
    right–;
    }
    }
    a[left] = pivot;
    }

  • Hii Shilpi,
    I am sorry, I didt gt time to go through the code.I am @ office and bsy now..
    one error is: while (left = pivot) .. condition inside the while lop is
    while (left == pivot)

  • i just wanna ask u that y u ve given the function prototype void quickSort(int numbers[], int array_size);
    since it is not being used in prog.

  • great code.so helpful.

  • great code it is

  • I support you Anshul. There is no use of void quickSort(…); at all.

  • while (left = pivot) && (left < right))
    right–;
    if (left != right)
    {
    numbers[left] = numbers[right];
    left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
    left++;
    if (left != right)
    {
    numbers[right] = numbers[left];
    right–;

    can u please explain d code in detail… how it works everything?

Leave a comment

Archives

Highslide for Wordpress Plugin