Sorting Algorithms in Java
In this notebook, we’ll implement various sorting algorithms in Java and test their performance. We’ll implement Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort. Additionally, we’ll create a generic TQueue class with a Collectables implementation to compare keys.
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Time Complexity:
- Average Case: O(n^2)
- Worst Case: O(n^2)
// Bubble Sort Implementation
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
Selection Sort
Selection Sort sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.
Time Complexity:
- Average Case: O(n^2)
- Worst Case: O(n^2)
// Selection Sort Implementation
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// swap arr[i] and arr[minIndex]
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
Insertion Sort
Insertion Sort builds the final sorted array one item at a time by repeatedly picking the next item and inserting it into the sorted part.
Time Complexity:
- Average Case: O(n^2)
- Worst Case: O(n^2)
// Insertion Sort Implementation
public class InsertionSort {
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;
}
}
}
Merge Sort
Merge Sort is a divide-and-conquer algorithm that divides the array into two halves, sorts each half separately, and then merges the sorted halves.
Time Complexity:
- Average Case: O(n log n)
- Worst Case: O(n log n)
// Merge Sort Implementation
public class MergeSort {
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);
}
}
private static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
Quick Sort
Quick Sort is a highly efficient sorting algorithm based on the divide-and-conquer approach.
Time Complexity:
- Average Case: O(n log n)
- Worst Case: O(n^2)
// Quick Sort Implementation
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
Generic TQueue with Collectables Implementation
Let’s implement a generic TQueue class with a Collectables implementation to compare keys.
// TQueue with Collectables Implementation
import java.util.Comparator;
import java.util.PriorityQueue;
public class TQueue<T> {
private PriorityQueue<T> queue;
public TQueue() {
this.queue = new PriorityQueue<>();
}
public void enqueue(T element) {
queue.offer(element);
}
public T dequeue() {
return queue.poll();
}
public T peek() {
return queue.peek();
}
public boolean isEmpty() {
return queue.isEmpty();
}
public int size() {
return queue.size();
}
public static <T> void sortWithCollectables(T[] arr, Comparator<T> comparator) {
TQueue<T> tQueue = new TQueue<>();
for (T item : arr) {
tQueue.enqueue(item);
}
int index = 0;
while (!tQueue.isEmpty()) {
arr[index++] = tQueue.dequeue();
}
}
}
Tester Methods
Now, let’s implement tester methods to run each sorting algorithm.
// Tester Methods
import java.util.Arrays;
public class SortTester {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// Bubble Sort
System.out.println("Bubble Sort:");
BubbleSort.bubbleSort(arr.clone());
System.out.println(Arrays.toString(arr));
// Selection Sort
System.out.println("Selection Sort:");
SelectionSort.selectionSort(arr.clone());
System.out.println(Arrays.toString(arr));
// Insertion Sort
System.out.println("Insertion Sort:");
InsertionSort.insertionSort(arr.clone());
System.out.println(Arrays.toString(arr));
// Merge Sort
System.out.println("Merge Sort:");
MergeSort.mergeSort(arr.clone(), 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
// Quick Sort
System.out.println("Quick Sort:");
QuickSort.quickSort(arr.clone(), 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}