Form a group of three to four people. Write a Java, C or C++ program to compare

Question

Form a group of three to four people. Write a Java, C or C++ program to compare the QuickSort algorithm with Lomuto's partition and Hoare's partition. Use a counter to record the total number of key comparisons and another counter to record the total number of element swaps for sorting a given array. Select 10 array lengths between a few hundred and a few thousands. For each array length, generate random numbers for the array elements and run your program to get the numbers of key comparisons and element swaps for both partition methods. Record your results in an Excel spreadsheet.

Explanation / Answer

import java.util.Random;

public class SortingAnalysis {

   public SortingAnalysis() {
       Random random = new Random(System.currentTimeMillis());
       QuickSort qSort = new QuickSort();
      
       for(int i=1; i<=10; i++) {
           int size = random.nextInt(1000*i); /* Few Hundred to Few Thousands */
           int[] array = new int[size];
           int[] arrayCopy = new int[size];
          
           for (int k=0; k<size; k++) {
               array[i] = random.nextInt();
               arrayCopy[i] = array[i];
           }
          
           qSort.qSortLomutos(array, 0, size-1);
           qSort.qSortHoare(array, 0, size-1);
          
           System.out.println("Size = " + size);
           System.out.println("Lomutos-Comparisions = " + qSort.lomutosComparisions + ", Lomutos-Swaps = " + qSort.lomutosSwaps);
           System.out.println("Hoare-Comparisions = " + qSort.hoareComparisions + ", Hoare-Swaps = " + qSort.hoareSwaps + " ");
           qSort.resetCounters();
       }
   }

   public static void main(String args[]) {
       new SortingAnalysis();
   }
  
}

class QuickSort {

   public int lomutosSwaps;
   public int lomutosComparisions;

   public int hoareSwaps;
   public int hoareComparisions;

   /**
   * QuickSort with Lumutos Scheme
   */
   public void qSortLomutos(int arr[], int low, int high) {
       if (low < high) {
           int div = partitionLomutos(arr, low, high);
           qSortLomutos(arr, low, div - 1);
           qSortLomutos(arr, div + 1, high);
       }
   }

   public int partitionLomutos(int array[], int low, int high) {
       int pivot = array[high];

       int k = low - 1, i = low;
       for (; i < high; i++) {
           if (array[i] <= pivot) {
               lomutosComparisions++;
               k++;
               swap(array, i, k);
           }
       }
       k++;
       swap(array, i, k);
       lomutosSwaps++;
       return k;
   }

   /**
   * QuickSort with Hoare's Scheme
   */
   public void qSortHoare(int arr[], int low, int high) {
       if (low < high) {
           int pi = partitionHoare(arr, low, high);
           qSortHoare(arr, low, pi);
           qSortHoare(arr, pi + 1, high);
       }
   }

   public int partitionHoare(int array[], int low, int high) {
       int pivot = array[low];
       int i = low - 1, j = high + 1;

       while (true) {
           do {
               i++;
               hoareComparisions++;
           } while (array[i] < pivot);

           do {
               j--;
               hoareComparisions++;
           } while (array[j] > pivot);

           if (i >= j) {
               return j;
           }

           swap(array, i, j);
           hoareSwaps++;
       }
   }

   /**
   * method to swap two elements in an array
   */
   public void swap(int array[], int i, int k) {
       int temp = array[i];
       array[i] = array[k];
       array[k] = temp;
   }

   /**
   * Resets the swap and comparision counters of both procedures
   */
   public void resetCounters() {
       lomutosSwaps = 0;
       lomutosComparisions = 0;
       hoareSwaps = 0;
       hoareComparisions = 0;
   }

}

Output

Size = 239
Lomutos-Comparisions = 28203, Lomutos-Swaps = 237
Hoare-Comparisions = 2314, Hoare-Swaps = 915

Size = 1184
Lomutos-Comparisions = 700334, Lomutos-Swaps = 1183
Hoare-Comparisions = 15215, Hoare-Swaps = 5833

Size = 2804
Lomutos-Comparisions = 3929803, Lomutos-Swaps = 2803
Hoare-Comparisions = 39425, Hoare-Swaps = 15508

Size = 1380
Lomutos-Comparisions = 950131, Lomutos-Swaps = 1378
Hoare-Comparisions = 16589, Hoare-Swaps = 6910

Size = 349
Lomutos-Comparisions = 60716, Lomutos-Swaps = 348
Hoare-Comparisions = 3844, Hoare-Swaps = 1400

Size = 3757
Lomutos-Comparisions = 7055641, Lomutos-Swaps = 3756
Hoare-Comparisions = 54980, Hoare-Swaps = 21856

Size = 1209
Lomutos-Comparisions = 730230, Lomutos-Swaps = 1208
Hoare-Comparisions = 15552, Hoare-Swaps = 5964

Size = 4901
Lomutos-Comparisions = 12007443, Lomutos-Swaps = 4900
Hoare-Comparisions = 72948, Hoare-Swaps = 29124

Size = 4019
Lomutos-Comparisions = 8074163, Lomutos-Swaps = 4018
Hoare-Comparisions = 59796, Hoare-Swaps = 23871

Size = 6554
Lomutos-Comparisions = 21467628, Lomutos-Swaps = 6552
Hoare-Comparisions = 93939, Hoare-Swaps = 40410

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.