This is the 44th article in the C language learning series.
Shell sort is one of the top ten sorting algorithms. Today, let’s unveil the mystery of Shell sort together.
This article will start from scratch, striving to use the most relatable language to help you fully understand it.
Shell Sort: Adding “Rocket Boosters” to Insertion Sort
Imagine you have a messy deck of playing cards. Now, if you were to sort them in ascending order, how would you do it?
Many people would use a method called “insertion sort”:
Pick up the first card; it is already sorted by itself.
Pick up the second card, compare it with the first, and insert it before or after the first card.
Pick up the third card, and find the appropriate position to insert it among the already sorted first two cards.
Repeat this process until all cards are inserted into their correct positions.
This method is simple and intuitive, but for a chaotic deck, you need to constantly search for insertion positions within the sorted part, resulting in a lot of “moving” operations, which is relatively inefficient.
It’s like trying to slowly fit one part into a machine that is already half-assembled, which is very laborious.
So, is there a way to make this “insertion” process faster?
The answer is yes! This is the genius of Shell sort.
Core Idea: Break it Down, Coarse to Fine
The core idea of Shell sort is very simple: if the entire sequence is basically sorted, then the efficiency of insertion sort will be very high.
What does “basically sorted” mean? It means that although the sequence is not completely neat, most elements are already close to their final positions, requiring no long-distance moves.
How can we make a chaotic sequence “basically sorted”?
The inventor of Shell sort, Donald Shell, came up with a brilliant idea: instead of comparing one by one, we first scatter the entire lineup and perform several “long-distance” arrangements, allowing elements to return to their areas in large strides, and then make fine adjustments.
The tool for this “scattering” and “long-distance arrangement” is the “gap”.
Logical Approach: Step by Step Understanding
Let’s simulate with a specific example. Suppose the array we want to sort is: [8, 9, 1, 7, 2, 3, 5, 4, 6, 0].
Step 1: Choose an initial gap
The gap is a step size. We first choose a relatively large gap, for example, gap = 5. This means we divide the entire array into 5 groups:
Group 1: 8, 3 (index 0, 5)
Group 2: 9, 5 (index 1, 6)
Group 3: 1, 4 (index 2, 7)
Group 4: 7, 6 (index 3, 8)
Group 5: 2, 0 (index 4, 9)
As you can see, we are no longer looking at adjacent elements, but rather taking one element every 5 positions to form a group.
Step 2: Perform insertion sort on each group
Now, we perform insertion sort on these 5 small groups as mentioned earlier.
Sort Group 1 [8, 3] -> [3, 8]
Sort Group 2 [9, 5] -> [5, 9]
Sort Group 3 [1, 4] -> [1, 4] (already sorted)
Sort Group 4 [7, 6] -> [6, 7]
Sort Group 5 [2, 0] -> [0, 2]
Now, the entire array becomes: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2].
Does it still look messy? But please feel the difference: compared to the initial [8, 9, 1, 7, 2, …], smaller numbers (like 0, 1, 2, 3) are now more on the left, and larger numbers (like 7, 8, 9) are more on the right. It is now “basically sorted”!
Step 3: Reduce the gap and continue grouping and sorting
Next, we reduce the gap, for example, halving it, gap = 2. Now we divide the array into 2 groups:
Group 1: 3, 1, 0, 9, 7 (index 0, 2, 4, 6, 8)
Group 2: 5, 6, 8, 4, 2 (index 1, 3, 5, 7, 9)
Again, we perform insertion sort on these two groups:
Sort Group 1 [3, 1, 0, 9, 7] -> [0, 1, 3, 7, 9]
Sort Group 2 [5, 6, 8, 4, 2] -> [2, 4, 5, 6, 8]
Now, the entire array becomes: [0, 2, 1, 4, 3, 5, 7, 6, 9, 8].
Wow! Isn’t it much neater? It is already very close to the final result.
Step 4: Final fine-tuning (standard insertion sort)
Finally, we set the gap to 1, gap = 1. What does this mean? It means we treat the entire array as one group and perform a standard insertion sort.
At this point, the array is [0, 2, 1, 4, 3, 5, 7, 6, 9, 8], which is already very ordered. Insertion sort is highly efficient for such nearly sorted arrays, requiring very few comparisons and moves to quickly complete the sorting.
Final result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
In summary, the essence of Shell sort:
By using a decreasing gap, the entire sequence is divided into several subsequences, each undergoing insertion sort. As the gap continues to shrink, the entire sequence becomes increasingly ordered. When the gap is 1, the entire sequence is already “basically sorted”, and a final insertion sort can efficiently complete the task.
It is like first using a coarse sieve to roughly separate big fish from small fish, then using a medium sieve for further separation, and finally using a fine sieve for precise separation. Each step creates better conditions for the next.
C Language Implementation Code
Having understood the above ideas, the code becomes very clear. Here we use a classic gap sequence: starting with half the length of the array, then halving it each time until we reach 1.
#include
// Shell sort function
void shellSort(int arr[], int n) {
// Initial gap is half the length of the array, then halved each time
for (int gap = n / 2; gap > 0; gap /= 2) {
// Starting from the gap-th element, perform insertion sort on each group
// Note: Here i++, which means we are processing one element in each group “in turn”
// instead of completely finishing one group before moving to the next, but the effect is the same, and the code is more concise.
for (int i = gap; i < n; i++) {
// Below is the standard insertion sort logic, but the comparison and move step is gap, not 1
int temp = arr[i]; // Current element to be inserted
int j;
// Within the same group (step size gap), find the insertion position for temp
// Move all elements greater than temp back by gap positions
for (j = i; j >= gap && arr[j – gap] > temp; j -= gap) {
arr[j] = arr[j – gap];
}
// Insert temp into the correct position
arr[j] = temp;
}
}
}
// A helper function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, arr[i]);
}
printf(“\n”);
}
// Main function to test Shell sort
int main() {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate array length
printf(“Array before sorting: \n”);
printArray(arr, n);
shellSort(arr, n); // Call the Shell sort function
printf(“Array after sorting: \n”);
printArray(arr, n);
return 0;
}
Key points of the code explained:
Outer loop for (int gap = n / 2; gap > 0; gap /= 2):
Controls the change of the gap, starting from n/2, halving each time until 1.
Middle loop for (int i = gap; i < n; i++):
This loop is very clever. It starts from gap and traverses the array. i points to the first element of the “unsorted part” in each group. By using i++, we are actually processing the next element to be sorted in different groups in turn, rather than finishing one group at a time. This makes the code more concise and has the same effect as processing each group separately.
Inner loop for (j = i; …; j -= gap):
This is the core of the insertion sort within the group. It starts from the current position i and compares forward with a step size of gap. If the previous element is greater than temp, it moves it back by gap positions. The loop continues until the position for temp is found.
I hope this detailed explanation of over 1000 words gives you a clear and profound understanding of Shell sort!
It is a great improvement over simple insertion sort, embodying the profound idea of “step-by-step refinement”.