Improvements to Quicksort using the Median of 3 partition and Insertion sort

[usman2k4u]

Implement the following improvement to the quick sort and find out the percentage of key comparisons that can be saved in each case. Using randomly generated 1000 integers as input for sorting. Repeat the experiment 1000 times for each case to get the average percentage reduction in key comparisons.

Case 1. Median of Three Partition
Case 2. Sort partition of size less than 16 directly using Insertion sort
Case 3. Combine both techniques above.

Please let me know how do I do this?

Thanks in advance.

[ArkM]

Read this:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx

[usman2k4u]

Source Code
Below is the basic quick sort algorithm.

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;
  l_hold = left;
  r_hold = right;
  pivot = numbers;
  while (left < right)
  {
    while ((numbers >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers = numbers;
      left++;
    }
    while ((numbers <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers = numbers;
      right--;
    }
  }
  numbers = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

[usman2k4u]

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define CUTOFF 16
#define length(x) ( sizeof x / sizeof *x )
 
struct pivots {
  int left, right;
};
int bas,spe,choice; 
void swap ( int *a, int *b );
void insertion_sort ( int list[], int left, int right );
int median ( int list[], int left, int right );
struct pivots partition ( int list[], int left, int right );
void quicksort_r ( int list[], int left, int right );
void quicksort ( int list[], int left, int right );
 
int basicpartition(int array[1000],int x1, int x2)
{
 int temp,x,i,j;
 x=array[x2];
 i=x1-1;
 for(j=x1;j<x2;j++)
 {
  
  if(array[j]<=x)
   {
	bas++;
    i=i+1;
    temp=array[i];
	array[i]=array[j];
	array[j]=temp;
   }
  else
	  bas++;
 }
 temp=array[i+1];
 array[i+1]=array[x2];
 array[x2]=temp;
 return (i+1);
}
void inser(int arc[1000],int x1,int x2)
{
	int i,j,value;
    for(i=x1+1;1<=x2;i++)
	{
        value= arc[i];
        j=i-1;
        while((j >= 0)&&( arc[j] > value))
		{
            arc[j+1]=arc[j];
            j = j-1;
		}
        arc[j+1] = value;
	}
} 
void swap ( int *a, int *b )
{
  int save = *a;
  *a = *b;
  *b = save;
}
 
void insertion_sort ( int list[], int left, int right )
{
  int i, j;
 
  for ( i = left + 1; i < right; i++ ) {
    int save = list[i];
 
    for ( j = i; j > 0 && list[j - 1] > save; j-- )
      list[j] = list[j - 1];
 
    list[j] = save;
  }
}
 
int median ( int list[], int left, int right )
{
   //Find the median of three values in list, use it as the pivot 

  int mid = ( left + right ) / 2;
 
  if ( list > list[mid] )
    swap ( &list, &list[mid] );
 
  if ( list > list )
    swap ( &list, &list );
 
  if ( list[mid] > list )
    swap ( &list[mid], &list );
 
  swap ( &list[mid], &list[right - 1] );
 
  return list[right - 1];
}
 
struct pivots partition ( int list[], int left, int right )
{
  int k;
  int i = left, j = right - 1;
  int m = left, n = right - 1;
  int pivot = median ( list, left, right );
  struct pivots ret;
 
  //Three way partition <,==,> 

  for ( ; ; ) {
    while ( list[++i] < pivot )
      ;
    while ( list[--j] > pivot ) {
      if ( j == left )
        break;
    }
 
    if ( i >= j )
      break;
 
    swap ( &list[i], &list[j] );
 
    if ( list[i] == pivot )
      swap ( &list[++m], &list[i] );
 
    if ( list[j] == pivot )
      swap ( &list[--n], &list[j] );
  }
 
  swap ( &list[i], &list[right - 1] );
 
  j = i - 1;
  i = i + 1;
 
  for ( k = left; k < m; k++, j-- )
    swap ( &list[k], &list[j] );
 
  for ( k = right - 1; k > n; k--, i++ )
    swap ( &list[k], &list[i] );
 
  ret.left = i;
  ret.right = j;
 
  return ret;
}
 
void quicksort_r ( int list[], int left, int right )
{
// Terminate on small subfiles 

  if ( left + CUTOFF <= right ) {
    struct pivots pivot = partition ( list, left, right );
 
    quicksort_r ( list, left, pivot.right );
    quicksort_r ( list, pivot.left, right );
  }
}
 
void quicksort ( int list[], int left, int right )
{
  quicksort_r ( list, left, right - 1 );
 
  //Insertion sort on almost sorted list 

  insertion_sort ( list, left, right );
}


void basi(int arc[1000],int x1, int x2)	//basic quick sort recursive function
{
 int q=0;
 if(x1<x2)
 {
	 if(choice==2)
	 {if((x2-x1)>15)
	 {
 q=basicpartition(arc,x1,x2);
 basi(arc,x1,q-1);
 basi(arc,q+1,x2);
 	 }
	 else
		 inser(arc,x1,x2);
	 }
 }
}

[Narue]

I think I prefer the code from the site ArkM gave you. ;)