SCHOOL OF CODE BUILDERS: Quick sort - choosing last element as pivot element

Quick sort - choosing last element as pivot element

#include <stdio.h>
#include <stdlib.h>

/* function to swap two elements in the array */
void swap(int *x,int *y)
{
 int temp;
 temp=*x;
 *x=*y;
 *y=temp;
}

/* function partition which
1. Select the pivot element
2. sort the smaller elements to left of pivot
3. sort the larger elements to right of pivot
4. merge the left part, pivot, & right part */
int partition(int *a,int start,int end)
{
 /* selecting the last element to be pivot element */
 int pivot=a[end];
 int pindex=start;
 int i;
 for(i=start;i<end;i++)
 {
  if(a[i]<=pivot)
  {
   swap(&a[pindex],&a[i]);
   pindex++;
  }
 }
 swap(&a[pindex],&a[end]);
 return pindex;
}

/* function quick sort */
void quicksort(int *a,int start,int end)
{
 int pivot;
 if(start<end)
 {
  pivot=partition(a,start,end);
  
  /* recur for left of pivot index */
  quicksort(a,start,pivot-1);
  
  /* recur for right of pivot index */
  quicksort(a,pivot+1,end);
 }
}

int main(void) {
 /* input unsorted array */
 int a[]={5,4,2,3,1};
 
 /* find the number of elements in the array */
 int n=sizeof(a)/sizeof(a[0]);
 int i;
 
 /* function call to perform quick sort */
 quicksort(a,0,n-1);
 
 /* print the elements in the sorted array */
 for(i=0;i<n;i++)
  printf("%d ",*(a+i));
 return 0;
}

Pages

Quick sort - choosing last element as pivot element