Question

Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot = first index) algorithms.

Compute the CPU processing time for all the algorithms for varying input sizes as follows: N = 10², 10³, 10⁴, 10⁵, and 10⁶

Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 10³, 1 - 10⁶, 1 – 10⁹, 1 - 10¹²

Write down your results as a table (with varying input size and algorithm type) and plot the graph. Present your inferences and/or explanations for your result (in a separate document).

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

import java.util.Arrays;

import java.util.Queue;

/**

* This class looks like it's meant to provide a few public static methods

* for searching and sorting arrays. It also has a main method that tests

* the searching and sorting methods.

*

* TODO: The search and sort methods in this class contain bugs that can

* cause incorrect output or infinite loops. Use the Eclipse debugger to

* find the bugs and fix them

*/

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 = 100; n<= 10000 ; n = n*10) {

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

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

Kindly revert for any queries

Thanks.