Question

I need to program 3 and add to program 2 bellows:

Add the merge sort and quick sort to program 2 and do the same timings, now with all 5 sorts and a 100,000 element array. Display the timing results from the sorts. DO NOT display the array.

____________________>>>>>>>>>>>>>>>>>>>>___________________________

(This is program 2 code that I did : ) ---->>>>>> code bellow from program 2

java program - Algorithms

Write a program that randomly generates 100,000 integers into an array.

Write a method that sorts this large array using shell sort.

Write a method that sorts this large array using insertion sort.

Write a method that sorts this large array using selection.

Place code in the main method to evaluate the timing of the execution of each sort algorithm and report on each of them

Code program 2

SortDemo.java:
import java.util.Random;

public class SortDemo {

public static int[] createRandomArray(int size) {

int array[] = new int[size];

Random r = new Random();

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

array[i] = r.nextInt() % (int) (size * 1.8);

}

return array;

}

public static int[] getArrayCopy(int[] arr) {

int newArr[] = new int[arr.length];

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

newArr[i] = arr[i];

}

return newArr;

}

public static void shellSort(int array[]) {

int gap = array.length / 2;

boolean swapflag;

while (gap > 0) {

swapflag = true;

while (swapflag) {

swapflag = false;

for (int s = 0; s < (array.length - gap); s++) {

if (array[s] > array[s + gap]) {

int temp = array[s];

array[s] = array[s + gap];

array[s + gap] = temp;

swapflag = true;

}

}

}

gap = gap / 2;

}

}

public static void insertionSort(int arr[]) {

int n = arr.length;

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

int key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

}

public static void selectionSort(int arr[]) {

int n = arr.length;

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

int min_idx = i;

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

if (arr[j] < arr[min_idx])

min_idx = j;

int temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

}

}

public static void main(String[] args) {

final int SIZE = 100000;

int arr1[] = createRandomArray(SIZE);

int arr2[] = getArrayCopy(arr1);

int arr3[] = getArrayCopy(arr1);

// Now all the 3 arrays have exactly same numbers

long start, end;

start = System.currentTimeMillis();

shellSort(arr1);

end = System.currentTimeMillis();

System.out.println("Shell sort time: " + (end - start) + " milliseconds.");

start = System.currentTimeMillis();

insertionSort(arr2);

end = System.currentTimeMillis();

System.out.println("Insertion sort time: " + (end - start) + " milliseconds.");

start = System.currentTimeMillis();

selectionSort(arr3);

end = System.currentTimeMillis();

System.out.println("Selection sort time: " + (end - start) + " milliseconds.");

}

}

Answer 1

//SortDemo.java

import java.util.Random;
public class SortDemo {
public static int[] createRandomArray(int size) {
int array[] = new int[size];
Random r = new Random();
for (int i = 0; i < size; i++) {
array[i] = r.nextInt() % (int) (size * 1.8);
}
return array;
}
public static int[] getArrayCopy(int[] arr) {
int newArr[] = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
return newArr;
}
public static void shellSort(int array[]) {
int gap = array.length / 2;
boolean swapflag;
while (gap > 0) {
swapflag = true;
while (swapflag) {
swapflag = false;
for (int s = 0; s < (array.length - gap); s++) {
if (array[s] > array[s + gap]) {
int temp = array[s];
array[s] = array[s + gap];
array[s + gap] = temp;
swapflag = true;
}
}
}
gap = gap / 2;
}
}
public static void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void selectionSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

public static int partitionArray(int arr[], int l, int h)
{
int pivot = arr[h];
int i = (l-1);
for (int j=l; j<h; j++)
{
  
  
if (arr[j] <= pivot)
{
i++;

  
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}

  
int t = arr[i+1];
arr[i+1] = arr[h];
arr[h] = t;

return i+1;
}

public static void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int t = partitionArray(arr, l, h);

quickSort(arr, l, t-1);
quickSort(arr, t+1, h);
}
}

public static void merge(int arr[], int l, int m, int r)
{
  
int len1 = m - l + 1;
int len2 = r - m;

int left[] = new int [len1];
int right[] = new int [len2];

for (int i=0; i<len1; ++i)
left[i] = arr[l + i];
for (int j=0; j<len2; ++j)
right[j] = arr[m + 1+ j];

int i = 0, j = 0;
int k = l;
while (i < len1 && j < len2)
{
if (left[i] <= right[j])
{
arr[k] = left[i];
i++;
}
else
{
arr[k] = right[j];
j++;
}
k++;
}

while (i < len1)
{
arr[k] = left[i];
i++;
k++;
}

while (j < len2)
{
arr[k] = right[j];
j++;
k++;
}
}

public static void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
  
int m = (l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr , m+1, r);
merge(arr, l, m, r);
}
}

public static void main(String[] args) {
final int SIZE = 100000;
int arr1[] = createRandomArray(SIZE);
int arr2[] = getArrayCopy(arr1);
int arr3[] = getArrayCopy(arr1);
int arr4[] = getArrayCopy(arr1);
int arr5[] = getArrayCopy(arr1);

long start, end;
start = System.currentTimeMillis();
shellSort(arr1);
end = System.currentTimeMillis();
System.out.println("Shell sort time: " + (end - start) + " milliseconds.");
start = System.currentTimeMillis();
insertionSort(arr2);
end = System.currentTimeMillis();
System.out.println("Insertion sort time: " + (end - start) + " milliseconds.");
start = System.currentTimeMillis();
selectionSort(arr3);
end = System.currentTimeMillis();
System.out.println("Selection sort time: " + (end - start) + " milliseconds.");

start = System.currentTimeMillis();
quickSort(arr4, 0, arr4.length-1);
end = System.currentTimeMillis();
System.out.println("Quick sort time: " + (end - start) + " milliseconds.");

start = System.currentTimeMillis();
mergeSort(arr5, 0, arr5.length-1);
end = System.currentTimeMillis();
System.out.println("Merge sort time: " + (end - start) + " milliseconds.");

}
}