Quick Sort


1. Algorithm:

Considering the array of n elements a0, a1, ..., an-1
Step 1: Select the lock pivot = a (left + right) / 2
Step 2: Partitioning. These smaller particles are located on the left key of the lock, the key element is larger on the right side of the key and the lock element may be located in any place on the range.
Step 3: Arrange for a new partition both left and right.

quicksort_intro

2. Source Code:

#include <iostream>
#include <conio.h>
#define max 100
using namespace std;
//Input Array
void InputArray(int A[],int n){
for(int i=0; i<n; i++) {
cout<<"Input element A["<<i<<"] =";
cin>>A[i];
}
}
//Print Array
void PrintArray(int A[],int n){
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
//Swap 2 elements
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
//Quick Sort Algorithm
void QuickSort(int A[], int Left, int Right){
int i = Left, j = Right;
int pivot = A[(Left + Right) / 2];
/* partition */
while (i <= j) {
while (A[i] < pivot)
i++;
while (A[j] > pivot)
j--;
if (i <= j) {
Swap(A[i],A[j]);
i++;
j--;
}
}
/* recursion */
if (Left < j)
QuickSort(A, Left, j);
if (i < Right)
QuickSort(A, i, Right);
}
//Main Function
int main() {
int A[max],n;
cout<<"Input number of array:";
cin>>n;
InputArray(A,n);
cout<<"\nOriginal Array:";
PrintArray(A,n);
cout<<endl;
QuickSort(A,0,n-1);
cout<<"\nSorted Array:";
PrintArray(A,n);
getch();
return 0;
}

3. Result:

quicksort_result_1


Advertisements