Answer:
Java algorithm is given below
Explanation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class Temp {
static void bubbleSort(ArrayList<Integer> list) {
int n = list.size();
for (int p = 0; p < n - 1; p++)
for (int q = 0; q < n - p - 1; q++)
if (list.get(q) > list.get(q + 1)) {
int temp = list.get(q);
list.set(q, list.get(q + 1));
list.set(q + 1, temp);
}
}
static void selectionSort(ArrayList<Integer> list) {
int n = list.size();
for (int p = 0; p < n - 1; p++) {
int minimumIndex = p;
for (int q = p + 1; q < n; q++)
if (list.get(q) < list.get(minimumIndex))
minimumIndex = q;
int temp = list.get(p);
list.set(p, list.get(minimumIndex));
list.set(minimumIndex, temp);
}
}
static void insertionSort(ArrayList<Integer> list) {
int size = list.size();
int p, val, q;
for (p = 1; p < size; p++) {
val = list.get(p);
q = p - 1;
while (q >= 0 && list.get(q) > val) {
list.set(q + 1, list.get(q));
q = q - 1;
}
list.set(q + 1, val);
}
}
static void mergeSort(ArrayList<Integer> list, int low, int high) {
if (low < high && (high - low) >= 1) {
int mid = (high + low) / 2;
mergeSort(list, low, mid);
mergeSort(list, mid + 1, high);
merger(list, low, mid, high);
}
}
static void merger(ArrayList<Integer> list, int low, int mid, int high) {
ArrayList<Integer> mergedArray = new ArrayList<Integer>();
int left = low;
int right = mid + 1;
while (left <= mid && right <= high) {
if (list.get(left) <= list.get(right)) {
mergedArray.add(list.get(left));
left++;
} else {
mergedArray.add(list.get(right));
right++;
}
}
while (left <= mid) {
mergedArray.add(list.get(left));
left++;
}
while (right <= high) {
mergedArray.add(list.get(right));
right++;
}
int i = 0;
int j = low;
while (i < mergedArray.size()) {
list.set(j, mergedArray.get(i++));
j++;
}
}
public static void main(String[] args) throws Exception {
ArrayList<Integer> list = new ArrayList<>();
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < 10000; i++) {
list.add(rand.nextInt(256));
}
long start = System.currentTimeMillis();
selectionSort(list);
int sel = (int) (System.currentTimeMillis() - start);
System.out.println("Selection Sort time (in ms): " + sel);
list.clear();
// ------------------------
rand = new Random(System.currentTimeMillis());
for (int i = 0; i < 10000; i++) {
list.add(rand.nextInt(256));
}
start = System.currentTimeMillis();
insertionSort(list);
int ins = (int) (System.currentTimeMillis() - start);
System.out.println("Insertion Sort time (in ms): " + ins);
list.clear();
// ------------------------
rand = new Random(System.currentTimeMillis());
for (int i = 0; i < 10000; i++) {
list.add(rand.nextInt(256));
}
start = System.currentTimeMillis();
bubbleSort(list);
int bub = (int) (System.currentTimeMillis() - start);
System.out.println("Bubble Sort time (in ms): " + bub);
list.clear();
// ---------------------------
rand = new Random(System.currentTimeMillis());
for (int i = 0; i < 10000; i++) {
list.add(rand.nextInt(256));
}
start = System.currentTimeMillis();
mergeSort(list, 0, list.size() - 1);
int mer = (int) (System.currentTimeMillis() - start);
System.out.println("Merge Sort time (in ms): " + mer);
long m = Math.min(Math.min(sel, ins), Math.min(bub, mer));
if (m == sel)
System.out.println("Selection Sort is fastest");
else if (m == ins)
System.out.println("insertion Sort is fastest");
else if (mer == m)
System.out.println("Merge Sort is fastest");
else if (m == bub)
System.out.println("Bubble Sort is fastest");
}
}
