Write a simple program that will measure the time taken to sort an array of integers | compare various sorting algorithms selection sort, insertion sort, merge sort, Quick sort

Below has java program to compare time taken between Insertion Sort, Selection Sort, Quick Sort, Merge Sort.





import java.util.Random;

public class Sorting {
      private static final int SIZE = 16000;
      private static int[] z = new int[SIZE];
      private static int[] a = new int[SIZE];
      private static int[] b = new int[SIZE];

      public static void main(String[] args) {
            // Create and populate array with random values
            Random rand = new Random();
            int[] x = new int[SIZE];
            for (int i = 0; i < x.length; i++) {
                  x[i] = rand.nextInt(SIZE);
            }
            showArray(x);
            int[] y = new int[SIZE];
            y = x;
            z = x;
            a = x;
            // Insertion Sort
            long start = System.currentTimeMillis();
            insertionSort(x);
            long end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");
           
            // Selection sort

            start = System.currentTimeMillis();
            selectionSort(y);
            end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");

            // Quicksort

            start = System.currentTimeMillis();
            quickSort(0, z.length - 1);
            end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");

            // Mergesort

            start = System.currentTimeMillis();
            mergeSort(0, a.length - 1);
            end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");

      }

      private static void showArray(int[] x) {
            System.out.print("[");
            for (int i = 0; i < x.length - 1; i++) {
                  System.out.print(x[i] + ", ");
            }
            System.out.println(x[x.length - 1] + "]");
      }

      // Add sorting algorithms here // Insertion, Selection, Quicksort, Mergesort
      public static void insertionSort(int[] arr) {
            int i, j, newValue;
            for (i = 1; i < arr.length; i++) {
                  newValue = arr[i];
                  j = i;
                  while (j > 0 && arr[j - 1] > newValue) {
                        arr[j] = arr[j - 1];
                        j--;
                  }
                  arr[j] = newValue;
            }
      }
 //selection sort
      public static void selectionSort(int[] x) {

            for (int i = 0; i < x.length - 1; i++) {
                  int minIndex = i;
                  for (int j = i + 1; j < x.length; j++) {
                        if (x[minIndex] > x[j]) {
                              minIndex = j;
                        }
                  }
                  if (minIndex != i) {

                        int temp = x[i];
                        x[i] = x[minIndex];
                        x[minIndex] = temp;
                  }
            }
      }
// Quick sort
      public static void quickSort(int low, int high) {

            int i = low, j = high;
            // the pivot element from the middle of the list
            int pivot = z[low + (high - low) / 2];
            // divide into two lists
            while (i <= j) {
                  while (z[i] < pivot) {
                        i++;
                  }
                  while (z[j] > pivot) {
                        j--;
                  }

                  if (i <= j) {
                        swap(i, j);
                        i++;
                        j--;
                  }
            }

            if (low < j)
                  quickSort(low, j);
            if (i < high)
                  quickSort(i, high);
      }

      public static void swap(int i, int j) {
            int temp = z[i];
            z[i] = z[j];
            z[j] = temp;
      }
// Merge Sort
      public static void mergeSort(int low, int high) {
            System.out.print("");
            // Check if low is smaller then high, if not then the array is sorted
            if (low < high) {
                  // Get the index of the element which is in the middle
                  int middle = low + (high - low) / 2;
                  // Sort the left side of the array
                  mergeSort(low, middle);
                  // Sort the right side of the array
                  mergeSort(middle + 1, high);
                  // Combine them both
                  merge(low, middle, high);
            }
      }

      public static void merge(int low, int middle, int high) {

            // Copy both parts into the temp array
            for (int i = low; i <= high; i++) {
                  b[i] = a[i];
            }

            int i = low;
            int j = middle + 1;
            int k = low;
            // copy the smallest values from either the left or the right side back
            // to the original array
            while (i <= middle && j <= high) {
                  if (b[i] <= b[j]) {
                        a[k] = b[i];
                        i++;
                  } else {
                        a[k] = b[j];
                        j++;
                  }
                  k++;
            }
            // copy the rest of the left side of the array into the target array
            while (i <= middle) {
                  a[k] = b[i];
                  k++;
                  i++;
            }

      }

}

Output:

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.