Skip to main content

Quick Sort algorithm to select random/middle/first/last element as a pivot


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

Popular posts from this blog

MonoLithic Vs Microservice Architecture | which Architecture should i choose ?

From last few years ,microservices are an accelerating trend . Indeed, microservices approach offers tangible benefits including an increase in scalability, flexibility, agility, and other significant advantages. Netflix, Google, Amazon, and other tech leaders have successfully switched from monolithic architecture to microservices. Meanwhile, many companies consider following this example as the most efficient way for business growth. On the contrary, the monolithic approach is a default model for creating a software application. Still, its trend is going down because building a monolithic application poses a number of challenges associated with handling a huge code base, adopting a new technology, scaling, deployment, implementing new changes and others. So is the monolithic approach outdated and should be left in the past? And is it worth shifting the whole application from a monolith to microservices ? Will developing a microservices application help you reach you...

C Program to sort an array using insertion sort

I have seen couple of students who use swap in insertion sort to sort an array.Insertion sort is an example of exchange sort ,we don't swap two elements to sort an array ,instead of this we shift elements if ith element is greater than i+1th element to sort an array.It works on simple concept:- Store the ith element in temporary variable and shift element until you find the element smaller than this element towards 0 index position.Here is the C Program to find insertion sort:- _________________________________________________________________________________ #include <stdio.h> #include <string.h> main() {     int arrSize,i;    printf("Enter Size of array:");    scanf("%d",&arrSize);    int array[arrSize];    for(i=0;i<arrSize;i++){        scanf("%d",&array[i]);    }    int temp,j;    for(i=1;i<arrSize;i++){        temp...

Perfect Hashing and its implementation in C

Perfect hashing simply means hashing with no collision.But there is nothing like perfect hashing(no collision).These are just a work around to achieve perfect hashing.Using this we can able to search the large set of records in a constant time i.e O(1) time complexity.To achieve searching in strict O(1) time ,one needs to implement hash table and then search the given record in to hash table using hash function.         Here in perfect hashing ,one need to implement two level hash table , first level hash table consist a set of pointers that points to the second level hash table,we must select hash function that first maps the key in to first level hash table,so it simply means there must be collision in first level hash table ,thats  why i am saying its just a work around to achieve prefect  hashing.We must wisely choose hash function:                  h(x)=((a*x+b)mod p)mod m x is the key to be map, Here ...