Posted on by Kalkicode
Code Sorting

# Shell Sort

Shell Sort, also known as Shell's method, is an efficient sorting algorithm that is an extension of Insertion Sort. It is designed to improve the efficiency of Insertion Sort by comparing elements that are far apart first, and then gradually reducing the gap between compared elements. This sorting algorithm was introduced by Donald Shell in 1959.

## Problem Statement

Given an array of integers, the goal is to sort the array in ascending order using the Shell Sort algorithm.

## Example

Let's take the array `[5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12]` as an example.

## Idea to Solve

The main idea behind Shell Sort is to divide the array into smaller subarrays and sort them using Insertion Sort with varying gap sizes. The gap sizes are initially set to some predefined values, and they gradually decrease as the algorithm progresses. This process helps in moving smaller elements towards the beginning of the array faster than Insertion Sort would on its own.

## Pseudocode

``````function shellSort(arr):
size = length(arr)
for gap = size/2 to 1:
for i = gap to size - 1:
auxiliary = arr[i]
j = i
while j >= gap and arr[j - gap] > auxiliary:
arr[j] = arr[j - gap]
j = j - gap
arr[j] = auxiliary``````

## Algorithm Explanation

1. The outer loop iterates over different gap sizes, starting from `size/2` and reducing the gap size in each iteration.
2. The inner loop uses Insertion Sort logic but works with the gap. It iterates over the array, starting from the `gap` index.
3. For each element at index `i`, store its value in the `auxiliary` variable.
4. Initialize `j` as `i`.
5. While `j` is greater than or equal to `gap` and the element at index `j - gap` is greater than `auxiliary`, shift the element at index `j - gap` by `gap` positions to the right.
6. Decrement `j` by `gap`.
7. Place `auxiliary` in the correct position, which is `j`.
8. Repeat steps 3-7 for each element in the subarray.
9. Continue with the next gap size in the outer loop until the gap size becomes 1.

## Code Solution

``````//C Program
//Shell sort
#include <stdio.h>
#include <stdlib.h>

void shell_sort(int arr[],int size)
{
int auxiliary=0,j=0,i=0,space=0;

for (space = size/2; space > 0; space=space/2)
{

for (i = space; i < size; ++i)
{

auxiliary = arr[i];

for (j = i; j >= space && arr[j-space] > auxiliary; j=j-space)
{
arr[j] = arr[j-space];
}

arr[j] = auxiliary;

}
}
}
//Display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d",arr[i] );
}
printf("\n");
}
int main()
{

//Define array elements
int arr[]= {5,7,8,2,6,9,-7,2,1,4,12,68,0,12};
//get the size of array elements
int size=sizeof(arr)/sizeof(arr[0]);
printf("Before Sort : \n");
display(arr,size);
shell_sort(arr,size);
printf("After Sort : \n");
display(arr,size);

return 0;
}```
```

#### Output

``````Before Sort :
5  7  8  2  6  9  -7  2  1  4  12  68  0  12
After Sort :
-7  0  1  2  2  4  5  6  7  8  9  12  12  68``````
``````/*
C++ Program
Shell Sort
*/
#include<iostream>
using namespace std;
class MySort {
public:
void shell_sort(int arr[], int size) {
int auxiliary = 0, j = 0, i = 0, space = 0;
for (space = size / 2; space > 0; space = space / 2) {
for (i = space; i < size; ++i) {
auxiliary = arr[i];
for (j = i; j >= space && arr[j - space] > auxiliary; j = j - space) {
arr[j] = arr[j - space];
}
arr[j] = auxiliary;
}
}
}
//Display array elements
void display(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MySort obj ;
int arr[] = {
5,
7,
8,
2,
6,
9,
-7,
2,
1,
4,
12,
68,
0,
12
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Before Sort : \n";
obj.display(arr, size);
obj.shell_sort(arr, size);
cout << "After Sort : \n";
obj.display(arr, size);
return 0;
}```
```

#### Output

``````Before Sort :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68``````
``````/*
Java Program
Shell Sort
*/
public class MySort {

public void shell_sort(int []arr,int size)
{
int auxiliary=0,j=0,i=0,space=0;

for (space = size/2; space > 0; space=space/2)
{

for (i = space; i < size; ++i)
{

auxiliary = arr[i];

for (j = i; j >= space && arr[j-space] > auxiliary; j=j-space)
{
arr[j] = arr[j-space];
}

arr[j] = auxiliary;

}
}
}
//Display array elements
public void display(int []arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  "+arr[i] );
}
System.out.print("\n");
}

public static void main(String[] args)
{

MySort obj = new MySort();
//Define array elements
int []arr= {5,7,8,2,6,9,-7,2,1,4,12,68,0,12};
//Get the size of array
int size = arr.length;
System.out.print("Before Sort : \n");
obj.display(arr,size);

obj.shell_sort(arr,size);
System.out.print("After Sort : \n");
obj.display(arr,size);

}
}```
```

#### Output

``````Before Sort :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68``````
``````/*
C# Program
Shell Sort
*/
using System;
public class MySort {

public void shell_sort(int[] arr, int size) {
int auxiliary = 0, j = 0, i = 0, space = 0;
for (space = size / 2; space > 0; space = space / 2) {
for (i = space; i < size; ++i) {
auxiliary = arr[i];
for (j = i; j >= space && arr[j - space] > auxiliary; j = j - space) {
arr[j] = arr[j - space];
}
arr[j] = auxiliary;
}
}
}
//Display array elements
public void display(int[] arr, int size) {
for (int i = 0; i < size; ++i) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MySort obj = new MySort();
int[]
//Define array elements
arr = {
5,
7,
8,
2,
6,
9,
-7,
2,
1,
4,
12,
68,
0,
12
};
//Get the size of array
int size = arr.Length;
Console.Write("Before Sort : \n");
obj.display(arr, size);
obj.shell_sort(arr, size);
Console.Write("After Sort : \n");
obj.display(arr, size);
}
}```
```

#### Output

``````Before Sort :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68``````
``````<?php
/*
Php Program
Shell Sort
*/
class MySort {
//Swap the array element
public  function shell_sort(&\$arr, \$size) {
\$auxiliary = 0;
\$j = 0;
\$i = 0;
\$space = 0;
for (\$space = intval(\$size / 2); \$space > 0; \$space = intval(\$space / 2)) {
for (\$i = \$space; \$i < \$size; ++\$i) {
\$auxiliary = \$arr[\$i];
for (\$j = \$i; \$j >= \$space && \$arr[\$j - \$space] > \$auxiliary; \$j = \$j - \$space) {
\$arr[\$j] = \$arr[\$j - \$space];
}
\$arr[\$j] = \$auxiliary;
}
}
}
//Display array elements

public  function display(\$arr, \$size) {
for (\$i = 0; \$i < \$size; ++\$i) {
echo(" ". \$arr[\$i]);
}
echo("\n");
}
}

function main() {
\$obj = new MySort();
//Define array elements
\$arr = array(5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12);
//Get the size of array
\$size = count(\$arr);
echo("Before Sort : \n");
\$obj->display(\$arr, \$size);
\$obj->shell_sort(\$arr, \$size);
echo("After Sort : \n");
\$obj->display(\$arr, \$size);

}
main();```
```

#### Output

``````Before Sort :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68``````
``````/*
Node Js Program
Shell Sort
*/
class MySort {
shell_sort(arr, size) {
var auxiliary = 0;
var j = 0;
var i = 0;
var space = 0;
for (space = parseInt(size / 2); space > 0; space = parseInt(space / 2)) {
for (i = space; i < size; ++i) {
auxiliary = arr[i];
for (j = i; j >= space && arr[j - space] > auxiliary; j = j - space) {
arr[j] = arr[j - space];
}
arr[j] = auxiliary;
}
}
}

//Display array elements
display(arr, size) {
for (var i = 0; i < size; ++i) {
process.stdout.write(" " + arr[i]);
}

process.stdout.write("\n");
}
}

function main(args) {
var obj = new MySort();
//Define array elements
var arr = [5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12];
//Get the size of array
var size = arr.length;
process.stdout.write("Before Sort : \n");
obj.display(arr, size);
obj.shell_sort(arr, size);
process.stdout.write("After Sort : \n");
obj.display(arr, size);
}

main();```
```

#### Output

``````Before Sort :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68``````
``````# Python 3 Program
# Shell Sort
class MySort :

def shell_sort(self, arr, size) :
auxiliary = 0
j = 0
i = 0
space = 0
space = int(size / 2)
while (space > 0) :
i = space
while (i < size) :
auxiliary = arr[i]
j = i
while (j >= space and arr[j - space] > auxiliary) :
arr[j] = arr[j - space]
j = j - space

arr[j] = auxiliary
i += 1

space = int(space / 2)

# Display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

def main() :
obj = MySort()
# Define array elements
arr = [5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12]
# Get the size of array
size = len(arr)
print("Before Sort : \n", end = "")
obj.display(arr, size)
obj.shell_sort(arr, size)
print("After Sort : \n", end = "")
obj.display(arr, size)

if __name__ == "__main__":
main()```
```

#### Output

``````Before Sort :
5  7  8  2  6  9  -7  2  1  4  12  68  0  12
After Sort :
-7  0  1  2  2  4  5  6  7  8  9  12  12  68``````
``````# Ruby Program
# Shell Sort
class MySort
def shell_sort(arr, size)
auxiliary = 0
j = 0
i = 0
space = 0
space = size / 2
while (space > 0)
i = space
while (i < size)
auxiliary = arr[i]
j = i
while (j >= space && arr[j - space] > auxiliary)
arr[j] = arr[j - space]
j = j - space
end
arr[j] = auxiliary
i += 1
end
space = space / 2
end
end
# Display array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MySort.new()
# Define array elements
arr = [5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12]
# Get the size of array
size = arr.length
print("Before Sort  :\n")
obj.display(arr, size)
obj.shell_sort(arr, size)
print("After Sort  :\n")
obj.display(arr, size)
end
main()```
```

#### Output

``````Before Sort  :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort  :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68
``````
``````/*
Scala Program
Shell Sort
*/
class MySort {

def shell_sort(arr: Array[Int], size: Int): Unit = {
var auxiliary: Int = 0;
var j: Int = 0;
var i: Int = 0;
var space: Int = 0;
space = (size / 2).toInt;
while (space > 0) {
i = space;
while (i < size) {
auxiliary = arr(i);
j = i;
while (j >= space && arr(j - space) > auxiliary) {
arr(j) = arr(j - space);
j = j - space;
}
arr(j) = auxiliary;
i += 1;
}
space = (space / 2).toInt;
}
}
//Display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MySort = new MySort();

//Define array elements
var arr: Array[Int] = Array(5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12);

//Get the size of array
val size: Int = arr.length;
print("Before Sort : \n");
obj.display(arr, size);
obj.shell_sort(arr, size);
print("After Sort : \n");
obj.display(arr, size);
}
}```
```

#### Output

``````Before Sort :
5 7 8 2 6 9 -7 2 1 4 12 68 0 12
After Sort :
-7 0 1 2 2 4 5 6 7 8 9 12 12 68``````
``````/*
Swift Program
Shell Sort
*/
class MySort {

func shell_sort(_ arr: inout [Int], _ size: Int) {
var auxiliary: Int = 0;
var j: Int = 0;
var i: Int = 0;
var space: Int = 0;
space = size / 2;
while (space > 0) {
i = space;
while (i < size) {
auxiliary = arr[i];
j = i;
while (j >= space && arr[j - space] > auxiliary) {
arr[j] = arr[j - space];
j = j - space;
}
arr[j] = auxiliary;
i += 1;
}
space = space / 2;
}
}
//Display array elements
func display(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj: MySort = MySort();
//Define array elements
var arr: [Int] = [5, 7, 8, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0, 12];
//Get the size of array
let size: Int = arr.count;
print("Before Sort : \n", terminator: "");
obj.display(arr, size);
obj.shell_sort(&arr, size);
print("After Sort : \n", terminator: "");
obj.display(arr, size);
}
main();```
```

#### Output

``````Before Sort :
5  7  8  2  6  9  -7  2  1  4  12  68  0  12
After Sort :
-7  0  1  2  2  4  5  6  7  8  9  12  12  68``````

## Time Complexity

The time complexity of the Shell Sort algorithm depends on the chosen gap sequence. The worst-case time complexity is O(n^2), but it can be significantly faster than other quadratic sorting algorithms like Bubble Sort and Insertion Sort because it moves elements more efficiently. With certain gap sequences, Shell Sort can achieve an average-case time complexity of O(n log n). However, predicting the exact time complexity is challenging due to the variation in gap sizes and their effects on the algorithm's behavior.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post