Question

Use the median of 3 partitioning algorithm (given in the next page) to implement quick sort. This algorithm chooses the pivot element as the median of the 3 elements namely: A[p], A[r], and A[(p+r)/2].(Java language)

Quicksort(A,p,r)

1 if p

2 N = r- p +1

3 m = Median3(A, p, p + N/2 , r)

4 exchange A[m] with A[r]

5 q = Partition (A,p,r)

6 Quicksort(A,p, q-1)

7 Quicksort(A,q+1,r)

Answer 1

The java code for quick sort is provided below.

Java Code:

import java.util.Scanner;

public class QuicksortMedian {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.print("Enter the size of array: ");
int n=sc.nextInt();
int[] arr=new int[n];
System.out.println("Enter the elements");
// Read elements
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
// Print array
System.out.println("Unsorted array");
for(int i=0;i<n;i++)
{
System.out.print(arr[i]+" ");
}
System.out.println();
// Sort the array
quicksort(arr,0,arr.length-1);
// Print sorted array
System.out.println("Sorted array");
for(int i=0;i<n;i++)
{
System.out.print(arr[i]+" ");
}
}

private static void quicksort(int[] A, int p, int r) {
int N,q;
if(p<r)
{
N=r-p+1;
// Finding median
int m=Median3(A, p, p + N/2 , r);
// Exchange median with the last element
swap(A,m,r);
q=Partition(A,p,r);
quicksort(A,p, q-1);
quicksort(A,q+1,r);
}
}

private static int Median3(int[] A, int p, int cent, int r) {
if ((A[p] > A[cent])&&(A[p]>A[r]))
{
if(A[cent]>A[r])
return cent;
else
return r;
}
else if((A[cent] > A[p])&&(A[cent]>A[r]))
{
if(A[p]>A[r])
return p;
else
return r;
}
else
{
if(A[cent]>A[p])
return cent;
else
return p;
  
}

}

private static void swap(int[] A,int l ,int r) {
int te = A[l];
A[l] = A[r];
A[r] = te;
}

// Partitioning array based on pivot
private static int Partition(int[] A, int p, int r) {
int piv = A[r];
int i = (p-1);
for (int j=p; j<r; j++)
{
if (A[j] < piv)
{
i++;
int te = A[i];
A[i] = A[j];
A[j] = te;
}
}
int te = A[i+1];
A[i+1] = A[r];
A[r] = te;
  
return i+1;
}
  
}

Output: