Quick Sort : It is sorting algorithm which takes , O(n*2) time in worst case ,but usually its faster than O(NlogN) algorithms on average case.
It uses , devide and conquer algorithm.
Souce Code : C++ Implementation :
#include <iostream>
#include <cstdio>
using namespace std;
int q_partition(int arr[],int p,int r)
{
int x,i,j,temp;
x = arr[r];
i = p-1;
for(j = p;j< (r);j++)
{
if(arr[j] <= x)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i+1];
arr[i+1] = arr[r];
arr[r] = temp;
return ++i;
}
void q_sort(int arr[],int p,int r)
{
if(p < r)
{
int q = q_partition(arr,p,r);
q_sort(arr,p,q-1);
q_sort(arr,q+1,r);
}
}
int main(void)
{
int arr[] = {2,5,1,9,3};
int i;
q_sort(arr,0,4);
for(i = 0;i<5;i++)
cout<<"\t"<<arr[i];
int halt;
cin>>halt;
return 0;
}
No comments :
Post a Comment