Integrating Some Algorithms and Animations#
Bubble Sort#
Bubble Sort is a simple sorting algorithm that repeatedly traverses the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until no more swaps are needed, resulting in a sorted list.
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Mark whether a swap has occurred; if not, sorting is complete
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
// Compare adjacent elements; swap if in the wrong order
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no swaps occurred, the array is sorted; exit the loop early
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Selection Sort#
The basic idea is to repeatedly select the smallest (or largest) element from the unsorted portion of the sequence and place it at the beginning, continuing this process until all elements are sorted.
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Assume the current element is the minimum in the unsorted portion
int minIndex = i;
// Find the minimum in the remaining unsorted portion
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum with the current element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Insertion Sort#
Consider the first element of the unsorted sequence as a sorted sequence, treating the second element to the last element as the unsorted sequence.
Scan the unsorted sequence from start to end, inserting each scanned element into the appropriate position in the sorted sequence. (If the element to be inserted is equal to an element in the sorted sequence, insert it after the equal element.)
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // Current element to insert
int j = i - 1;
// Look for elements greater than the current element, moving them back
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert at the correct position
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Quick Sort#
Quick Sort is an efficient sorting algorithm developed by Tony Hoare. On average, sorting n elements requires Ο(nlogn) comparisons, while in the worst case, it may require Ο(n²) comparisons, though this rarely occurs. In fact, Quick Sort is usually faster than other Ο(nlogn) algorithms because its inner loop can be efficiently implemented on most hardware architectures.
Quick Sort sorts a sequence (list) by dividing it into two sub-sequences (sub-lists) using the divide-and-conquer method. As a classic application of the divide-and-conquer idea in sorting algorithms, Quick Sort is essentially an extension of the recursive divide-and-conquer method based on Bubble Sort.
The worst-case runtime of Quick Sort is O(n²), such as in the case of a sorted sequence. However, its average expected time is O(nlogn), and the constant factor implied in the O(nlogn) notation is very small, much smaller than that of Merge Sort, which has a stable complexity of O(nlogn). Therefore, for the vast majority of weakly ordered random sequences, Quick Sort is always superior to Merge Sort.
public class QuickSort {
// Main method for testing
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
quickSort(array, 0, array.length - 1);
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
// Main method for Quick Sort
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1); // Sort left half
quickSort(array, pivotIndex + 1, high); // Sort right half
}
}
// Partition method, choosing a pivot and partitioning
private static int partition(int[] array, int low, int high) {
int pivot = array[high]; // Choose the rightmost element as the pivot
int i = low - 1; // i is the index of the smaller element
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j); // Swap elements smaller than the pivot to the left
}
}
swap(array, i + 1, high); // Place the pivot in the correct position
return i + 1; // Return the pivot's position
}
// Swap two elements in the array
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Shell Sort#
Shell Sort, also known as the diminishing increment sort algorithm, is an efficient improvement over insertion sort, but it is not a stable sorting algorithm.
The improvement of Shell Sort is mainly based on two key characteristics of insertion sort:
- Insertion sort is efficient for nearly sorted data: When the data is almost sorted, the efficiency of insertion sort can approach linear.
- Limitations of insertion sort: Insertion sort can only move one element at a time, which makes it inefficient for handling large unsorted data.
The basic idea of Shell Sort is:
- Group sorting: First, divide the sequence to be sorted into several smaller sub-sequences and perform insertion sort on these sub-sequences. The grouping of sub-sequences is done using a decreasing increment (gap). Initially, the gap is large, and as sorting progresses, the gap gradually decreases.
- Final sorting: When the gap reduces to 1, the entire sequence is "almost sorted," and a single insertion sort on all records can complete the sorting.
The key to Shell Sort lies in choosing a reasonable increment sequence. Different increment sequences can significantly affect the efficiency of sorting, with common increment sequences starting at n/2 and gradually decreasing to 1.
public class ShellSort {
// Main method for testing
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
shellSort(array);
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
// Shell sort method
public static void shellSort(int[] array) {
int n = array.length;
// Initial gap set to half the array length
for (int gap = n / 2; gap > 0; gap /= 2) {
// Perform insertion sort for each gap value
for (int i = gap; i < n; i++) {
int temp = array[i];
int j = i;
// Perform insertion sort for the current element
while (j >= gap && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
}
}
Merge Sort#
Merge Sort is an effective sorting algorithm based on the divide-and-conquer method. Its basic idea is to recursively split the sequence to be sorted into two sub-sequences until each sub-sequence contains only one element, and then gradually merge these sub-sequences into a sorted sequence. Merge Sort can be implemented in two ways: top-down recursive implementation and bottom-up iterative implementation.
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy arr to avoid changing the parameter content
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
Heap Sort#
Heap Sort is an effective sorting algorithm based on the heap data structure. It uses the properties of heaps to achieve sorting, typically using a max heap or min heap. The basic idea of Heap Sort is to convert the sequence to be sorted into a heap, then gradually extract the maximum or minimum value from the heap and adjust the heap structure to achieve sorting.
Basic Steps of Heap Sort:#
-
Build the heap: Convert the array to be sorted into a max heap (or min heap). In a max heap, the value of each parent node is not less than that of its child nodes. In a min heap, the value of each parent node is not greater than that of its child nodes.
-
Sorting:
- Extract the root node (maximum or minimum value) from the heap and swap it with the last element of the heap.
- Re-adjust the heap to restore the heap property.
- Repeat the above steps until the heap is empty.
public class HeapSort {
// Main method for testing
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
heapSort(array);
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
// Heap sort method
public static void heapSort(int[] array) {
int n = array.length;
// Build the max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// Extract elements from the heap
for (int i = n - 1; i > 0; i--) {
// Swap the root node (maximum value) to the end of the array
swap(array, 0, i);
// Re-adjust the heap
heapify(array, i, 0);
}
}
// Method to adjust the heap, ensuring the subtree rooted at i satisfies the max heap property
private static void heapify(int[] array, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// If left child is larger
if (left < n && array[left] > array[largest]) {
largest = left;
}
// If right child is larger
if (right < n && array[right] > array[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
swap(array, i, largest);
// Recursively adjust the subtree
heapify(array, n, largest);
}
}
// Swap two elements in the array
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Counting Sort#
Counting Sort is a linear time complexity sorting algorithm suitable for scenarios with a limited range of integers. Its basic idea is to determine the position of each element by counting the occurrences of each element, thus completing the sorting. Here are the basic steps of Counting Sort:
- Determine the range: First, determine the maximum and minimum values of the elements to be sorted. This range will determine the size of the counting array to be created.
- Create the counting array: Create a counting array based on the range of elements. The index of the array represents the value of the elements to be sorted, and the value of the array represents the count of occurrences of that value.
- Count the occurrences of elements: Traverse the original data, incrementing the value at the corresponding index of the counting array for each element.
- Calculate cumulative counts: Perform a cumulative sum on the counting array to determine the final position of each element.
- Generate the sorted result: Based on the information in the cumulative counting array, place the elements in the correct position to generate the sorted array.
import java.util.Arrays;
public class CountingSort {
public static void countingSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
// Find the maximum value in the array
int max = Arrays.stream(array).max().orElse(Integer.MAX_VALUE);
// Create and initialize the counting array
int[] count = new int[max + 1];
// Count the occurrences of each element
for (int num : array) {
count[num]++;
}
// Convert the counting array to a cumulative counting array
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// Generate the sorted result based on the cumulative counting array
int[] sortedArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// Copy the sorted result back to the original array
System.arraycopy(sortedArray, 0, array, 0, array.length);
}
public static void main(String[] args) {
int[] array = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original array: " + Arrays.toString(array));
countingSort(array);
System.out.println("Sorted: " + Arrays.toString(array));
}
}
Bucket Sort#
Bucket Sort is a distribution-based sorting algorithm, particularly suitable for cases where the input data is uniformly distributed. It distributes elements into multiple buckets, sorts the elements within each bucket individually, and finally merges all the sorted elements from the buckets to complete the sorting.
Basic Steps of Bucket Sort#
- Create buckets: Based on the range and distribution of the input data, create a certain number of buckets. Each bucket represents an interval.
- Distribute elements into buckets: Traverse the input array and place each element into the corresponding bucket based on its value.
- Sort the elements within each bucket: Choose an appropriate sorting algorithm (such as insertion sort or quick sort) to sort the elements within each bucket.
- Merge the sorted results of all buckets: Concatenate the elements from each bucket in order to form the final sorted array.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(float[] array) {
if (array == null || array.length == 0) {
return;
}
// Create buckets
int numberOfBuckets = array.length;
List<Float>[] buckets = new ArrayList[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++) {
buckets[i] = new ArrayList<>();
}
// Distribute elements into buckets
for (float num : array) {
int bucketIndex = (int) (num * numberOfBuckets); // Determine the bucket position
buckets[bucketIndex].add(num);
}
// Sort the elements within each bucket
for (List<Float> bucket : buckets) {
Collections.sort(bucket);
}
// Merge the sorted results of all buckets
int index = 0;
for (List<Float> bucket : buckets) {
for (float num : bucket) {
array[index++] = num;
}
}
}
public static void main(String[] args) {
float[] array = {0.42f, 0.32f, 0.73f, 0.25f, 0.67f, 0.48f, 0.12f, 0.89f, 0.94f, 0.36f};
System.out.println("Original array: ");
for (float num : array) {
System.out.print(num + " ");
}
System.out.println();
bucketSort(array);
System.out.println("Sorted: ");
for (float num : array) {
System.out.print(num + " ");
}
}
}
Radix Sort#
Radix Sort is a non-comparative integer sorting algorithm suitable for sorting integers or fixed-length strings. Radix Sort sorts by digits or by the number of digits, performing multiple rounds of sorting from the least significant digit (LSD) to the most significant digit (MSD), ultimately achieving a sorted array.
Basic Idea of Radix Sort#
The core idea of Radix Sort is to sort the numbers to be sorted by their digits (from low to high or from high to low). Since Radix Sort relies on sorting each digit, it typically uses a stable sorting algorithm (such as Counting Sort or Bucket Sort) to ensure that the relative order of elements with the same digit is maintained after each round of sorting.
Steps of Radix Sort#
- Determine the number of digits of the maximum value: Find the number of digits of the maximum element in the array, which will determine the number of sorting rounds.
- Sort starting from the least significant digit: Starting from the least significant digit, sort the numbers based on each digit. A stable sorting algorithm, such as Counting Sort, can be used for sorting.
- Repeat: Sort each higher digit in turn until the most significant digit is reached.
- Final sorted result: After sorting all digits, the array will be sorted.
Example#
Suppose we want to perform Radix Sort on the integer array [170, 45, 75, 90, 802, 24, 2, 66]:
-
Determine the number of digits of the maximum value: The maximum value
802has 3 digits, so sorting will require 3 rounds. -
First round (sort by units):
- Sorting result:
[170, 90, 802, 2, 24, 45, 75, 66]
- Sorting result:
-
Second round (sort by tens):
- Sorting result:
[802, 2, 24, 45, 66, 170, 75, 90]
- Sorting result:
-
Third round (sort by hundreds):
- Sorting result:
[2, 24, 45, 66, 75, 90, 170, 802]
- Sorting result:
import java.util.*;
public class RadixSortWithHashMap {
// Get the maximum value in the array to determine the number of sorting rounds
private static int getMax(int[] array) {
int max = array[0];
for (int num : array) {
if (num > max) {
max = num;
}
}
return max;
}
// Use HashMap to implement Counting Sort
private static void countingSortWithHashMap(int[] array, int exp) {
// HashMap to store the corresponding list for each digit
Map<Integer, List<Integer>> countMap = new HashMap<>();
// Initialize the HashMap with keys (0-9) and corresponding lists
for (int i = 0; i < 10; i++) {
countMap.put(i, new ArrayList<>());
}
// Place elements into the corresponding HashMap lists based on each digit
for (int num : array) {
int digit = (num / exp) % 10;
countMap.get(digit).add(num);
}
// Write back the elements from the HashMap to the array in order of keys (0 to 9)
int index = 0;
for (int i = 0; i < 10; i++) {
for (int num : countMap.get(i)) {
array[index++] = num;
}
}
}
// Main Radix Sort function
public static void radixSort(int[] array) {
// Find the maximum number to determine the number of rounds
int max = getMax(array);
// Perform counting sort for each digit starting from the least significant digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortWithHashMap(array, exp);
}
}
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original array: " + Arrays.toString(array));
radixSort(array);
System.out.println("Sorted: " + Arrays.toString(array));
}
}
This article is synchronized and updated to xLog by Mix Space Original link: https://me.liuyaowen.club/posts/default/20240821and3