Shell sort (also known as Shell sort or Shell's approach) is an in-place comparison-based sorting algorithm. In 1959, Donald Shell published the first version of the shell sort algorithm. Shell sort's execution time is strongly influenced by the gap sequence it employs. Shell sort is a sorting algorithm that is highly efficient and is based on the insertion sort algorithm. This algorithm avoids large shifts, as in insertion sort, where the smaller value is on the far right and must be moved to the far left. Shell Sort reduces its time complexity by utilising the fact that using Insertion Sort on a partially sorted array results in fewer moves.
What Is a Shell Sort Algorithm?
- Shell sort is an in-place comparison sort that is also known as Shell sort or Shell's method.
- It can be shown as a generalization of either exchange bubble sorting or insertion sorting.
- The method begins by sorting pairs of elements far apart from each other, then gradually narrows the gap between elements to be compared.
- Some out-of-place elements can be moved into position faster than what a simple nearest-neighbor exchange would, by starting with far apart elements.
This algorithm uses insertion sort on widely spread elements to sort them and then sort the less widely spaced elements. This spacing is termed as the interval.
This interval is calculated using Knuth's formula, which is as follows:
Knuth's Formula:
|
i = i * 3 + 1 Where i is the interval with a starting value of 1 |
You will now look at the operating procedure of the shell sort algorithm after understanding what it is.
How Does a Shell Sort Algorithm Work?
- Consider the following example to have a better understanding of how shell sort works. You must use the same array as in the previous examples. For the purpose of clarity, you must use the interval of 4 as an example.
Make a virtual sub-list of all values in the four-position interval. These are the values: (32, 17); (35, 21); (45, 27); and (13, 47).
- You compare the values in each sub-list and swap them in the original array if necessary. After this step, the new array should look like this:
- Then we pick one interval and divide it into two sub-lists: (17, 27, 32, 45) and (21, 13, 35, 47).
- You compare the values in the original array and, if necessary, swap them. This is how the array should look after this step:
- Finally, you need to use interval 1 to sort the rest of the array. The array is sorted by shell sort using insertion sort.
The following is a step-by-step guide:
You will now look at the shell sort algorithm's algorithm and pseudocode after seeing how it works.
Algorithm and Pseudocode of Shell Sort Algorithm
Algorithm for the Shell Sort Algorithm
|
Step 1: Set the value of i. Step 2: Separate the list into sub-lists with the same i interval. Step 3: Using insertion sort, sort these sub-lists. Step 4: Continue until the entire list has been sorted. |
Pseudocode for the Shell Sort Algorithm
|
procedure begin shell sort() Array: array of items while inter < Array.length /3 do: // calculating the interval (inter) inter = inter * 3 + 1 end while while inter > 0 do: for out = inter; out < Array.length; out++ do: value = Array[out] // select the inserted value in= out; while in > inter -1 && Array[in - inter] >= value do: //shifting value to right Array[in] = Array[in - inter] in = in - inter end while Array[in] = value // insert the number at position end for inter = (inter -1) /3; // calculating interval end while end procedure |
You will look at the complexity of the shell sort algorithm in the next segment of this tutorial.
The Complexity of the Shell Sort Algorithm
The Time Complexity of the Shell Sort Algorithm
-
Complexity in the Worst-Case Scenario: Less Than or Equal to O (n2)
Shell sort's worst-case complexity is always less than or equal to O. (n2).
The worst-case complexity for shell sort, according to the Poonen Theorem, is (N log N)2/(log log N)2, or (N log N)2/log log N), or (N(log N)2), or something in between.
-
Complexity in the Best Case: O(n*Log n)
The total number of comparisons for each interval (or increment) is equal to the size of the array when it is already sorted.
-
Complexity in the Average Case: O(n*log n)
It's somewhere around O. (n1.25).
The degree of complexity is determined by the interval picked. The above complexity varies depending on the increment sequences used. The best increment sequence has yet to be discovered.
The Space Complexity of the Shell Sort Algorithm
- The space complexity of the shell sort algorithm is O(1).
After learning about the complexity of the shell sort algorithm, you will look at some of its applications.
Applications of Shell Sort Algorithm
Shell Sort can be used for a variety of purposes, including:
- Shell sort has a more significant cache miss percentage than quicksort and executes more operations.
- However, some versions of the qsort function in the C standard library geared at embedded devices utilize it instead of quicksort because it requires less code and does not use the call stack. The uClibc library, for example, uses Shell sort. The Linux kernel has a Shell Sort implementation for similar reasons.
- Shell sort can also be used as a sub-algorithm of the introspective sort to sort short subarrays and avoid slowdowns when the recursion depth exceeds a certain threshold. This method is used in the bzip2 compression algorithm, for example.
In this tutorial, you will look at how to code the shell sort algorithm in C.
Code Implementation of Shell Sort Algorithm
The shell sort algorithm is implemented in the code below.
|
#include <stdio.h> #include <stdlib.h> #include <conio.h> void shellsortalgorithm(int array[], int number) { int i, j, k, temp; for (i = number / 2; i > 0; i = i / 2) { for (j = i; j < number; j++) { for(k = j - i; k >= 0; k = k - i) { if (array[k+i] >= array[k]) break; else { temp = array[k]; array[k] = array[k+i]; array[k+i] = temp; } } } } } int main() { int array[30]; int k, values; printf("Enter total no. of elements : "); scanf("%d", &values); printf("\nEnter the %d values: ", values); for (k = 0 ; k < values; k++) { scanf("%d", &array[k]); } shellsortalgorithm(array, values); printf("\n Array after the sorting: "); for (k = 0; k < values; k++) printf("%d ", array[k]); return 0; } |
Output
Next Steps
You learned everything there is to know about the shell sort algorithm in this tutorial, including how to implement and utilize it.
You will return to another fascinating topic in data structure and algorithms. Enroll in Simplilearn's Full Stack Web Development PGP to gain a better understanding of data structures and programming languages.
Please leave any comments or questions about the "shell Sort Algorithm" instruction in the space provided below. We will gladly help you resolve your queries as soon as possible.
Please stay safe until then and subscribe to the Simplilearn channel.
