Sorting Algorithms: Java Implementation and Comparison
Implementation and analysis of common sorting algorithms (Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort) in Java, including time and space complexity comparison.
Sorting Algorithms in Competitive Programming (Java)
Introduction to Sorting Algorithms
Sorting is a fundamental operation in computer science, arranging elements of a collection (e.g., an array or list) into a specific order. This order is typically numerical or lexicographical. Efficient sorting algorithms are crucial for various applications, including database management, search engines, and, importantly, competitive programming. The right sorting algorithm can dramatically impact the performance of your solution, especially when dealing with large datasets.
Overview of Sorting Algorithms and Their Importance in Competitive Programming
In competitive programming, the choice of sorting algorithm can be the difference between acceptance and "Time Limit Exceeded" (TLE). Understanding the characteristics of different algorithms allows you to choose the most appropriate one for the given problem constraints. Here's a brief overview of commonly used sorting algorithms:
- Bubble Sort: Simple to understand but inefficient for large datasets. Mostly used for educational purposes.
- Selection Sort: Similar to Bubble Sort in terms of simplicity and inefficiency for larger problems.
- Insertion Sort: Efficient for small datasets or nearly sorted data. Can be useful as a part of more complex algorithms like hybrid sorting.
- Merge Sort: A divide-and-conquer algorithm with guaranteed O(n log n) time complexity. Generally preferred for large datasets when stability is required (maintains the relative order of equal elements).
- Quick Sort: Another divide-and-conquer algorithm, often the fastest in practice. However, its worst-case time complexity is O(n^2). Can be optimized to mitigate this risk.
- Heap Sort: Guarantees O(n log n) time complexity and sorts in-place (minimal extra space). Less commonly used than Merge Sort or Quick Sort.
- Counting Sort: Efficient for sorting integers within a known, limited range. Has a time complexity of O(n + k), where k is the range of input values. Not a general-purpose sorting algorithm.
- Radix Sort: Sorts based on the digits of the numbers. Useful for sorting integers. Can be faster than comparison-based sorts in certain scenarios.
The importance lies in selecting the algorithm that best fits the problem's requirements. Consider factors like:
- Dataset Size: For large datasets, algorithms with O(n log n) complexity (Merge Sort, Quick Sort, Heap Sort) are generally preferred.
- Input Distribution: Is the data nearly sorted? Insertion Sort might be a good choice. Are the values within a small range? Consider Counting Sort.
- Space Complexity: Does the problem have strict memory constraints? In-place algorithms like Heap Sort or Quick Sort might be necessary.
- Stability: Is maintaining the relative order of equal elements important? Merge Sort is a stable sorting algorithm.
Time and Space Complexity Analysis
Understanding time and space complexity is fundamental to algorithm analysis. Time complexity describes how the runtime of an algorithm grows as the input size increases. Space complexity describes how much memory the algorithm requires.
Big O Notation: We use Big O notation to express the upper bound of an algorithm's growth rate. For example:
- O(1): Constant time (e.g., accessing an element in an array by its index).
- O(log n): Logarithmic time (e.g., binary search).
- O(n): Linear time (e.g., iterating through an array once).
- O(n log n): Linearithmic time (e.g., Merge Sort, Quick Sort (average case), Heap Sort).
- O(n^2): Quadratic time (e.g., Bubble Sort, Selection Sort, Insertion Sort (worst case), Quick Sort (worst case)).
- O(n^3): Cubic time.
- O(2^n): Exponential time.
- O(n!): Factorial time.
Space Complexity: Describes the amount of memory an algorithm uses. We consider:
- O(1): Constant space (e.g., using a few fixed-size variables). Also referred to as in-place.
- O(n): Linear space (e.g., creating a copy of an array).
- O(n log n): (Less common, but can occur in recursive algorithms).
In competitive programming, time and space complexity are critical constraints. You must choose an algorithm that can solve the problem within the given time and memory limits. The problem statement typically specifies these limits.
Sorting Algorithms in Java with Solutions
1. Bubble Sort
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It is simple but inefficient.
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+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; ++i)
System.out.print(arr[i] + " ");
}
} Time Complexity: O(n^2) (worst and average case), O(n) (best case, when the array is already sorted).
Space Complexity: O(1) (in-place).
2. Selection Sort
Selection Sort repeatedly finds the minimum element from the unsorted portion of the list and places it at the beginning.
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
selectionSort(arr);
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; ++i)
System.out.print(arr[i] + " ");
}
} Time Complexity: O(n^2) (worst, average, and best case).
Space Complexity: O(1) (in-place).
3. Insertion Sort
Insertion Sort iterates through the list and inserts each element into its correct position in the sorted portion of the list.
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;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; ++i)
System.out.print(arr[i] + " ");
}
} Time Complexity: O(n^2) (worst and average case), O(n) (best case, when the array is already sorted).
Space Complexity: O(1) (in-place).
4. Merge Sort
Merge Sort divides the list into smaller sublists, recursively sorts them, and then merges them back together.
public class MergeSort {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
// Find sizes of the two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temporary arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temporary arrays */
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];
/* Initial indexes of first and second subarrays */
int i = 0, j = 0;
/* Initial index of merged subarray array */
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++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using merge()
void sort(int arr[], int l, int r) {
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2; // Same as (l+r)/2, but avoids overflow for large l and r
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Driver method
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("Sorted array");
printArray(arr);
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
} Time Complexity: O(n log n) (worst, average, and best case).
Space Complexity: O(n) (due to the temporary arrays used in the merge operation). Can be implemented in-place, but it's more complex.
5. Quick Sort
Quick Sort picks an element as a pivot and partitions the list around the pivot, such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the sublists.
public class QuickSort {
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[pi] is now
at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n - 1);
System.out.println("sorted array");
printArray(arr);
}
} Time Complexity: O(n log n) (average case), O(n^2) (worst case). The worst case occurs when the pivot is consistently the smallest or largest element.
Space Complexity: O(log n) (average case, due to recursion depth), O(n) (worst case). Can be made O(1) with an in-place iterative approach, but it's more complex to implement.
6. Heap Sort
Heap Sort uses a binary heap data structure. First, it builds a max-heap from the input array and then repeatedly extracts the maximum element from the heap and places it at the end of the array.
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
} Time Complexity: O(n log n) in all cases (worst, average, and best).
Space Complexity: O(1) because it's an in-place sorting algorithm.
7. Counting Sort
Counting Sort is an efficient sorting algorithm that is suitable for sorting collections of objects according to keys that are small integers. It works by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.
public class CountingSort {
public void sort(int[] arr) {
int n = arr.length;
// Find the maximum element of the array
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// Create a counting array
int[] count = new int[max + 1];
// Initialize the counting array to zero
for (int i = 0; i < count.length; i++) {
count[i] = 0;
}
// Store the count of each element
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// Modify the count array to store the cumulative count
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// Create a sorted array
int[] sortedArray = new int[n];
// Find the index of each element of the original array in count array, and
// place the elements in the sorted array
for (int i = n - 1; i >= 0; i--) {
sortedArray[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the sorted array back into the original array
for (int i = 0; i < n; i++) {
arr[i] = sortedArray[i];
}
}
// A utility function to print array of size n
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
CountingSort ob = new CountingSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
} Time Complexity: O(n + k), where n is the number of elements in the input array and k is the range of input values (max - min + 1).
Space Complexity: O(k), as it requires an auxiliary array of size k to store the counts.
8. Radix Sort
Radix Sort sorts elements by processing individual digits. It requires knowing the maximum value of the array to find how many digits exist, then using the counts to sort accordingly.
import java.util.Arrays;
public class RadixSort {
// A function to get maximum value in arr[]
static int getMax(int arr[], int n) {
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp) {
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count, 0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void radixsort(int arr[], int n) {
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
static void print(int arr[], int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver program to test above functions
public static void main(String[] args) {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
} Time Complexity: O(nk), where n is the number of elements and k is the number of digits in the largest number. Often written as O(wn) where w is the word size.
Space Complexity: O(n+k), where n is the input size and k is the range of digits (0-9 for decimal numbers).