Question

Implement a method called bubbleSort, that takes an ArrayList, sorts it using bubble sort algorithm, and returns a sorted list; 2. Implement a method called selectionSort, that takes an ArrayList, sorts it using selection sort algorithm, and returns a sorted list; 3. Implement a method called insertionSort, that takes an ArrayList, sorts it using insertion sort algorithm, and returns a sorted list; 4. Implement a method called mergeSort, that takes an ArrayList, sorts it using merge sort algorithm, and returns a sorted list.

Answer 1

Java algorithm is given below

Step-by-step 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");

}

}