Quick Sort (क्विक सॉर्ट)

Quick Sort (क्विक सॉर्ट):-

It is a comparison based sorting method developed by tony hoare in 1961. It is also known as "divide and conquer algorithm" or "in-place sorting algorithm" or "partition exchange sort." 

In quick sort, first of all we select either first or last element of the list as pivot element and divide the given list in to two parts on the basis of pivot element to obtain two sub-list. Now again we divide these two sub-list in to two parts on the basis of pivot elements and we obtain four sub-lists. this process will continue until all the left hand side elements are smaller and all the right hand side elements are equal or greater than the pivot element.

यह तुलना पर आधारित सॉर्टिंग मेथड है जिसे टोनी होअरे ने सन 1961 में तैयार किया था। इसे "डिवाइड एंड कॉन्कर अल्गोरिथम" या "इन- प्लेस सॉर्टिंग अल्गोरिथम" या "पार्टीशन एक्सचेंज सॉर्ट" के नाम से भी जाना जाता है। 

इस मेथड में सर्वप्रथम एक पाइवोट एलिमेंट का चुनाव किया जाता है यह लिस्ट का पहला या अंतिम एलिमेंट हो सकता है एवं इस एलिमेंट के आधार पर दी गयी लिस्ट को दो भागो में विभाजित किया जाता है जिससे दो सबलिस्ट प्राप्त होती है। अब पुनः दोनों सबलिस्ट को पाइवोट एलिमेंट के आधार पर दो भागो में विभाजित किया जाता है जिससे चार सबलिस्ट प्राप्त होती है।यह प्रक्रिया तब तक चलती रहती है जब तक की पाइवोट एलिमेंट के बायीं ओर के सभी एलेमेंट्स पाइवोट से छोटे एवं दायी ओर के सभी एलेमेंट्स पाइवोट से बढे या बराबर ना हो जाये।

Algorithm/function/program for Quick Sort:-

File Name:- qsort.cpp

#include<iostream.h>
#include<conio.h>
#define N 10
void quicksort(int list[],int first, int last ){
int temp,low,high,pivot;
low=first;
high=last;
pivot=list[first];
do{
while(list[low]<pivot) low++;
while(list[high]>pivot) high--;
if(low<=high){
temp=list[low];
list[low++]=list[high];
list[high--]=temp;
}}while(low<=high);
if(first<high)
quicksort(list,first,high);
if(low<last)
quicksort(list,low,last);
}
void main(){
int i;
int list[N];
clrscr();
cout<<"Enter Elements of List "<<endl;
for(i=0;i<N;i++){
cout<<"Enter "<<i+1<<" element= ";
cin>>list[i];
}
cout<<"List Before Sorting :- ";
for(i=0;i<N;i++){
cout<<list[i]<<" ";
}
quicksort(list,0,N-1);
cout<<endl<<"List After Sorting :- ";
for(i=0;i<N;i++){
cout<<list[i]<<" ";
}
getch();
}

File Name:- qsort.c

#include<stdio.h>
#include<conio.h>
#define N 10
void quicksort(int list[],int first, int last ){
int temp,low,high,pivot;
low=first;
high=last;
pivot=list[first];
do{
while(list[low]<pivot) low++;
while(list[high]>pivot) high--;
if(low<=high){
temp=list[low];
list[low++]=list[high];
list[high--]=temp;
}}while(low<=high);
if(first<high)
quicksort(list,first,high);
if(low<last)
quicksort(list,low,last);
}
void main(){
int i;
int list[N];
clrscr();
printf("ENter Elements of List\n");
for(i=0;i<N;i++){
printf("Enter %d Element=",i+1);
scanf("%d",&list[i]);
}
printf("List before Sorting\n");
for(i=0;i<N;i++){
printf("%d ",list[i]);
}
quicksort(list,0,N-1);
printf("\nList after Sorting\n");
for(i=0;i<N;i++){
printf("%d ",list[i]);
}
getch();
}