In this tutorial, you will learn how shell sort works. Likewise, you will discover working instances of shell sort in C, C++, Java, and Python.
In this article, you will learn-
What is a shell sort?
The shell sort algorithm extends the insertion sort algorithm and is proficient in sorting generally unsorted arrays. The array is divided into sub-arrays and afterward insertion sort is applied.
Note: This algorithm will sort in ascending order.
Shell sort is an algorithm that first sorts the elements far apart from each other and progressively lessens the interval between the elements to be sorted. It is a generalized adaptation of insertion sort.
In shell sort, elements at a particular interval are sorted. The interval between the elements is progressively diminished dependent on the sequence used. The performance of the shell sort relies upon the type of sequence used for a given input array.
A portion of the optimal sequences used are:
- Shell’s original sequence: N/2 , N/4 , …, 1
- Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
- Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577…4j+1+ 3·2j+ 1
- Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
- Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,…
- Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81….
How Shell Sort Works?
- Assume, we need to sort the accompanying array.
2. We are using the shell’s original sequence (N/2, N/4, …1) as intervals in our algorithm.
In the first loop, on the off chance that the array size is N = 8, the elements lying at the interval of/2 = 4 are looked at and swapped in the event that they are not in order.
a. The 0th element is compared and the fourth element.
b. In the event that the 0th element is greater than the fourth one, the fourth element is first put away in the temp variable and the 0th element (ie. greater element) is put away in the fourth position and the element put away in temp is put away in the 0th position.
This process goes on for all the remaining elements.
3. In the second loop, an interval of n/4 = 8/4 = 2 is taken and again the elements lying at these intervals are sorted.
You may get confused now.
The elements at the fourth and second positions are thought about. The elements at second and 0th position are additionally looked at. Every one of the elements in the array lying at the current interval are thought about.
4. A similar process continues for residual elements.
5. At last, when the interval is N/8 = 8/8 =1 then the array elements lying at the interval of 1 are sorted. The array is currently totally sorted.
Shell Sort Algorithm
shellSort(array, size)
for interval i <- size/2n down to 1
for each interval "i" in array
sort all the elements at interval "i"
end shellSort
Python, Java and C/C++ Examples
Python
# Shell sort in python
def shellSort(array, n):
# Rearrange elements at each n/2, n/4, n/8, ... intervals
interval = n // 2
while interval > 0:
for i in range(interval, n):
temp = array[i]
j = i
while j >= interval and array[j - interval] > temp:
array[j] = array[j - interval]
j -= interval
array[j] = temp
interval //= 2
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Java
// Shell sort in Java programming
import java.util.Arrays;
// Shell sort
class ShellSort {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
void shellSort(int array[], int n) {
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Driver code
public static void main(String args[]) {
int[] data = { 9, 8, 3, 7, 5, 6, 4, 1 };
int size = data.length;
ShellSort ss = new ShellSort();
ss.shellSort(data, size);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
C
// Shell Sort in C programming
#include <stdio.h>
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
printf("Sorted array: \n");
printArray(data, size);
}
C++
// Shell Sort in C++ programming
#include <iostream>
using namespace std;
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
cout << "Sorted array: \n";
printArray(data, size);
}
Complexity
Shell sort is an unstable sorting algorithm since this algorithm doesn’t inspect the elements lying in between the intervals.
Time Complexity
- Worst case scenario Complexity: not exactly or equivalent to O(n2)
Worst case scenario complexity for shell sort is in every case not exactly or equivalent to O(n2).
As indicated by Poonen Theorem, the worst-case complexity for shell sort is Θ(Nlog N)2/(log N)2) or Θ(Nlog N)2/log N) or Θ(N(log N)2) or something in the middle.
- Best Case Complexity: O(n*log n)
At the point when the array is sorted, the all out number of examinations for every interval (or increment is equivalent to the size of the array.
- Average Case Complexity: O(n*log n)
It is around O(n1.25).
The complexity relies upon the interval picked. The above complexities vary for various increment arrangements picked. The best increment arrangement is unknown.
Space Complexity:
The space complexity for shell sort is O(1).
Shell Sort Applications
Shellsort is used when:
- calling a stack is overhead. uClibc library uses this sort.
- recursion exceeds a limit. bzip2 compressor uses it.
- Insertion sort doesn’t perform well when the close elements are far apart. Shell sort helps in lessening the distance between the close elements. Accordingly, there will be less number of swappings to be performed.
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.
