Quick sort - choosing first/starting element as pivot

Quick sort - choosing first/starting element as pivot


Quick Sort:

1. Has the Time Complexity of O(n^2) in worst case
2. Preferred Sorting technique in real-time applications
3. Better than Bubble sort, Selection sort, Insertion sort
4. Can be modified to achieve O(nlogn) complexity by modifying the code of choosing pivot element
5. Logic:
• Choose a pivot element
• Partition the array into subarrays such that the sub-array having elements less than falls in the left side of the pivot element
• and the sub-array with elements greater than the pivot element falls in the right side of  the pivot element
• merge the sub-arrays
• recursively do the above steps until there is a single element in the sub-array

#include <stdio.h> #include <stdlib.h> /* function swap to swap the two values of the array */ void swap(int *x,int *y) { int temp; temp=*x; *x=*y; *y=temp; } /* function partition to find the pivot element and sort the array elements such that elements in the left of piovt are smaller than it & elements in the right of pivot are greater than it */ int partition(int *a,int start,int end) { /* choosing starting element of the sub-array to be pivot element */ int pivot=a[start]; int pindex=end; int i; /* sort the array inorder to sort the elements to right & left side of pivot element */ for(i=end;i>=start+1;i--) { if(a[i]>pivot) { swap(&a[pindex],&a[i]); pindex=pindex-1; } } swap(&a[pindex],&a[start]); return pindex; } /* function quick sort */ void quicksort(int *a,int start,int end) { int pindex; /* break when there is single element in the sub-array */ if(start<end) { /* find the index of the pivot element, where the partition have to be performed */ pindex=partition(a,start,end); /* recur for the left sub-array */ quicksort(a,start,pindex-1); /* recur for the right sub-array */ quicksort(a,pindex+1,end); } } int main() { /* Input unsorted array */ int a[]={5,3,4,1,2,8,9,4,5,0,0,6,4,7,10}; /* find the number of elements in the array */ int n=sizeof(a)/sizeof(*a); int i; /* function call to perform quick sort */ quicksort(a,0,n-1); /* print the values in the sorted array */ for(i=0;i<n;i++) printf("%d ",*(a+i)); return 0; }