Algorithmic Complexity
Understanding the complexity of sorting algorithms is essential for selecting the appropriate one for a given task.
Bubble Sort
Bubble Sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. This process repeats until no swaps are needed. An optimized version includes a flag to stop early if the list becomes sorted. Its time complexity is O(n²), making it inefficient for large datasets.
public void performBubbleSort() {
int[] numbers = {7, 3, 9, 2, 4, 5};
for (int outer = 0; outer < numbers.length - 1; outer++) {
boolean isSorted = true;
for (int inner = 0; inner < numbers.length - outer - 1; inner++) {
if (numbers[inner] > numbers[inner + 1]) {
int holder = numbers[inner];
numbers[inner] = numbers[inner + 1];
numbers[inner + 1] = holder;
isSorted = false;
}
}
if(isSorted) break;
}
System.out.println("Sorted array: " + Arrays.toString(numbers));
}
Selection Sort
Selection Sort divides the list into a sorted and an unsorted region. It repeatedly finds the smallest element from the unsorted part and moves it to the beginning. Time complexity is O(n²).
public void executeSelectionSort() {
int[] data = {7, 3, 9, 2, 4, 5};
for (int start = 0; start < data.length - 1; start++) {
int smallestIdx = start;
for (int scan = start + 1; scan < data.length; scan++) {
if (data[scan] < data[smallestIdx]) {
smallestIdx = scan;
}
}
int temporary = data[start];
data[start] = data[smallestIdx];
data[smallestIdx] = temporary;
}
System.out.println("Sorted array: " + Arrays.toString(data));
}
Insertion Sort
Insertion Sort builds the final sorted array one element at a time by inserting each new element into its correct position within the already sorted part. While its worst-case time complexity is O(n²), it performs well on small or nearly sorted lists.
public void runInsertionSort() {
int[] sequence = {7, 3, 9, 2, 4, 5};
for (int current = 1; current < sequence.length; current++) {
int keyValue = sequence[current];
int position = current - 1;
while (position >= 0 && sequence[position] > keyValue) {
sequence[position + 1] = sequence[position];
position--;
}
sequence[position + 1] = keyValue;
}
System.out.println("Sorted array: " + Arrays.toString(sequence));
}
Shell Sort
Shell Sort is an optimization of Insertion Sort. It sorts elements that are far apart by a defined gap and progressive reduces the gap. Its performance, better than Insertion Sort, depends on the gap sequence used.
public void applyShellSort() {
int[] values = {5, 2, 8, 3, 1, 6, 7, 9, 4};
int gap = values.length / 2;
while (gap >= 1){
for (int index = gap; index < values.length; index++) {
int prev = index - gap;
int currentVal = values[index];
while (prev >= 0 && values[prev] > currentVal) {
values[prev + gap] = values[prev];
prev -= gap;
}
values[prev + gap] = currentVal;
}
gap /= 2;
}
System.out.println("Sorted array: " + Arrays.toString(values));
}
Quick Sort
Quick Sort employs a divide-and-conquer strategy. It selects a 'pivot' element and partitions the array so that elements less than the pivot come before it, and elements greater come after. It then recursively sorts the sub-arrays. Average time complexity is O(n log n).
public class QuickSorter {
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int partitionIndex = partition(array, low, high);
quickSort(array, low, partitionIndex - 1);
quickSort(array, partitionIndex + 1, high);
}
}
private static int partition(int[] array, int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
int swapTemp = array[i];
array[i] = array[j];
array[j] = swapTemp;
}
}
int swapTemp = array[i + 1];
array[i + 1] = array[high];
array[high] = swapTemp;
return i + 1;
}
}
Heap Sort
Heap Sort uses a binary heap data structure. It first builds a max-heap from the data, then repeatedly extracts the largest element and rebuilds the heap. Time complexity is O(n log n).
public class HeapSorter {
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int heapSize, int root) {
int largest = root;
int leftChild = 2 * root + 1;
int rightChild = 2 * root + 2;
if (leftChild < heapSize && arr[leftChild] > arr[largest]) largest = leftChild;
if (rightChild < heapSize && arr[rightChild] > arr[largest]) largest = rightChild;
if (largest != root) {
int swapTemp = arr[root];
arr[root] = arr[largest];
arr[largest] = swapTemp;
heapify(arr, heapSize, largest);
}
}
}
Counting Sort
Counting Sort is a non-comparison algorithm. It counts the occurrances of each distinct element, calculates positions, and places elements directly into their correct sorted positions. It works best when the range of input values (k) is not significantly larger than the number of items (n), with time complexity O(n+k).
public class CounterSorter {
public static void countingSort(int[] arr) {
int size = arr.length;
int maxVal = Arrays.stream(arr).max().getAsInt();
int[] countArray = new int[maxVal + 1];
for (int value : arr) countArray[value]++;
for (int i = 1; i <= maxVal; i++) countArray[i] += countArray[i - 1];
int[] output = new int[size];
for (int i = size - 1; i >= 0; i--) {
int element = arr[i];
output[countArray[element] - 1] = element;
countArray[element]--;
}
System.arraycopy(output, 0, arr, 0, size);
}
}
Radix Sort
Radix Sort processes numbers digit by digit, from the least significant digit (LSD) to the most significant. It uses a stable subroutine sort (like Counting Sort) for each digit. Time complexity is O(d*(n+b)), where d is the number of digits, n is the number of elements, and b is the base for representing numbers.
import java.util.ArrayList;
import java.util.List;
public class RadixSorter {
public static void radixSort(int[] arr) {
if (arr.length == 0) return;
int max = Arrays.stream(arr).max().getAsInt();
int totalDigits = (int) Math.log10(max) + 1;
List<List<Integer>> buckets = new ArrayList<>(10);
for (int i = 0; i < 10; i++) buckets.add(new ArrayList<>());
int divisor = 1;
for (int place = 0; place < totalDigits; place++) {
for (int value : arr) {
int digit = (value / divisor) % 10;
buckets.get(digit).add(value);
}
int idx = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) arr[idx++] = num;
bucket.clear();
}
divisor *= 10;
}
}
}
Merge Sort
Merge Sort is a stable, divide-and-conquer algorithm. It recursively divides the array into halves until single elements remain, then merges the halves back together in sorted order. It guarantees O(n log n) time complexity.
public class MergeSorter {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int leftSize = mid - left + 1;
int rightSize = right - mid;
int[] leftArr = new int[leftSize];
int[] rightArr = new int[rightSize];
System.arraycopy(arr, left, leftArr, 0, leftSize);
System.arraycopy(arr, mid + 1, rightArr, 0, rightSize);
int i = 0, j = 0, k = left;
while (i < leftSize && j < rightSize) {
if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
else arr[k++] = rightArr[j++];
}
while (i < leftSize) arr[k++] = leftArr[i++];
while (j < rightSize) arr[k++] = rightArr[j++];
}
}