Updated April 10, 2023
Definition of Shell sort C
The Shell sort in C is used to sorts the array by sort the pair of elements far apart from each other, then successively reduces the gap between the elements to be sorted. The Shell sort is the version of the insertion sort algorithm. In insertion sort, the element moves one position ahead to insert an element at its correct position, whereas the shell sort exchanges the far elements. If an element has to move far ahead many moves are required. The shell sort starts by sorting the pair of elements that are far apart from each other and successively interval between them. It can transfer some out-of-place elements into the correct place faster than a simple nearest-neighbor exchange if it starts with far apart elements. Shell sort is not a stable sorting algorithm since it ignores the items that fall in between the intervals. The worst-case running time complexity of the shell sort is O(n2) and the best-case running time complexity is O(nlog(n)).
The algorithm of the shell sort –
Shell_Sort( a, length)
for interval x <- length / 2n down to 1
for each interval "x" in a
sort all the elements at interval "x"
end shell_SortReturn value – The return value of this method is the sorted array.
Working of the shell sort in C
Working of the shell sort in C are as followa:
1. Let the specified array is:
Given array: [8, 7, 2, 6, 4, 5, 4, 0]2. In our algorithm, we use the shell’s original sequence (N/2, N/4,…1) as intervals. If the array size is N = 8, the elements in the interval of N/2 = 4 are compared and swapped if they are out of order in the first loop.
The 0th element and the 4th element are compared.
If the 0th element is greater than the 4th, the 4th element is stored first in the temp variable, followed by the 0th element (i.e. greater element) in the 4th position, and the element stored in temp in the 0th position and rearrange the elements in an n/2 interval.
array: [4, 7, 2, 6, 8, 5, 3, 0], temp = 4This procedure is repeated for all the remaining elements and rearranges the elements in an n/2 interval. we get the array:
array: [4, 5, 2, 0, 8, 7, 3, 6]3. In the second cycle, an interval of N/4 = 8/4 = 2 is chosen, and the elements that fall within this range are sorted once more and rearrange the elements in an n/4 interval.
array: [2, 5, 4, 0, 8, 7, 3, 6]4. The 4th and 2nd place elements are compared. Also contrasted are the elements in the 2nd and 0th positions. The current interval is used to compare all of the elements in the sequence.
array: [2, 5, 4, 0, 8, 7, 3, 6]This procedure is repeated for all the remaining elements and rearranges the elements in an n/2 interval. we get the array:
array: [2, 0, 3, 5, 4, 7, 8, 6]5. Next, the array elements in the interval of 1 are sorted when the interval is N/8 = 8/8 =1. The array has now been sorted absolutely and rearrange the elements in an n/8 interval.
array: [2, 0, 3, 5, 4, 7, 8, 6]
array: [0, 2, 3, 5, 4, 7, 8, 6]
array: [0, 2, 3, 5, 4, 7, 8, 6]
array: [0, 2, 3, 4, 5, 7, 8, 6]
array: [0, 2, 3, 4, 5, 7, 8, 6]
array: [0, 2, 3, 4, 5, 7, 8, 6]
array: [0, 2, 3, 4, 5, 7, 8, 6]
array: [0, 2, 3, 4, 5, 6, 7, 8]Examples for the shell sort in C
Example for shell sort in C to sort the array of numbers.
Example #1
Code:
#include <stdio.h>
void print(int a[], int s) {
int i;
for (i = 0; i < s; ++i) {
printf( "%d ", a[i]);
}
}
void shell_Sort(int a[], int s) {
int gap, i;
for (gap = s / 2; gap > 0; gap /= 2) {
for ( i = gap; i < s; i += 1) {
int temp = a[i];
int j;
for (j = i; j >= gap && a[j - gap] > temp; j -= gap) {
a[j] = a[j - gap];
}
a[j] = temp;
}
}
}
int main() {
int array[] = { 8, 2, 5, 9, 3, 1, 0 };
int size = sizeof( array ) / sizeof( array[0] );
shell_Sort(array, size);
printf("The sorted array is : \n");
print(array, size);
}An output of the above code is –
As in the above program, the shell_Sort() function is created to sort the number array. Inside the function, the first for loop creates the half of the gap, the second loop perform a gapped insertion sort, if the first gap elements a[0..gap-1] are already gap sorted, then add one more element before the entire array is gap sorted, and the third for loop shift the earlier gap-sorted elements until the correct location for a[i] is found. Then finally, copy the temp to the original array and printing all the sorted array by using the print() function, as we can see in the above output.
Rewrite the above program to sort the character array.
Example #2
Code:
#include <stdio.h>
void print(char a[], int s) {
int i;
for (i = 0; i < s; ++i) {
printf( "%c ", a[i]);
}
}
void shell_Sort(char a[], int s) {
int gap,i;
for (gap = s / 2; gap > 0; gap /= 2) {
for ( i = gap; i < s; i += 1) {
char temp = a[i];
int j;
for (j = i; j >= gap && a[j - gap] > temp; j -= gap) {
a[j] = a[j - gap];
}
a[j] = temp;
}
}
}
int main() {
char array[] = { 'h', 'e', 'l', 'l', 'o' };
int size = sizeof( array ) / sizeof( array[0] );
shell_Sort(array, size);
printf("The sorted array is : \n");
print(array, size);
}An output of the above code is –
As in the above program, the shell_Sort() function is created to sort the character array. Inside the function, the first for loop creates the half of the gap, the second loop perform a gapped insertion sort, if the first gap elements a[0..gap-1] are already gap sorted, then add one more element before the entire array is gap sorted, and the third for loop shift the earlier gap-sorted elements until the correct location for a[i] is found. Then finally, copy the temp to the original array and printing all the sorted array by using the print() function, as we can see in the above output.
Conclusion
The shell sort in C is used to sorts the array by sort the pair of elements far apart from each other, then successively reduces the gap between the elements to be sorted.
Recommended Articles
This is a guide to Shell sort C. Here we discuss definition, syntax, and parameters, working of the shell sort in C examples with code implementation. You may also have a look at the following articles to learn more –
