Shell Sort
Shell Sort is a sorting algorithm that was invented by Donald Shell in 1959. It is a variation of the insertion sort algorithm that improves its performance by sorting elements that are far apart before sorting elements that are nearby. The basic idea behind Shell Sort is to divide the input array into smaller sub-arrays, and then apply insertion sort to each of these sub-arrays.
The algorithm works by defining a sequence of gap values that determine the distance between elements being compared. The sequence of gap values is usually generated using the Knuth sequence or the Sedgewick sequence. The algorithm starts with the largest gap value and performs insertion sort on each sub-array defined by that gap value. It then reduces the gap value and repeats the process until the gap value becomes 1, at which point the algorithm performs a final insertion sort on the entire array.
The performance of Shell Sort depends on the sequence of gap values used. The worst-case time complexity of Shell Sort is O(n^2), but it can be much faster than other O(n^2) sorting algorithms for certain input data. The best-case time complexity of Shell Sort is O(n log n), but this is only achieved for certain sequences of gap values.
Overall, Shell Sort is a simple and effective sorting algorithm that can be faster than other O(n^2) sorting algorithms for certain input data. However, its performance can be highly dependent on the choice of gap sequence.
Here given code implementation process.
//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
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.
New Comment