Question

Can someone implement the following in Java?

Quicksort with switching to Insertion sort when the number of elements in the subarray is less than or equal to 2% of the original number

Requirements:

1) functions from standard libraries implementing Quicksort are NOT allowed;

Answer 1

public class Main
{
//function to sort an array using insertion sort algorithm
public static void insertionSort(int arr[], int size)
{
   int k, j;
   for (int i = 1; i < size; i++)
   {
       k = arr[i];
       j = i - 1;
      
       while (j >= 0 && arr[j] > k)
       {
           arr[j + 1] = arr[j];
           j = j - 1;
       }
       arr[j + 1] = k;
   }
}
  
//method for partition
public static int partition(int a[], int l, int h)
{
int pvt = a[h];
int i = l - 1;
int temp;
  
for (int j = l; j <= h - 1; j++)
{
if (a[j] < pvt)
{
i++;
  
//swapping
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i + 1];
a[i + 1] = a[h];
a[h] = temp;
return i + 1;
}
  
//mthod for quick sort
public static void Quick_Sort(int A[], int l, int r, int size)
{
if (l < r)
{
  
int p = partition(A, l, r);
  
//switching to Insertion sort when the number of elements in the subarray is less than or equal to 2% of the original number
if((p-1-l)<=(.02 * size))
{
insertionSort(A, p-1-l);
}
else
{
Quick_Sort(A, l, p - 1, size);
}
  
if((r-p-1)<=(.02 * size))
{
insertionSort(A, r-p-1);
}
else
{
Quick_Sort(A, p + 1, r, size);
}
}
}
   public static void main(String[] args)
   {
   //array declaration and initialization
int a[] = {20, 55, 11, 64, 97, 99, 74, 85, 34, 35, 74, 11, 47, 65, 69};
  
//method calling
Quick_Sort(a, 0, 14, 14);
  
System.out.println("The array after sorting is: ");
for(int i=0; i<=14; i++)
{
System.out.print(a[i] + " ");
}
      
   }
}

OUTPUT:

The array after sorting is:
11 11 20 34 35 47 55 64 65 69 74 74 85 97 99