Yet another application of quicksort.Searching Kth minimum element in O(n)…
[gist https://gist.github.com/vishnujayvel/5879818]
Yet another application of quicksort.Searching Kth minimum element in O(n)…
[gist https://gist.github.com/vishnujayvel/5879818]
Quicksort has so many applications.One of them is to find the K minimum elements from a array in O(n) times.
How does quicksort’s O(nlogn) becomes O(n).Well,we need not sort the K minimum elements in order.we just want to find it. So we execute the partition till K becomes pivot position
[gist https://gist.github.com/vishnujayvel/5879546 ]We know how efficient quicksort algorithm is.its efficiency is O(nlogn)
By randomly selecting a pivot element it is found that the number of swaps reduces further.
To generate a random pivot use rand() function .
#include<iostream> | |
#include<stdlib.h> | |
using namespace std; | |
void swap(int &a,int &b){ | |
int temp=a; | |
a=b; | |
b=temp; | |
} | |
int partition(int arr[],int low,int high){ | |
int left,right,pivot; | |
int r=low+(rand()%(high-low+1)); | |
swap(arr[r],arr[low]); | |
pivot=arr[low]; | |
left=low; | |
right=high; | |
while(left<right){ | |
while(arr[left]<=pivot) | |
left++; | |
while(arr[right]>pivot) | |
right--; | |
if(left<right) | |
swap(arr[left],arr[right]); | |
} | |
arr[low]=arr[right]; | |
arr[right]=pivot; | |
return right; | |
} | |
void quicksort(int arr[],int low,int high){ | |
if(low<high){ | |
int p=partition(arr,low,high); | |
quicksort(arr,low,p-1); | |
quicksort(arr,p+1,high); | |
} | |
} | |
int main(){ | |
int arr[]={34,1,2,89,56,23}; | |
quicksort(arr,0,5); | |
for(int i=0;i<5;i++){ | |
cout<<arr[i]<<" "; | |
} | |
} |