Sorting Algorithms in Java with Time Complexity# Sorting Algorithms in Java with Time Complexity
Sorting is a fundamental operation in computer science that arranges elements in a specific order, either ascending or descending. Java provides several ways to sort data using different algorithms. Below are some of the most commonly used sorting algorithms with their time complexities and Java implementations.
1. Bubble Sort
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.
Time Complexity:
- Best Case: O(n) (already sorted array)
- Average Case: O(n²)
- Worst Case: O(n²)
Java 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;
}
}
}
}
}Explanation:
- Inner Loop: Compares adjacent elements and swaps them if they are out of order.
- Outer Loop: Ensures that the process repeats until the array is sorted.
- Inefficiency: Due to repetitive comparisons and swaps, Bubble Sort is inefficient for large datasets.
2. Selection Sort
Selection Sort divides the array into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the first unsorted element.
Time Complexity:
- Best Case: O(n²)
- Average Case: O(n²)
- Worst Case: O(n²)
Java 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[minIndex] with arr[i]
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}Explanation:
- Selection: The algorithm finds the smallest element in the unsorted part and moves it to the sorted part.
- Efficiency: Fewer swaps than Bubble Sort but still inefficient for large datasets due to nested loops.
3. Insertion Sort
Insertion Sort works by building a sorted array one element at a time. It takes each element and inserts it into its correct position within the already sorted part of the array.
Time Complexity:
- Best Case: O(n) (already sorted array)
- Average Case: O(n²)
- Worst Case: O(n²)
Java 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--;
}
arr[j + 1] = key;
}
}
}Explanation:
- Shifting Elements: It shifts elements of the sorted section to find the correct place for the new element.
- Efficient for Small Arrays: Performs well for small or partially sorted arrays but becomes inefficient with larger datasets.
4. Merge Sort
Merge Sort is a divide-and-conquer algorithm that splits the array into two halves, recursively sorts them, and then merges the sorted halves back together.
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Java 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);
}
}
public static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int i = 0; i < n2; i++) right[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
}Explanation:
- Divide and Conquer: Divides the array into halves and recursively sorts each half.
- Efficiency: It has an excellent time complexity of O(n log n) but requires additional space for merging.
5. Quick Sort
Quick Sort also follows the divide-and-conquer approach. It selects a "pivot" element and partitions the array such that elements smaller than the pivot are on the left and those larger are on the right. Then, it recursively sorts the left and right partitions.
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n²) (when pivot is the smallest or largest element)
Java Implementation:
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public 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;
}
}Explanation:
- Partitioning: The key operation is the partitioning step, which rearranges the array such that all elements less than the pivot come before it and all elements greater than the pivot come after it.
- Efficient for Large Arrays: Quick Sort is one of the fastest algorithms for large datasets, although its worst-case complexity is O(n²).
6. Heap Sort
Heap Sort uses a binary heap data structure. It first builds a max heap from the input array and then repeatedly extracts the largest element and rebuilds the heap.
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Java Implementation:
public class HeapSort {
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);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
}Explanation:
- Binary Heap: It ensures the array is partially sorted by maintaining a max heap structure.
-
Efficiency: Like Merge Sort and
Quick Sort, Heap Sort has a time complexity of O(n log n) but it’s not as fast as Quick Sort in practice.
Conclusion:
Choosing the right sorting algorithm depends on your requirements. For small arrays, Insertion Sort is often a good choice due to its simplicity. For larger datasets, Quick Sort and Merge Sort are more suitable due to their time efficiency. Heap Sort is useful in certain cases, while Bubble Sort and Selection Sort are generally not recommended for large datasets due to their O(n²) time complexity.
Happy Coding!