# Shell Sort

Sorting Algorithm

Share

In this tutorial we will be learning about Shell sort algorithm.

It is a generalisation of the insertion sort. In this sorting algorithm we compare elements that are distant apart rather than adjacent.

We start by comparing elements that are at a certain distance apart. So, if there are N elements then we start with a value gap < N.

In each pass we keep reducing the value of gap till we reach the last pass when gap is 1.

In the last pass shell sort is like insertion sort.

## C Code

``````#include <stdio.h>

//function declaration
void display(int arr[], int size);
void shellSort(int arr[], int size);

int main(void) {
//unsorted elements
int arr[] = {14,18,19,37,23,40,29,30,11};

//size of the array
int n = sizeof(arr)/sizeof(arr);

//output unsorted elements
display(arr, n);

//sort the elements
shellSort(arr, n);

//display sorted elements
display(arr, n);

return 0;
}

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

void shellSort(int arr[], int size) {
int i, j, gap, temp;

gap = size/2;

while(gap > 0) {
//now we will do the insertion sort of the gapped elements
i = gap;

while(i < size) {
temp = arr[i];

//shifting gap sorted element to correct location
for(j = i; (j >= gap) && (arr[j - gap] > temp); j -=gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;

//increase i
i++;
}

//reduce the gap by half
gap = gap / 2;
}
}
``````
Share