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

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

04 Mar 2024
Intermediate
5.44K Views
17 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

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:

    Initial Array

  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.
    3. Rearrange the elements at n/2 interval

    This process goes on for all the remaining elements.

    Rearrange all the elements at n/2 interval

  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.

    Rearrange the elements at n/4 interval

    You might get confused at this point.

    All the elements in the array lying at the current interval are compared.

    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.

    Rearrange all the elements at n/4 interval

  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.
  6. Rearrange the elements at n/8 interval

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
    CaseTime Complexity
    Best O(nlog n)
    Average O(nlog n)
    WorstO(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

FAQs

Q1. Is shell sort stable?

Although insertion sort is stable, shell sort is not. Moving the elements using intervals makes the shell sort unstable.

Q2. What are the factors on which the time complexity of shell sort depends?

Shell sort is an adaptive algorithm. Its time complexity depends on how sorted the given data is. Shell sort’s performance also depends on the interval sequence we choose.

Q3. Can you explain the steps involved in the Shell Sort algorithm?

  • Choose a gap sequence
  • Perform insertion sort for all elements at the current interval (gap).
  • Repeat step 2, reducing the gap size each time until it becomes 1. At this point, the array should be sorted.

Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
Full Stack .Net Certification Training May 26 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
ASP.NET Core Certification Training May 26 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training May 26 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Azure DevOps Certification Training Course Jun 01 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Data Structures and Algorithms Training Jun 04 TUE, FRI
Filling Fast
08:30PM to 10:00PM (IST)
Get Details
ASP.NET Core Certification Training Jun 14 MON, WED, FRI
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
ASP.NET Core (Project) Jun 22 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this