Below i have attached quick sort algorithm that can select pivot element position from the user for the first time and sort the array with nlogn complexity.
Approx. in all the books ,algorithm shows to select either first or last element as a pivot.This algorithm is able to select pivot position from user and sort the array elements accordingly.
Lets take an example:
95 5 1 3 7
try a quick sort dry run of this array elements on pen and paper,here 1 is a pivot element:-
1st pass:-1 5 95 3 7 (pivot element 1 is in final position)
2nd pass:-1 3 5 95 7 (now pivot element 5 is in final position)
3rd pass:-1 3 5 7 95 (pivot element 95 is in final position)
Just with the slight modification in the main & quick sort function , you can able to select middle element as a pivot element.To make a middle element as a pivot element,you only need to do three changes :
1.)Remove below two lines in the main function
printf("Enter pivot element position===>\n");
scanf("%d",&pivotpos);
2.) Add below lines in quicksort function
pivotpos=(start+end)/2;
3.)Remove pivotpos paramter from quicksort and partition function.
You can also change your algorithm to select first or last element as a pivot .You only need to do below changes in partition function and remove some code in quicksort function.
1.)pivotpos=left so that it always select first element in the list/sublist.
OR
2.)pivotpos=right so that it always select last element in the list/sublist.
Here is the code that are able to select random pivot element from the user.I hope this code works for you as well, you can try run this code on http://www.compileonline.com/compile_c_online.php.
If case you find anything wrong or any type of suggestion,please comment below.
Happy Coding.
----------------------------------------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
void quicksort(int arrElements[],int pivotpos,int start,int end){
int newpivotpos=partition(arrElements,pivotpos,start,end);
if(start<end){
if(newpivotpos<end){
quicksort(arrElements,newpivotpos+1,newpivotpos+1,end);
}
if(newpivotpos>0){
quicksort(arrElements,newpivotpos-1,start,newpivotpos-1);
}
}
}
int partition(int arrElements[],int pivotpos,int left,int right){
int pivotValue=arrElements[pivotpos],checkPosFlag=0,start=left,end=right;
while(left<right){
while(arrElements[left]<=pivotValue && left<=end) left++;
while(arrElements[right]>pivotValue) right--;
if(right==pivotpos){
checkPosFlag=1;
}
if(left<right){
swapElements(arrElements+left,arrElements+right);
if(checkPosFlag==1){
pivotpos=left;
checkPosFlag=0;
}
}
}
if(pivotpos!=right){
swapElements(&arrElements[pivotpos],&arrElements[right]);
pivotpos=right;
}
return pivotpos;
}
int swapElements(int *left,int *right){
*left=*left^*right;
*right=*left^*right;
*left=*left^*right;
return 0;
}
main()
{
int arrayLength,i,pivotpos;
printf("Enter Size of array=>\n");
scanf("%d",&arrayLength);
int arrElements[arrayLength];
printf("Enter array Elements=>\n");
for(i=0;i<arrayLength;i++){
scanf("%d",&arrElements[i]);
}
printf("Enter pivot element position===>\n");
scanf("%d",&pivotpos);
quicksort(arrElements,pivotpos,0,arrayLength-1);
printf("\nSorted Elements of array===>\n");
for(i=0;i<arrayLength;i++){
printf("%d",arrElements[i]);
}
}
----------------------------------------------------------------------------------------------------------------------------------
Comments
Post a Comment