Shell Sort in Data Structures - Algorithm, Visualization, & Complexity

Shell Sort: An Overview

We have seen in the insertion sort algorithm, that elements are moved only one position ahead until it reaches the correct position. Hence, it will take a lot of time for large-size datasets. To overcome this drawback, we have the shell sort algorithm with us. In this DSA tutorial, we will understand its technique, working, implementation, etc.

To further enhance your understanding and application of shell sort, consider enrolling in the Dsa Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Shell Sort in Data Structures?

The Shell Sort algorithm is an extension to the insertion sort method, where it sorts subsets of elements that are distant from each other rather than adjacent. Here, an array is made h-sorted for a large value of h. The value of h is kept reducing until it becomes 1. If all sublists of every h’th element are sorted then the array is said to be h-sorted.

The algorithm first sorts the elements that are far away and then subsequently reduces the gap between the elements. This gap is also known as intervals. The interval between the elements is reduced based on the sequence used. The performance of the shell sort depends on the type of sequence used for a given input array. Some of the optimal sequences that can be used in the shell sort algorithm 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....

Read More - DSA Interview Questions and Answers

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

Working of Shell Sort Algorithm

1. Let's suppose, the input array is:

   

2. We are using the shell's original sequence (N/2, N/4, ...1) as intervals in our algorithm.

   In the first loop, if the array size is N = 8 then, the elements lying at the interval of N/2 = 4 are compared and swapped if they are not in order.

   1. The 0th element is compared with the 4th element.
   2. If the 0th element is greater than the 4th one then, the 4th element is first stored in thetemp variable and the 0th element (ie. greater element) is stored in the 4th position and the element stored in temp is stored 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 might get confused at this point.

   

   The elements at the 4th and 2nd positions are compared. The elements at the 2nd and 0th positions are also compared. All the elements in the array lying at the current interval are compared.

4. The same process goes on for the remaining elements.

   

5. Finally, when the interval is N/8 = 8/8 =1 then the array elements lying at the interval of 1 are sorted. The array is now completely sorted.

Implementation of Shell Sort in Different Languages in Data Structures

def shell_sort(array):
    n = len(array)

    # 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
        
def print_list(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()

arr = [9, 4, 7, 2, 1, 5, 3, 8, 6]

# Print the original array
print('Original Array:', end=" ")
print_list(arr)

shell_sort(arr)

print('Sorted Array in Ascending Order:', end=" ")
print_list(arr) 
    

public class ShellSort {
    public static void shellSort(int[] array) {
        int n = array.length;

        // Rearrange elements at each n/2, n/4, n/8, ... intervals
        int interval = n / 2;
        while (interval > 0) {
            for (int i = interval; i < n; i++) {
                int temp = array[i];
                int j = i;
                while (j >= interval && array[j - interval] > temp) {
                    array[j] = array[j - interval];
                    j -= interval;
                }

                array[j] = temp;
            }
            interval /= 2;
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {9, 4, 7, 2, 1, 5, 3, 8, 6};

        // Print the original array
        System.out.print("Original Array: ");
        printArray(arr);

        shellSort(arr);

        // Print the sorted array
        System.out.print("Sorted Array in Ascending Order: ");
        printArray(arr);
    }
}
    

#include <iostream>
using namespace std;

void shellSort(int arr[], int n) {
    // Rearrange elements at each n/2, n/4, n/8, ... intervals
    int interval = n / 2;
    while (interval > 0) {
        for (int i = interval; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= interval && arr[j - interval] > temp) {
                arr[j] = arr[j - interval];
                j -= interval;
            }

            arr[j] = temp;
        }
        interval /= 2;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {9, 4, 7, 2, 1, 5, 3, 8, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Print the original array
    cout << "Original Array: ";
    printArray(arr, n);

    shellSort(arr, n);

    // Print the sorted array
    cout << "Sorted Array in Ascending Order: ";
    printArray(arr, n);

    return 0;
}
    

Output

 Original Array: 9 4 7 2 1 5 3 8 6 
Sorted Array in Ascending Order: 1 2 3 4 5 6 7 8 9 

Complexity Analysis of Shell Sort Algorithm

1. Time Complexity

   Case	Time Complexity
   Best	O(nlog n)
   Average	O(nlog n)
   Worst	O(n^2)

2. Space Complexity: The space complexity of the shell sort is O(1) since an extra space is used for sub-lists.

Applications of Shell Sort Algorithm

1. Numeric data: Shell sort works well for sorting arrays or lists of numeric data, such as integers or floating-point numbers. It can handle both small and large data sets efficiently.
2. Strings: Shell sort can also be applied to sort strings based on alphabetical order or other defined criteria. It can arrange a list of names or words in a desired order.
3. Records or objects: If you have a collection of records or objects that need to be sorted based on one or more attributes, Shell sort can be used. You can define custom comparison functions or operators to determine the sorting order based on specific attributes.
4. Large data sets: Shell sort is often used in situations where the data set is large and other sorting algorithms may be too slow. It provides better performance compared to simple algorithms like bubble sort or insertion sort.
5. Online sorting: Shell sort can also be applied in situations where new elements are continuously added to an already sorted list. It can efficiently handle incremental sorting by adapting the gap sequence dynamically as new elements are inserted

Advantages of Shell Sort Algorithm

1. Efficient for medium-sized lists: Shell sort performs well for lists of medium size.
2. In-place sorting: Shell sort is an in-place sorting algorithm, meaning it doesn't require additional memory space proportional to the input size. It operates directly on the input list, making it memory efficient and suitable for situations with limited memory availability.
3. Adaptive nature: Shell sort is an adaptive algorithm, which means it can take advantage of partially sorted lists. It starts with a large gap between elements and gradually reduces the gap until it becomes 1.
4. Wide range of applications: Shell sort finds its applications in various scenarios. It is commonly used in embedded systems and applications where memory is limited. Additionally, it can be useful in scenarios where a quick and efficient sorting algorithm is required but the input size is not excessively large.

Disadvantages of Shell Sort Algorithm

1. Unstable sort: Shell sort is generally an unstable sorting algorithm, meaning that it may change the relative order of equal elements.
2. Non-optimal gap sequence selection: The performance of shell sort heavily relies on the choice of gap sequence. Different gap sequences can lead to significantly different running times for the same input. Finding the optimal gap sequence for a given input is a challenging task.

Summary

So, here we saw every aspect of the shell sort algorithm in data structures. It must have been a little difficult to understand the implementation of it in programming. But, not to worry. After a time, you won't find it. To apply your knowledge of the shell sort algorithm, enroll in our Best Dsa Course.

Similar Sorting Algorithms

• Insertion Sort
• Selection Sort
• Quick Sort
• Bubble Sort