Question

Using Java compare how many swaps it takes a 1000 element array of integers. Use both quick-sort and heap sort. Only count when you swap values. Run the test in best case (array starts in sorted order), average case (array starts in random order), and in worst case array is sorted in reverse order. Print out the number of swaps for each sorting method's results.

Answer 1

//COMMENT IF YOU HAVE DOUBTS AND LIKE THE ANSWER.
class SortsSimulation
{
   public int quickSwapsCount = 0;
   public int heapSwapsCount = 0;
   public final int MAX_ELEMENTS = 1000;
   public int[] getSortedArray()
   {
       int[] array = new int[MAX_ELEMENTS];
       for(int i = 0;i<MAX_ELEMENTS;i++)
       {
           array[i] = i;
       }
       return array;
   }
   public int[] getReverseSortedArray()
   {
       int[] array = new int[MAX_ELEMENTS];
       for(int i = 0;i<MAX_ELEMENTS;i++)
       {
           array[i] = MAX_ELEMENTS-i;
       }
       return array;
   }
   public int[] getRandomSortedArray()
   {
       int[] array = new int[MAX_ELEMENTS];
       for(int i = 0;i<MAX_ELEMENTS/2;i++)
       {
           array[i] = MAX_ELEMENTS-i;
       }
       for(int i = MAX_ELEMENTS/2;i<MAX_ELEMENTS;i++)
       {
           array[i] = i;
       }
       return array;
   }
   public void quickSort(int[] A)
   {
       quickSwapsCount = 0;
       //call qSort()to sort the array A
       qSort(A,0,A.length-1);
       System.out.println("Total Number of Swaps: "+quickSwapsCount);
   }
   //qSort()function to recursively parition the array
   //and then sort
   public void qSort(int []A,int start,int stop){
       if(start < stop){
           //get pivot element
           int pivot = partition(A,start,stop);
           //call qSort()from start to pivot -1
           qSort(A,start,pivot-1);
           //call qSort()from pivot + 1 to stop
           qSort(A,pivot+1,stop);
       }
       return;
   }
   //function that sorts the given sub array
public int partition(int []array , int start, int stop){
       int ind = (start-1);// index of smaller element
       int pivot = array[stop];
       int temp;
       for (int j=start;j<stop;j++)
       {
           // If current element is smaller than the pivot
           if (array[j] < pivot)
           {
               quickSwapsCount++;
               ind++;
               temp = array[ind];
               array[ind] = array[j];
               array[j] = temp;
           }
       }
       temp = array[ind+1];
       array[ind+1] = array[stop];
       array[stop] = temp;
       quickSwapsCount++;
       return ind+1;
   }
   public void printArray(int [] array)
   {
       System.out.println("\n------ Total Array Elements : " + array.length );
       System.out.print("\n[ ");
       for(int i = 0;i<array.length;i++)
       {
           System.out.print(array[i]);
           if(i < array.length-1)
           {
               System.out.print(" , ");
           }
       }
       System.out.print("]\n");
   }
   public void heapSort(int array[])
   {
       heapSwapsCount = 0;
       int n = array.length;
       for (int i = n / 2 - 1;i >= 0;i--)
       {
           heapify(array, n, i);
       }
       int temp;
       for (int i=n-1;i>=0;i--)
       {
           // Move current root to end
           temp = array[0];
           array[0] = array[i];
           array[i] = temp;
           heapSwapsCount ++;
           // call max heapify on the reduced heap
           heapify(array, i, 0);
       }
       System.out.println("Total Number of Swaps: "+heapSwapsCount);
   }
  
// To heapify a subtree rooted with node ind which is
// an index in array[]. n is size of heap
   void heapify(int array[], int n, int ind)
   {
       int largest = ind;
       int left= 2*ind + 1;
       int right = 2*ind + 2;

       if (left< n && array[left] > array[largest])
       {
           largest = left;
       }

       if (right < n && array[right] > array[largest])
       {
           largest = right;
       }

       // If largest inds not root
       int swap;
       if (largest != ind)
       {
           heapSwapsCount ++;
           swap = array[ind];
           array[ind] = array[largest];
           array[largest] = swap;
           // Recursindvely heapify the affected sub-tree
           heapify(array, n, largest);
       }
}
   public static void main(String[] args)
   {
       SortsSimulation tester = new SortsSimulation();
       int qOne[] = tester.getSortedArray();
       int hOne[] = tester.getSortedArray();
      
       int qTwo[] = tester.getRandomSortedArray();
       int hTwo[] = tester.getRandomSortedArray();
      
       int qThree[] = tester.getReverseSortedArray();
       int hThree[] = tester.getReverseSortedArray();
      
       System.out.println("\n-------- Sorted Order ---------\n");
       System.out.println("Quick Sort: ");
       tester.quickSort(qOne);
       System.out.println("\nHeap Sort: ");
       tester.heapSort(hOne);
      
       System.out.println("\n-------- Random Sorted Order ---------\n");
       System.out.println("Quick Sort: ");
       tester.quickSort(qTwo);
       System.out.println("\nHeap Sort: ");
       tester.heapSort(hTwo);
      
       System.out.println("\n-------- Reverse Sorted Order ---------\n");
       System.out.println("Quick Sort: ");
       tester.quickSort(qThree);
       System.out.println("\n\nHeap Sort: ");
       tester.heapSort(hThree);
      
   }
}