Question

The objective of this Assignment is to compare the performance of some standard SORT algorithms.

You should look at MergeSort, QuickSort, and Insertion Sort; you can also look at an additional Sort mechanism that isn't covered in class or that isn't covered in the book for extra credit.

You will have to find the right implementations in Java so that you can make your comparisons.

Things you will be comparing are the raw running time and the time complexity in terms of a key operation for the algorithms (ex: as we discussed in class for Selection Sort comparisons are often a good way of measuring the time complexity of sort algorithms).

You will have to figure out how to use time methods in Java to measure running time. Use what was done in class as a reference.

Testing:

When comparing algorithms you want to make sure that you use a wide variety of test cases. In your case, you should have at least 4 different example sets on which to run your tests, each test case should have at least 20 points.

Report:

If you chose a 4th algorithm for extra credit, discuss which is the 4th algorithm and why you chose that.

You must have MergeSort, QuickSort, and Insertion Sort.

Discuss your plan for testing. Explain the 4 test cases that you chose and explain briefly why you chose those test cases. Test cases must have at least 20 integers or more.

Summarize your results for both measured running time and time complexity.

Describe your conclusions including insights, and surprises if any. How does the measured time complexity compare with the expected O cost?

Answer 1

import java.util.Arrays;

import java.util.Queue;

public class Sort {

private static int[] numbers;

private static int[] helper;

private static int number;

public void sort(int[] values) {

this.numbers = values;

number = values.length;

this.helper = new int[number];

System.out.println("START");

mergesort(0, number - 1);

System.out.println("END");

}

static void mergeSort(int[] values) {

numbers = values;

number = values.length;

helper = new int[number];

mergesort(0, number - 1);

}

private static void mergesort(int low, int high) {

// 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) / 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);

}

}

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

// printParts(low, middle);

//printParts(middle + 1, high);

// Copy both parts into the helper array

for (int i = low; i <= high; i++) {

helper[i] = numbers[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 (helper[i] <= helper[j]) {

numbers[k] = helper[i];

i++;

} else {

numbers[k] = helper[j];

j++;

}

k++;

}

// Copy the rest of the left side of the array into the target array

while (i <= middle) {

numbers[k] = helper[i];

k++;

i++;

}

}

private static int partition(int num[], int p, int q)

{

int piv = num[q];

int i = (p-1);

for (int j=p; j<q; j++)

{

  

if (num[j] <= piv)

{

i++;

int temp = num[i];

num[i] = num[j];

num[j] = temp;

}

}

int temp = num[i+1];

num[i+1] = num[q];

num[q] = temp;

return i+1;

}

private static void qsort(int arr[], int l, int h)

{

if (l < h)

{

int pi = partition(arr, l, h);

qsort(arr, l, pi-1);

qsort(arr, pi+1, h);

}

}

static void quickSort(int val[]){

qsort(val, 0, val.length-1);

}

public static void insertionSort2(int arr[] , int left, int right) {

int in, out;

// sorted on left of out

for (out = left + 1; out <= right; out++) {

int temp = arr[out];

in = out;

// until one is smaller,

while (in > left && arr[in - 1] >= temp) {

arr[in] = arr[in - 1]; // shift item to right

--in;

}

arr[in] = temp;

}

}

private static void qsort2(int arr[], int l, int h)

{

if (l < h)

{

int size = h - l + 1;

if(size<=16){

insertionSort2(arr,l,h);

return;

}

else{

int pi = partition(arr, l, h);

qsort2(arr, l, pi-1);

qsort2(arr, pi+1, h);

}

}

}

static void quickSort2(int val[]){

qsort2(val, 0, val.length-1);

}

public static void main(String[] args) {

for(int n = 20,max = 0; max<4; max++) {

   System.out.println("=====================Array of "+ n +" elements: ====================");

int[] A = new int[n+1]; // Create an array and fill it with small random ints.

for (int i = 0; i < n+1; i++)

   A[i] = 1 + (int)(n * Math.random());

int[] B = A.clone(); // Make copies of the array.

  

long a = System.nanoTime();

Arrays.sort(B);

long b = System.nanoTime();

long Taken = b - a;

System.out.print("\nSorted by Arrays Sort: ");

System.out.println("\nTime taken by Arrays Sort: " + Taken + " ns");

printArray(B);

long time1 = System.nanoTime();

bubbleSort(B);

long time2 = System.nanoTime();

long timeTaken = time2 - time1;

  

  

System.out.print("\nSorted by Bubble Sort: ");

System.out.println("\nTime taken by Bubble Sort: " + timeTaken + " ns");

printArray(B);

  

time1 = System.nanoTime();

selectionSort(B);

time2 = System.nanoTime();

timeTaken = time2 - time1;

System.out.print("\nSorted by Selection Sort: ");

System.out.println("\nTime taken by Selection Sort: " + timeTaken + " ns");

printArray(B);

  

//

time1 = System.nanoTime();

insertionSort(B);

time2 = System.nanoTime();

timeTaken = time2 - time1;

System.out.print("\nSorted by Insertion Sort: ");

System.out.println("\nTime taken by Insertion Sort: " + timeTaken + " ns");

printArray(B);

  

time1 = System.nanoTime();

mergeSort(B);

time2 = System.nanoTime();

timeTaken = time2 - time1;

System.out.print("\nSorted by Merge Sort: ");

System.out.println("\nTime taken by Merge Sort: " + timeTaken + " ns");

   printArray(B);

//

//

time1 = System.nanoTime();

quickSort(B);

time2 = System.nanoTime();

timeTaken = time2 - time1;

System.out.print("\nSorted by Quick Sort: ");

System.out.println("\nTime taken by Quick Sort: " + timeTaken + " ns");

  

}

   // printArray(B);

  

  

// time1 = System.nanoTime();

// quickSort2(B);

// time2 = System.nanoTime();

// timeTaken = time2 - time1;

//

// System.out.print("\nSorted by Quick Sort2: ");

// System.out.println("\nTime taken by Quick Sort2: " + timeTaken + " ns");

//

// printArray(B);

   }

  

   /**

* Tests whether an array of ints contains a given value.

* @param array a non-null array that is to be searched

* @param val the value for which the method will search

* @return true if val is one of the items in the array, false if not

*/

   public static boolean contains(int[] array, int val) {

for (int i = 0; i < array.length;++i) {

   if (array[i] == val)

return true;

}

return false;

   }

  

   /**

* Sorts an array into non-decreasing order. This inefficient sorting

* method simply sweeps through the array, exchanging neighboring elements

* that are out of order. The number of times that it does this is equal

* to the length of the array.

*/

   public static void bubbleSort(int[] array) {

for (int i = 0; i < array.length; i++) {

   for (int j = 0; j < array.length-1; j++) {

if (array[j] > array[j+1]) { // swap elements j and j+1

   int temp = array[j];

   array[j] = array[j+1];

   array[j+1] = temp;

}

   }

}

   }

  

   /**

* Sorts an array into non-decreasing order. This method uses a selection

* sort algorithm, in which the largest item is found and placed at the end of

* the list, then the second-largest in the next to last place, and so on.

*/

   public static void selectionSort(int[] array) {

for (int top = array.length - 1; top >= 0; top--) {

   int positionOfMax = top;

   for (int i = 0; i <= top; i++) {

if (array[i] > array[positionOfMax])

   positionOfMax = i;

   }

   int temp = array[top]; // swap top item with biggest item

   array[top] = array[positionOfMax];

   array[positionOfMax] = temp;

}

   }

  

   /**

* Sorts an array into non-decreasing order. This method uses a standard

* insertion sort algorithm, in which each element in turn is moved downwards

* past any elements that are greater than it.

*/

   public static void insertionSort(int[] array) {

for (int top = 1; top < array.length; top++) {

   int temp = array[top]; // copy item that into temp variable

   int pos = top - 1;

   while (pos > 0 && array[pos] > temp) {

   // move items that are bigger than temp up one position

array[pos+1] = array[pos];

pos--;

   }

   array[pos] = temp; // place temp into last vacated position

}

   }

  

   /**

* Outputs the ints in an array on one line, separated by spaces,

* with a line feed at the end.

*/

   private static void printArray(int[] array) {

for (int i = 0; i < array.length; i++) {

   System.out.print(" ");

   System.out.print(array[i]);

}

System.out.println();

   }

}

================================================
See Output


Thanks, PLEASE COMMENT if there is any concern.