Shell sort is an in-place comparison sort that generalizes the insertion sort algorithm, allowing the exchange of items that are far apart. The idea is to arrange the list of elements to start anywhere, taking every nth element to produce a sorted list. This n-sorted list is then sorted using insertion sort. The unique feature of shell sort is how it reduces the amount of shifting required by insertion sort, By initially sorting items far apart from each other and progressively reducing the gap between elements to be compared. In this article, we will explore shell sort and write a C program that sorts an array by using the shell sort algorithm.
Table of Contents
Understanding Shell Sort
The shell sort algorithm starts by sorting pairs of elements far apart, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, It can move some out-place elements into the position faster than a simple nearest-neighbor exchange. The efficiency of shell sort heavily depends on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.
Shell Sort C Program
#include <stdio.h>
void shellsort(int arr[], int n)
{
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i += 1) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
void main()
{
int array[] = {6, 7, 8, 1289, 4, 2, 67, 23, 56};
int n = sizeof(array) / sizeof(array[0]);
printf("Array before sorting\n");
for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
shellsort(array, n);
printf("\nArray after sorting\n");
for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
}Output
The above C program first defines the shell sort function that takes an array and array length n as an argument with each iteration, it sorts the elements that are gap distance apart. Finally, it prints the sorted array.
Analysis of Shell Sort Algorithm
The performance of the shell sort algorithm depends on the choice of the gap sequence. The original sequence proposed by the shell sort algorithm, which halves the gap size each time (i.e., n/2, n4, n/8…), is relatively simple and shows good performance on small arrays. However, more sophisticated sequences such as the Hibbard, Sedgewicek, and others can improve performance on larger arrays.
One of the main advantages of the shell sort algorithm over other comparison-based algorithms is its ability to quickly move items a long distance toward their expected position. This capability makes shell sort particularly effective for arrays that are partially sorted or have a small number of unique elements.
However, shell sort is less effective on large data sets compared to more advanced algorithms like quicksort, heapsort, or mergesort. Its average and worst-case time complexity can vary widely depending on the gap sequence used, but it is generally considered to be between O(n) and O(n^2) for the average case.
Shell sort offers a good trade-off between simplicity and efficiency, especially for small to medium-sized arrays. Its ability to handle large gaps between elements makes it faster than simple insertion sort for unordered lists. While shell sort is not the fastest sorting algorithm for large data sets, shell sort’s ease of implementation and decent performance characteristics make it a valuable tool in the world of programming.
Happy Coding & Learning
2 thoughts on “Shell Sort in C”