Related Tags

shell sort
sort
c++
java

# What is a shell sort? Educative Answers Team

The shell sort algorithm extends the insertion sort algorithm and is very efficient in sorting widely unsorted arrays. The array is divided into sub-arrays and then insertion sort is applied. The algorithm is:

1. Calculate the value of the ​gap (formula given in the illustration below).
2. Divide the array into these sub-arrays.
3. Apply the insertion sort.
4. Repeat this process until the complete list is sorted.

Note: This algorithm will sort in ascending order.

The algorithm is illustrated below:

1 of 12

## Code

#include <iostream>
using namespace std;

//Shell sort.
void ShellSort(int arr[], int n)
{
int i, j, k, temp;
// Gap (i) is calculated in this loop.
for( i = n/2; i > 0; i = i/2)
{
for(j = i; j < n; j++)
{
for(k = j-i; k >= 0; k = k-i)
{
// Higher index value is greater than lower index,
// then no swapping required.
if(arr[k+i] >= arr[k])
break;
else
{
// swap the elements.
temp = arr[k];
arr[k] = arr[k+i];
arr[k+i] = temp;
}
}
}
}
}

// Driver Program
int main()
{
// sample array.
int arr[] = {13, 10, 11, 2, 5, 8, 15};
int n= 7;

// Printing the unsorted array.
cout<<"\nUnsorted array: ";
for (int i = 0; i < n; i++)
cout<<arr[i]<< ",";

ShellSort(arr, n);

// Printing the sorted array.
cout<<"\nAfter Shell sort, the array is: ";
for (int i = 0; i < n; i++)
cout<<arr[i]<< ",";

return 0;
}

RELATED TAGS

shell sort
sort
c++
java 