▼For more exciting recommendations, please follow us ▼
Source: Embedded Linux | Typesetting: Mastering Embedded Systems
Shell sort is very similar to insertion sort, resembling an upgraded version of insertion sort.Shell sort is a sorting algorithm proposed by Donald Shell in 1959. It is also a type of insertion sort, which is a more efficient version of the simple insertion sort after improvements, also known as diminishing increment sort, and it is one of the first algorithms to break the O(n^2) barrier..Shell sort is also a type of insertion sort algorithm, but it breaks through the boundaries of insertion sort, reaching another peak that reduces the time complexity to “O(nLogn)~O(n^2)“.
Assuming we need to sort the following data:
Combining with previous articles, we know that the insertion sort of two data involves comparing their sizes and then arranging them.Shell sort is performed through grouping + insertion.First, we have 8 elements to sort, and we need to divide the data into 8/2=4 groups, as shown in the figure below:
After performing insertion sort on the above 4 groups, we get:
Then, we continue to group 8➗2➗2=2 into 2 groups:
These two groups of data are then subjected to insertion sort, as shown in the figure below:
After this, the sorting of the entire data set is almost complete.On this basis, we perform one more insertion sort on the entire queue, which will complete the sorting of the entire queue. Since the data has already been sorted, the efficiency will be significantly improved during the subsequent insertion sort.
The entire process can be viewed in the animated image:
Let’s take a look at the code implementation:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int shell_sort(int arr[],int n)
{
register int i, j, tmp;
int step;
for(step = n/2; step > 0; step /= 2) /* Increment step length */
{
/* step = 4 2 1 */
for(i = step; i < n; i++)
{
tmp = arr[i];
j = i - step;
for(; j >= 0 && tmp < arr[j];)
{
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = tmp;
}
}
}
#define LENGTH 8
int main(int argc, int *argv[])
{
int i;
int arr[LENGTH] = {6,5,3,1,8,7,2,4};
for(i=0; i<LENGTH; i++)
printf("%d ", arr[i]);
printf("\n");
shell_sort(arr, LENGTH);
for(i = 0; i < LENGTH; i++)
printf("%d ", arr[i]);
printf("\n");
}
Code output:
6 5318724
12345678
Next is the code image analysis, when the step length is equal to 4, the first insertion sort is performed:
When the step length is equal to 2, the second insertion sort is performed:
When the step length is equal to 1, the third insertion sort is performed. The specific process can be found in the article on insertion sort:
After the last insertion sort, the sorted sequence will be obtained:
👉 What exactly is an algorithm?👉C Language, dynamically demonstrating classic sorting algorithms👉At 90 years old, he changed the world with algorithms!👉Is the CAN bus a digital signal or an analog signal?👉Oh no! I bought a fake chip👉Reviewing some tools commonly used by electronic engineers