Java Sorting Algorithms: Comparable Interface and Common Sorts
Sorting with the Comparable Interface
Java provides the Comparable interface to define sorting rules for classes.
Example:
- Define a
Studentclass withageandusernamefields, implementingComparableto provide comparison logic. - Define a test class with a method
getMax(Comparable c1, Comparable c2).
// Student.java
public class Student implements Comparable<Student> {
private String username;
private int age;
public Student() {}
public Student(String username, int age) {
this.username = username;
this.age = age;
}
public String getUsername() { return username; }
public void setUsername(String username) { this.username = username; }
public int getAge() { return age; }
public void setAge(int age) { this.age = age; }
@Override
public int compareTo(Student other) {
return this.age - other.age;
}
@Override
public String toString() {
return "Student{username='" + username + "', age=" + age + "}";
}
}
// TestComparable.java
public class TestComparable {
public static void main(String[] args) {
Student s1 = new Student("Alice", 18);
Student s2 = new Student("Bob", 20);
Comparable max = getMax(s1, s2);
System.out.println(max);
}
public static Comparable getMax(Comparable c1, Comparable c2) {
int result = c1.compareTo(c2);
if (result >= 0) {
return c1;
} else {
return c2;
}
}
}
Simple Sorting Algorithms
(1) Bubble Sort
Requirement: Sort array {4,5,6,3,2,1} to {1,2,3,4,5,6}.
Principle:
- Compare adjacent elements. If the first is larger than the second, swap them.
- After each pass, the largest element moves to the end.
- Repeat for the remaining elements.
public class BubbleSort {
public static void sort(Comparable[] arr) {
int n = arr.length;
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (greater(arr[j], arr[j + 1])) {
swap(arr, j, j + 1);
}
}
}
}
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
private static void swap(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public class BubbleSortTest {
public static void main(String[] args) {
Integer[] arr = {4, 5, 6, 3, 2, 1};
BubbleSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
Time Complexity: O(N²) in worst case (e.g., reverse order).
(2) Selection Sort
Principle:
- In each pass, find the smallest element in the unsorted portion and swap it with the first element of that portion.
- The sorted portion grows from left to right.
Requirement: Sort {4,6,8,7,9,2,10,1} to {1,2,4,6,7,8,9,10}.
public class SelectionSort {
public static void sort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (greater(arr[minIdx], arr[j])) {
minIdx = j;
}
}
swap(arr, i, minIdx);
}
}
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
private static void swap(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Time Complexity: O(N²) in all cases.
(3) Insertion Sort
Principle:
- Divide the array into sorted and unsorted parts.
- Take the first element from unsorted part and insert it into the correct position in the sorted part by shifting elements.
Requirement: Sort {4,3,2,10,12,1,5,6} to {1,2,3,4,5,6,10,12}.
public class InsertionSort {
public static void sort(Comparable[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (greater(arr[j - 1], arr[j])) {
swap(arr, j - 1, j);
} else {
break;
}
}
}
}
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
private static void swap(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Time Complexity: O(N²) worst case, O(N) best case (nearly sorted).
Advanced Sorting Algorithms
(1) Shell Sort
Shell sort is an improved version of insertion sort that works by comparing elements separated by a gap (h). The gap decreases over time until it becomes 1.
Principle:
- Choose a gap sequence (e.g., h = 1, 4, 13, 40...).
- Sort subarrays of elements spaced by h using insertion sort.
- Reduce h and repeat until h = 1.
Requirement: Sort {9,1,2,5,7,4,8,6,3,5} to {1,2,3,4,5,5,6,7,8,9}.
public class ShellSort {
public static void sort(Comparable[] arr) {
int n = arr.length;
int h = 1;
while (h < n / 2) {
h = 2 * h + 1;
}
while (h >= 1) {
for (int i = h; i < n; i++) {
for (int j = i; j >= h; j -= h) {
if (greater(arr[j - h], arr[j])) {
swap(arr, j - h, j);
} else {
break;
}
}
}
h /= 2;
}
}
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
private static void swap(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Performance: Shell sort is much faster than insertion sort for large datasets. In tests with 100,000 random data points:
- Insertion sort: ~18057 ms
- Shell sort: ~18 ms
(2) Merge Sort
Merge sort uses divide-and-conquer: split the array into halves, sort each half recursively, then merge the sorted halves.
Principle:
- Split until each subarray has one element.
- Merge adjacent subarrays in sorted order.
- Repeat until one array remains.
Requirement: Sort {8,4,5,7,1,3,6,2} to {1,2,3,4,5,6,7,8}.
public class MergeSort {
private static Comparable[] aux;
public static void sort(Comparable[] arr) {
aux = new Comparable[arr.length];
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] arr, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(arr, lo, mid);
sort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
private static void merge(Comparable[] arr, int lo, int mid, int hi) {
int i = lo, p1 = lo, p2 = mid + 1;
while (p1 <= mid && p2 <= hi) {
if (less(arr[p1], arr[p2])) {
aux[i++] = arr[p1++];
} else {
aux[i++] = arr[p2++];
}
}
while (p1 <= mid) aux[i++] = arr[p1++];
while (p2 <= hi) aux[i++] = arr[p2++];
for (int j = lo; j <= hi; j++) {
arr[j] = aux[j];
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
}
Time Complexity: O(N log N) in all cases. Disadvantages: Requires extra space O(N).
(3) Quick Sort
Quick sort also uses divide-and-conquer. It selects a pivot element and partitions the array sothat elements less than pivot go left, greater go right. Then recursively sort the partitions.
Principle:
- Pick a pivot (usually first element).
- Use two pointers: one from left looking for element greater than pivot, one from right looking for element less than pivot. Swap them until pointers cross.
- Swap pivot with right pointer to place it in correct position.
- Recursively sort left and right subarrays.
Requirement: Sort {6,1,2,7,9,3,4,5,8} to {1,2,3,4,5,6,7,8,9}.
public class QuickSort {
public static void sort(Comparable[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] arr, int lo, int hi) {
if (hi <= lo) return;
int pivotIdx = partition(arr, lo, hi);
sort(arr, lo, pivotIdx - 1);
sort(arr, pivotIdx + 1, hi);
}
private static int partition(Comparable[] arr, int lo, int hi) {
Comparable pivot = arr[lo];
int left = lo;
int right = hi + 1;
while (true) {
while (less(pivot, arr[--right])) {
if (right == lo) break;
}
while (less(arr[++left], pivot)) {
if (left == hi) break;
}
if (left >= right) break;
swap(arr, left, right);
}
swap(arr, lo, right);
return right;
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void swap(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Time Complexity: O(N log N) average, O(N²) worst case (when pivot is always smallest or largest).
Stability of Sorting Algorithms
Definition: A sorting algorithm is stable if equal elements maintain their relative order after sorting.
- Stable: Bubble, Insertion, Merge.
- Unstable: Selection, Shell, Quick.
Conclusion
This article covers common sorting algorithms in Java, their implementations, time complexities, and stability. Understanding these algorithms is fundamental for efficient data processing.
