Task Create a class that will implement 4 different sorting algorithms of your c

Question

Task Create a class that will implement 4 different sorting algorithms of your choosing. For this lab you are going to want to have overloaded constructors and mutator functions that will set the data section with a list to sort. Your class should sort a primitive array or a vector. For this assignment we want to be able to sort primitive types (int, char, double, float). So, it might be best to have your sort algorithms work on doubles. Each of your sort functions should produce a list of sorted values. Additional Functionality You should have a function that will return the number of iterations it took to sort the list. If I choose one of your sort algorithms l should then be able to call the function to get the number of iterations. Timer class: Attached to this assignment is the timer class that will allow you to profile each of the sorting algorithms. Implement this class and create a function that will return the time the last sort took to sort the list of numbers. In the end you should be able to successively call each of the sort functions and produce the number of iterations and the time it took to sort.

Explanation / Answer

import java.util.Random;

public class SortingAlgos {

   public static void main(String[] args) throws InterruptedException {
       int rangeMin = 0;
       int rangeMax = 50;
       double input[] = new double[1000];
       Random random = new Random();
       for (int i = 0; i < 1000; i++) {
           input[i] = rangeMin + (rangeMax - rangeMin) * random.nextDouble();

       }
       System.out.println("the input is ");
       printNumbers(input);
       long start_time = System.currentTimeMillis();
       // System.out.println(start_time);
       double res[] = bubble_srt(input);
       long end_time = System.currentTimeMillis();
       // System.out.println(end_time);
       long time_taken = end_time - start_time;
       // System.out.println(end_time + "," + start_time + "," + time_taken);
       System.out.print("Time taken to bubble sort is ");
       System.out.println(time_taken);
       printNumbers(res);
       start_time = System.currentTimeMillis();
       double res2[] = doInsertionSort(input);
       end_time = System.currentTimeMillis();
       time_taken = end_time - start_time;
       System.out.print("Time taken to insertion sort is ");
       System.out.println(time_taken);
       printNumbers(res2);
       start_time = System.currentTimeMillis();
       double res3[] = doSelectionSort(input);
       end_time = System.currentTimeMillis();
       time_taken = end_time - start_time;
       System.out.print("Time taken to selection sort is ");
       System.out.println(time_taken);
       printNumbers(res3);
       start_time = System.currentTimeMillis();
       double res4[] = sort(input);
       end_time = System.currentTimeMillis();
       time_taken = end_time - start_time;
       System.out.print("Time taken to heap sort is ");
       System.out.println(time_taken);
       printNumbers(res4);
   }

   public static double[] bubble_srt(double array[]) {
       int n = array.length;
       int k;
       int cnt1 = 0;
       int cnt2 = 0;
       for (int m = n; m >= 0; m--) {
           cnt1++;
           cnt2 = 0;
           for (int i = 0; i < n - 1; i++) {
               cnt2++;
               k = i + 1;
               if (array[i] > array[k]) {
                   double temp;
                   temp = array[i];
                   array[i] = array[k];
                   array[k] = temp;

               }
           }

       }
       System.out.println("Total no of iterations in Bubble sort " + cnt1 * cnt2);
       return array;
   }

   public static double[] doSelectionSort(double[] arr) {
       int cnt1 = 0;
       int cnt2;
       int sum = 0;
       for (int i = 0; i < arr.length - 1; i++) {
           cnt1++;
           cnt2 = 0;
           int index = i;
           for (int j = i + 1; j < arr.length; j++) {
               cnt2++;

               if (arr[j] < arr[index])
                   index = j;
           }
           double smallerNumber = arr[index];
           arr[index] = arr[i];
           arr[i] = smallerNumber;
           sum = sum + cnt2;

       }
       System.out.println("The total no of iteration in selection sort is " + (sum + cnt1));
       return arr;

   }

   public static double[] doInsertionSort(double[] input) {
       double temp;
       int cnt1 = 0;
       int cnt2;
       int sum = 0;
       for (int i = 1; i < input.length; i++) {
           cnt1++;
           cnt2 = 0;
           for (int j = i; j > 0; j--) {
               cnt2++;
               if (input[j] < input[j - 1]) {
                   temp = input[j];
                   input[j] = input[j - 1];
                   input[j - 1] = temp;
               }
           }
           sum = sum + cnt2;
       }
       System.out.println("The total no of iteration in insertion sort is " + (sum + cnt1));
       return input;
   }

   // heap sort is the best algo
   public static double[] sort(double arr[]) {
       int n = arr.length;
       int cnt1 = 0;
       int cnt2 = 0;

       // Build heap (rearrange array)
       for (int i = n / 2 - 1; i >= 0; i--) {
           cnt1++;
           heapify(arr, n, i);
       }
       // One by one extract an element from heap
       for (int i = n - 1; i >= 0; i--) {
           cnt2++;
           // Move current root to end
           double temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;

           // call max heapify on the reduced heap
           heapify(arr, i, 0);
       }
       System.out.println("The total no of iteration in heap sort is " + (cnt2 + cnt1));
       return arr;
   }

   // To heapify a subtree rooted with node i which is
   // an index in arr[]. n is size of heap
   static void heapify(double arr[], int n, int i) {
       int largest = i; // Initialize largest as root
       int l = 2 * i + 1; // left = 2*i + 1
       int r = 2 * i + 2; // right = 2*i + 2

       // If left child is larger than root
       if (l < n && arr[l] > arr[largest])
           largest = l;

       // If right child is larger than largest so far
       if (r < n && arr[r] > arr[largest])
           largest = r;

       // If largest is not root
       if (largest != i) {
           double swap = arr[i];
           arr[i] = arr[largest];
           arr[largest] = swap;

           // Recursively heapify the affected sub-tree
           heapify(arr, n, largest);
       }
   }

   private static void printNumbers(double[] input) {

       for (int i = 0; i < input.length; i++) {
           System.out.print(input[i] + ", ");
       }
       System.out.println(" ");
   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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