YouTipShell Sort
## Shell Sort
Shell Sort is an efficient improved version of insertion sort, proposed by Donald Shell in 1959.
The core idea of Shell Sort is **to first divide the original list into multiple sub-sequences, perform insertion sort on each sub-sequence, then gradually reduce the interval of the sub-sequences, and finally perform a standard insertion sort on the entire list**. This method allows elements to move across large distances, thereby eliminating a large number of inverted pairs in the early stages, significantly improving sorting efficiency.
Imagine sorting a shuffled deck of cards. Insertion sort is like picking up cards one by one and inserting them into the correct position in the sorted pile in your hand. Shell Sort, on the other hand, is like first taking out cards at regular intervals to form a small pile and sorting it, then reducing the interval for taking cards and repeating this process. When the interval reduces to 1, it becomes a standard insertion sort, but by this time the entire sequence is already nearly sorted, so the final insertion sort will be very fast.
### Working Principle
The key to Shell Sort is the concept of an **increment sequence**. The increment sequence determines the interval for dividing sub-sequences each time. The algorithm performs multiple rounds of sorting on the list according to a gradually decreasing increment sequence.
### Algorithm Steps
1. **Select Increment Sequence**: Determine a sequence of integers from large to small, with the last increment must be 1. The most commonly used initial increment is half the array length, then repeatedly halved.
2. **Group by Increment**: For the current increment `gap`, divide the entire list into `gap` sub-sequences. Each sub-sequence consists of all elements spaced `gap` apart.
3. **Perform Insertion Sort on Sub-sequences**: Perform insertion sort on each sub-sequence separately.
4. **Reduce Increment**: Get a new, smaller increment and repeat steps 2 and 3.
5. **Final Sorting**: When the increment reduces to 1, perform a standard insertion sort on the entire list. By this time, the list is already nearly sorted, and the sorting completes quickly.
### Applicable Description
Shell Sort has a time complexity of O(n^(1.3-2)) and a space complexity of constant order O(1). Shell Sort is not as fast as quicksort algorithms with O(n(logn)) time complexity, so it performs well for medium-sized data but is not the optimal choice for very large data sets. In summary, it is much faster than general algorithms with O(n^2) complexity.
### Process Illustration
Shell Sort improves insertion sort to speed it up by exchanging non-adjacent elements to partially sort the array, and finally uses insertion sort to sort the locally sorted array.
Here we choose increment gap=length/2, and reduce the increment as gap = gap/2, using the sequence **{n/2,(n/2)/2...1}** to represent it.
As shown in the example:
(1) Initial increment, first pass gap = length/2 = 4
!(#)
(2) Second pass, increment reduced to 2
!(#)
(3) Third pass, increment reduced to 1, getting the final sorted result
!(#)
### Java Example Code
**Source Package Download:*The innermost loop is actually insertion sort:
## ShellSort.java File Code:
public class ShellSort {
//Core code---start
public static void sort(Comparable[] arr){
int j;
for(int gap = arr.length/2; gap >0; gap /=2){
for(int i = gap; i = gap && tmp.compareTo(arr)<0; j -= gap){
arr= arr;
}
arr= tmp;
}
}
}
//Core code---end
public static void main(String[] args){
int N =2000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
ShellSort.sort(arr);
for(int i =0; i 0:
# Starting from gap, perform "insertion sort" on each element
# Note: i ranges from gap to n-1, traversing all elements
for i in range(gap, n):
# Save arr to temporary variable temp
temp = arr
j = i
# Perform insertion sort on the sub-sequence for current gap
# If the preceding element in the same sub-sequence is greater than temp, move it backward
while j >= gap and arr> temp:
arr= arr
j -= gap
# Insert temp into the correct position
arr= temp
# Reduce increment, e.g., halve gap
gap //=2
return arr
# Test code
if __name__ =="__main__":
# Test data 1: Random unsorted
test_array =[8,3,5,1,4,2,7,6]
print("Before sorting:", test_array)
sorted_array = shell_sort(test_array.copy())# Use copy to avoid modifying original array
print("After sorting:", sorted_array)
# Test data 2: Contains duplicate elements
test_array2 =[5,2,9,5,2,3,5]
print("n Before sorting:", test_array2)
print("After sorting:", shell_sort(test_array2.copy()))
# Test data 3: Reverse sorted array
test_array3 =[10,9,8,7,6,5,4,3,2,1]
print("n Before sorting:", test_array3)
print("After sorting:", shell_sort(test_array3.copy()))
**Code Analysis:**
1. `def shell_sort(arr):` defines the Shell Sort function.
2. `n = len(arr)` gets the array length.
3. `gap = n // 2` initializes the increment. This is the classic starting increment sequence for Shell Sort.
4. `while gap > 0:` outer loop, controls the gradual reduction of increment until it becomes 0 (actually after executing with gap = 1, `gap //= 2` becomes 0 and exits).
5. `for i in range(gap, n):` inner loop. Starts traversing from index `gap`. `i` points to the current element to be inserted. Note that this loop cleverly handles all sub-sequences spaced by `gap` simultaneously.
6. `temp = arr` and `j = i`: saves the current element's value, and uses `j` to record where it should be inserted in the current sub-sequence.
7. `while j >= gap and arr > temp:` this is the core of insertion sort. Within the same sub-sequence (accessed via `j - gap` index to get the previous element), if the previous element is greater than `temp`, move the previous element backward by `gap` positions.
8. `arr = temp`: inserts the saved `temp` value into the correct position.
9. `gap //= 2`: after one round of sorting, halves the increment for the next round of more refined sorting.
10. `return arr`: returns the sorted array.
* * *
## Selection of Increment Sequence
The choice of increment sequence directly affects the performance of Shell Sort. Above we used Shell's original sequence (n/2, n/4, ..., 1), but it is not optimal. Below are several common increment sequences:
| Sequence Name | Generation Formula | Features and Complexity |
| --- | --- | --- |
| **Shell's Original Sequence** | $gap = lfloor frac{n}{2} rfloor, gap = lfloor frac{g