C++ Program for QUICK SORT
by
Arun Vishnu
·
Published November 28, 2008
· Updated April 12, 2009
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--------------------
/**************************************************************
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--------------------
Tags: c and cpp Programming source code
You may also like...
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?