Thursday, August 18, 2011

Quick sort program in C++

//Quick sort program in C++
#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[5];


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);
}

No comments:

Post a Comment