Implementing Bucket Sort Algorithm in C++
Bucket sort is a non-comparison sorting algorithm that sorts elements by distributing them into multiple "buckets", sorting each bucket individually, and then merging the sorted buckets. The core is to reasonably partition the buckets so that each bucket contains a small number of elements, thereby reducing the sorting cost. Taking floating-point numbers in the range [0,1) as an example, the algorithm steps are as follows: 1. Create n empty buckets (where n is the length of the array); 2. Assign each element x to the corresponding bucket using the bucket index calculated as the integer part of x * n; 3. Sort each bucket using std::sort; 4. Merge all elements from the buckets. In the C++ implementation, the `bucketSort` function creates n buckets using a vector of vectors of doubles, distributes elements into the buckets through traversal, sorts each bucket, and then merges the results. Testing verifies the correctness of the algorithm. Complexity analysis: The average time complexity is O(n) (when elements are uniformly distributed), and the worst-case time complexity is O(n log n) (when all elements are placed in the same bucket). The space complexity is O(n). It is suitable for numerical data with uniformly distributed values and a clear range; performance degrades when data distribution is uneven. This algorithm is efficient when the data distribution is reasonable, especially suitable for sorting interval data in statistical analysis.
Read MoreImplementing the Shell Sort Algorithm in C++
Shell Sort is an improved version of Insertion Sort, also known as "diminishing increment sort". It efficiently sorts arrays by performing insertion sorts on grouped subsequences and gradually reducing the increment. The basic idea is: select an initial increment `gap` (e.g., half the array length), group elements with intervals of `gap` (forming subsequences), perform insertion sort on each group; repeat by reducing `gap` (usually halving it) until `gap=1` to complete the overall sorting. Core principle: Larger `gap` reduces the number of moves by grouping, while smaller `gap` leaves the array partially sorted, significantly lowering the total number of moves in the final insertion sort. For instance, take the array `[12, 34, 54, 2, 3]` – after initial `gap=2` grouping and sorting, the array becomes more ordered, and then `gap=1` completes the final sort. The code implements Shell Sort with three nested loops: the outer loop controls the `gap`, the middle loop iterates through each group, and the inner loop shifts elements. The average time complexity is `O(n^1.3)` (dependent on the increment), with the worst-case `O(n²)`, and a space complexity of `O(1)`. It is unstable. By optimizing insertion sort through grouping, Shell Sort is suitable for larger arrays. Its core logic lies in "grouping → sorting → reducing increment → final sorting".
Read MoreImplementing the Selection Sort Algorithm in Java
Selection sort is a simple and intuitive sorting algorithm. Its core idea is to repeatedly select the smallest (or largest) element from the unsorted portion and place it at the end of the sorted portion until the entire array is sorted. The basic approach involves an outer loop to determine the end position of the sorted portion, and an inner loop to find the minimum value in the unsorted portion, followed by swapping this minimum value with the element at the current position of the outer loop. In Java implementation, the `selectionSort` method is implemented with two nested loops: the outer loop iterates through the array (with `i` ranging from 0 to `n-2`), and the inner loop (with `j` ranging from `i+1` to `n-1`) finds the index `minIndex` of the minimum value in the unsorted portion. Finally, the element at position `i` is swapped with the element at `minIndex`. Taking the array `{64, 25, 12, 22, 11}` as an example, the sorted array `[11, 12, 22, 25, 64]` is gradually constructed through each round of swaps. The time complexity is O(n²), making it suitable for small-scale data. This algorithm has a simple logic and easy-to-implement code, serving as a typical example for understanding the basic sorting concepts.
Read More