Tag Archives: quicksort c code

Quick Sort

Quick Sort belongs to the category ofdivide and conquer algorithms. Quicksort  divides a large list into two smaller lists around a selected pivot . Quicksort can then recursively sort the sub-lists.It sorts the elements inplace.

The steps followed are are:

  1. Select an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it . After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the two sub-lists generated.

 For more information on bubble sort visit http://en.wikipedia.org/wiki/Quicksort.

Below is the C++ code for quick sort algorithm.
CODE:

/*
 http://randomtechbits.in/
*Program to sort numbers using QUICKSORT
*inputs: N- number of integers to sort ,A-array of integers       
*output: sorted array of integers
*code tested on devc++ IDE
*/

#include<iostream>

using namespace std;
int partition(int A[],int l,int r)
{
// note that I've used some vars unnecessarily just make the code more clear 
int key=A[l],q;
int  p=l+1;
q=r;
int t;
while(q>=p)
  {
   while(A[p]<key)
   ++p;
   while(A[q]>key)
   q--; 
  if(q>p)
    {t=A[q];
     A[q]=A[p];
     A[p]=t;  
    }
  } 
A[l]=A[q];
A[q]=key;
return q;                  
}

void quicksort(int A[],int p,int r)
{int q;
if(p>=r)return;
else
  q=partition(A,p,r);
  quicksort(A,p,q-1);
  quicksort(A,q+1,r);     
}

main()
{
int N,temp;
int *A;
int i,j;
cout<<"Enter the number of elements in array:\n";
cin>>N;
A=new int[N];
cout<<"Enter the array\n";
for(i=0;i<N;i++)
  cin>>A[i];
quicksort(A,0,N-1);
cout<<"\nThe Sorted array after QUICK SORT:"<<i<<"\n";  
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];   
//for more codes visit randomtechbits.in
getch();  
}