What is Shell Sort in Data Structure with Example?

 

What is Shell Sort in Data Structure?

Shell sort is one of the oldest sorting(ascending order) algorithms named after its inventor Donald L. Shell (1959). Shell Sort is a sorting algorithm that is an improved version of Insertion Sort. It works by comparing and exchanging elements that are far apart, progressively reducing the gap between elements compared, and ultimately performing a final pass with a gap of 1 (like Insertion Sort).

Key Features:

1. Efficient for Moderate-Sized Arrays:
   • Shell Sort is more efficient than simpler algorithms like Bubble Sort or Insertion Sort for larger datasets.
2. In-Place Sorting:
   • It requires no extra memory, making it a space-efficient algorithm.
3. Flexible with Gap Sequence:
   • The choice of the gap sequence can greatly influence the algorithm’s performance.
4. Not a Stable Sort:
   • Equal elements may not maintain their original relative order.

What is another name for Shell Sort?

Shell sort is also known as the “diminishing increment sort” or “gap sort” because it works by comparing elements separated by a gap that gradually diminishes as the algorithm progresses.

Who made Shell Sort?

Shell Sort was invented by Donald L. Shell in 1959. It was one of the first algorithms designed to improve upon simple sorting methods like insertion sort by allowing the exchange of elements that are far apart, which helps to reduce large inversions early in the sorting process. This approach makes Shell Sort more efficient than simple insertion sort for larger datasets.

METHOD……

• This method makes repeated use of insertion sort.
• To sort n elements of an array by this method requires a number S_icalled increment or step should be chosen before every pass.
• S_i Should be less than n.
• For the last pass S_ishould be 1.
• Initial value of step or increments can be n/2 and in further passes S_ishould be previous pass i.e.

S₁ =n/2

S₂ = S₁/2

S₃ = S₂/2

.

.

 

S_i+1 = S_i/2

1^st Pass

• If an array a[0], a[1],……….a[7] has 8 elements then step or increment S1=8/2=4. The array will be divided into four sublists in the first pass i.e.
• 1^stsublist: (a[0], a[0+4])
• 2^nd sublist: (a[1], a[1+4])
• 3^rd sublist: (a[2], a[2+4])
• 4^th sublist: (a[3], a[3+4])
• These 4 sublists are sorted using insertion sort independently.

2^nd Pass

• In the second pass increment or step S2=S1/2=4/2=2.
• The array will be divided into 2 sublists i.e.
• 1^stsublist: (a[0], a[0+2],a[0+4],a[0+6])
• 2^nd sublist: (a[1], a[1+2],a[1+4],a[1+6])
• These 2 sublists(1^stsublist: (a[0], a[0+2],a[0+4],a[0+6]) 2^nd   sublist: (a[1], a[1+2],a[1+4],a[1+6])

) are sorted using insertion sort independently.

3^rd Pass

• In the third pass the value of step S3=S2/2=2/2=1.
• Array will be divided into 1 sublist i.e.

1^st sublist: (a[0], a[1],a[2]…….a[7])

This sublist is sorted using insertion sort and we get all the elements in sorted form.

SHELL SORT ALGORITHM IN DATA STRUCTURE………

Algorithm Steps:

1. Initialize the Gap Sequence:
   • Start with a gap value, typically n/2n/2n/2 (where n is the size of the array), and reduce it by dividing by 2 in each iteration until the gap is 1.
2. Sort with Current Gap:
   • For each gap, perform a modified insertion sort:
     • Compare and swap (interchange)elements that are separated by the current gap.
     • Continue this until all elements are appropriately sorted for this gap.
3. Reduce the Gap:
   • Update the gap and repeat the process.
4. Final Pass:
   • Perform a final pass with a gap of 1 (standard insertion sort).

 

In this algorithm also array a is passed having the size n.

Shell(A,N)

{

For(s=n/2;s>0;s=s/2)

{

For(i=s;i<n;i++)

{

T=a[i];

For(j=i;j>=s;j=j-s)

{

If(t<a[j-s])

A[j]=a[j-s]

else

break

}

A[j]=t

}}}

EXPLANATION…….

Let’s take an example to sort the following elements using shell sort.

Array a[]=123 971 80 7 92 20 10 55

Original Array   123 971 80 7 92 20 10 55

1^st pass

S1=8/2=4

• Array before

123 971 80 7                       92 20 10 55

123 92

971 20

1. 10
2. 55

There are 4 sublists, each sublist has 2 elements, These are to be sorted using the insertion sort method.

• Array after

92 20       10 7        123 971           80 55

2^nd pass

S2=S1/2=2

Array before

92 20 10 7 123 971 80 55

So there are 2 sublists, and each sublist has 2 elements. They are to be sorted using the insertion sort method.

Array after

10 7              92 20           80 55           123 971

3^rd Pass

S3=S2/2=1

Array before

10 7 92 20 80 55   123 971

There is only one sublist of 8 elements. These are to be sorted using insertion sort method and we get all the elements in sorted order.

Array after

7 10 20 55 80 92 123 971

Shell Sort Time Complexity:

• Best Case: O(nlog⁡n)O(n \log n)O(nlogn) (for optimal gap sequences).
• Average Case: Depends on the gap sequence, typically O(n1.25)O(n^{1.25})O(n1.25) to O(n1.5)O(n^{1.5})O(n1.5).
• Worst Case: O(n2)O(n^2)O(n2) (for inefficient gap sequences, such as Shell’s original sequence).

Advantages:

1. Faster than insertion sort for larger arrays.
2. Simple to implement and requires no additional memory.

Disadvantages:

1. Not suitable for very large datasets compared to advanced algorithms like Quick Sort or Merge Sort.
2. Performance depends heavily on the chosen gap sequence.

 

Program to sort  elements using shell sort method

#include <stdio.h>

int gap,i;

// Function to perform Shell Sort

void shellSort(int array[], int n) {

// Start with a large gap, then reduce the gap

for ( gap = n / 2; gap > 0; gap /= 2) {

// Perform a gapped insertion sort for this gap size

for ( i = gap; i < n; i++) {

// Store the current element

int temp = array[i];

int j;

 

// Shift earlier gap-sorted elements until the correct location is found

for (j = i; j >= gap && array[j – gap] > temp; j -= gap) {

array[j] = array[j – gap];

}

// Put temp (the original array[i]) in its correct location

array[j] = temp;

}

}

}

// Function to print the array

void printArray(int array[], int n) {

for ( i = 0; i < n; i++) {

printf(“%d “, array[i]);

}

printf(“\n”);

}

// Main function

int main() {

int array[] = {12, 34, 54, 2, 3};

int n = sizeof(array) / sizeof(array[0]);

 

printf(“Original array:\n”);

printArray(array, n);

shellSort(array, n);

printf(“Sorted array:\n”);

printArray(array, n);

return 0;

}

 Explanation of the Program:

1. Input Data:
   • An array of integers is given as input to the function shellSort.
2. Gap Sequence:
   • The gap starts as half of the array size (n/2) and is reduced by half in each iteration until it becomes 1.
3. Gapped Insertion Sort:
   • For each gap, elements separated by that gap are compared and rearranged.
4. Final Output:
   • Once the gap becomes 1, the array is completely sorted.

Example Execution:

For the array {12, 34, 54, 2, 3}:

1. Gap = 2: {12, 34, 54, 2, 3} -> {12, 2, 54, 34, 3}
2. Gap = 1: {12, 2, 54, 34, 3} -> {2, 3, 12, 34, 54}

 

What is Recursion in Data Structure?