Question

Generate a random list NUMBERS of size 100. Sort NUMBERS using QUICKSORT until the sublist has size 15 or less; then use INSERTIONSORT on the sublist. Generate 10 random lists of 100 numbers. Sort each list using QUICKSORT and then sort the same list using the combination of QUICKSORT and INSERTIONSORT as described above. Compare the times for each of the two algorithms. You can measure the duration of the time which each algorithm takes as follows: Instant first = Instant.now(); // sort all the lists using QUICKSORT Instant second = Instant.now(); Duration duration = Duration.between(first, second); Instant first = Instant.now(); // Sort all the lists using the combined QUICKSORT and INSERTIONSORT Instant second = Instant.now(); Duration duration = Duration.between(first, second);

Answer 1

ClassName:QuickSort

public class QuickSort {
   /* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
   int partition(int arr[], int low, int high)
   {
       int pivot = arr[high];
       int i = (low-1); // index of smaller element
       for (int j=low; j<high; j++)
       {
           // If current element is smaller than or
           // equal to pivot
           if (arr[j] <= pivot)
           {
               i++;

               // swap arr[i] and arr[j]
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }

       // swap arr[i+1] and arr[high] (or pivot)
       int temp = arr[i+1];
       arr[i+1] = arr[high];
       arr[high] = temp;

       return i+1;
   }

   /* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
   void sort(int arr[], int low, int high)
   {
       if (low < high)
       {
           /* pi is partitioning index, arr[pi] is
now at right place */
           int pi = partition(arr, low, high);

           // Recursively sort elements before
           // partition and after partition
           sort(arr, low, pi-1);
           sort(arr, pi+1, high);
       }
   }

   /* A utility function to print array of size n */
   static void printArray(int arr[])
   {
       int n = arr.length;
       for (int i=0; i<n; ++i)
           System.out.print(arr[i]+" ");
   }
}

**********************************************************************************************************************************************
Classname:InsertionSort

public class InsertionSort {
   /*Function to sort array using insertion sort*/
   void sort(int arr[])
   {
       int n = arr.length;
       for (int i = 1; i < n; ++i) {
           int key = arr[i];
           int j = i - 1;

           /* Move elements of arr[0..i-1], that are
   greater than key, to one position ahead
   of their current position */
           while (j >= 0 && arr[j] > key) {
               arr[j + 1] = arr[j];
               j = j - 1;
           }
           arr[j + 1] = key;
       }
   }

   /* A utility function to print array of size n*/
   static void printArray(int arr[])
   {
       int n = arr.length;
       for (int i = 0; i < n; ++i)
           System.out.print(arr[i] + " ");

       System.out.println();
   }

}

*********************************************************************************************************************************************

ClassName:SortingTestor

import java.time.Duration;
import java.time.Instant;
import java.util.Random;

public class SortingTestor {
   public static int[] generateList(Integer n) {
       int[] arr=new int[n];
       int value=0;
       Random random=new Random();
       for(int i=0;i<n;i++) {
           value=random.nextInt();
           arr[i]=value;
       }
       return arr;
   }
  
   public static void main(String[] args) {
       for(int i=0;i<10;i++) {
           int[] arr=generateList(100);
           QuickSort qObj=new QuickSort();
           System.out.println("\n>> List before sorting using Quick sort ");
           qObj.printArray(arr);
           Instant qfirst = Instant.now();
           qObj.sort(arr, 0, 99);
           Instant qsecond = Instant.now();
           Duration duration = Duration.between(qfirst, qsecond);
           System.out.println("\n Time taken in quick sort : "+duration.getNano());
           System.out.println("\n>> List after sorting using Quick sort");
           qObj.printArray(arr);
           InsertionSort iObj=new InsertionSort();
           System.out.println("\n>> List before sorting using Insertion Sort");
           iObj.printArray(arr);
           Instant ifirst = Instant.now();
           iObj.sort(arr);
           Instant isecond = Instant.now();
           Duration time = Duration.between(ifirst, isecond);
           System.out.println("\n Time taken in quick sort : "+time.getNano());
           System.out.println("\n>> List after sorting using Insertion Sort ");
           iObj.printArray(arr);
       }
   }

}

**********************************************************************************************************************************************

Here time difference is in seconds change it to milliseconds for seeing the exact difference

>> List before sorting using Quick sort -1566800969 1375617284 914172075 1319444316 -473126938 -661843509 654125783 519741757 1203108776 - 1174771558 49909030 161981909 1978 Time taken in quick sort : 0 >>> List after sorting using Quick sort -2096006261 -2084933570 -2083531438 -2068795585 -2040677172 -1969874620 -1949353053 -1894377416 -1813147175 -1813071704 - 1733485529 >> List before sorting using Insertion Sort -2096006261 -2084933570 -2083531438 -2068795585 -2040677172 -1969874620 -1949353053 -1894377416 -1813147175 -1813071704 - 1733485529 - Time taken in quick sort : 0 >> List after sorting using Insertion Sort -2096006261 -2084933570 -2083531438 -2068795585 -2040677172 -1969874620 -1949353053 -1894377416 -1813147175 -1813071704 - 1733485529 >> List before sorting using Quick sort 1013083181 -226600023 -1298898741 -1604695953 102932406 -695393416 -1071474823 -1052684858 1516369001 1141235860 542318967 - 157554043 Time taken in quick sort : 0 >> List after sorting using Quick sort -2114330314 -2001735743 - 1985956132 -1983862610 -1964108460 -1912050054 -1862093654 -1853043480 -1809590100 -1782833047 -1707389000 >> List before sorting using Insertion Sort -2114330314 -2001735743 -1985956132 -1983862610 -1964108460 -1912050054 - 1862093654 -1853043480 -1809590100 -1782833047 -1707389000 - Time taken in quick sort : 0 >> List after sorting using Insertion Sort -2114330314 -2001735743 -1985956132 -1983862610 -1964108460 -1912050054 -1862093654 -1853043480 -1809590100 -1782833047 -1707389000 >> List before sorting using Quick sort 734338303 -1842071220 1690729112 1764956588 -280602708 529291057 -363648994 817582630 1496072073 254128072 -2018810838 -416526975 -13 Time taken in quick sort : 0