Quick Sort example in C++ (Quick Sort.CPP)

#include <iostream>

using namespace std;

void QuickSort(int * a, int n);
void quickSort(int a[], int l, int r);

int main(int argc, char **argv)
{
int a[5];
int i=0;
while(i<5){
cin>>a[i++];
}
QuickSort(a,5);
i=0;
while(i<5){cout<<a[i++]<"\n ";cout<"--";}
return 0;
}

void QuickSort(int * a, int n){
quickSort(a, 0, n-1);
}

void quickSort(int a[], int l, int r){
if(l>=r) return;

int i=l;
int j=r + 1;

int pivot = a[l];

//Swap elements  >= pivot on left side
//with elements <= pivot on right side

while(true){
do{
i++;
}while(a[i] < pivot );

do{
j--;
}while(a[j] > pivot );

if( i >= j) break;

int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}

//Place pivot
a[l] = a[j];
a[j] = pivot;

quickSort(a, l, j-1); //Sort Left Segment
quickSort(a, j+1, r); //Sort Right Segment

}

courtesy : Data Structures, Algorithms and Applications in C++, SAHNI, McGrawHill

Merge Sort Program in C++ (Merge Sort.CPP)

#include <iostream>
using namespace std;

void Merge(int *c, int *d, int l, int m, int r){
//Merge c[l:m] amd c[m:r] to d[l:r]
int i =l; //cursor for first segment
int j = m+1; //cursor for second
int k = l; //cursor for result

//merge until i or j exits its segment
while((i<=m) && (j<=r)){

if(c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
}
//take care over left overs
if(i > m) for(int q =j; q<=r;q++) d[k++] = c[q];

else for (int q = i; q<=m; q++) d[k++] = c[q];

}

void MergePass(int *x, int *y, int s, int n){
//Merge adjacent segments of size s
int i = 0;
while(i <=n -1 * s){
//Merge two adjacent segment of size a
Merge(x,y,i,i+s-1,i+2*s-1);
i = i + 2 *s;
}

//fewer than 2s elements remain
if(i+s < n) Merge(x,y,i,i+s-1,n-1);
else for(int j =i; j<n; j++){
//Copy last segment to y
y[j]= x[j];
}
}

void MergeSort(int *a, int n){
//Sort a[0:n-1] using merge sort
int *b= new int[n];
int s = 1; //Segment Size
while(s<n){
MergePass(a, b, s, n); //merge from a to b
s += s;
MergePass(b,a,s,n); // merge from b to a
s += s;
}

}

int main(int argc, char **argv)
{
int a[6]={10,4,87,17,53,34};
MergeSort(a,6);
int i=0;
while(i<6){
cout<<"--"<<a[i++];
}
return 0;
}

courtesy : Data Structures, Algorithms and Applications in C++, SAHNI, McGrawHill