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[0]);

	//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;

	//we start with a bigger gap
	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;
	}
}

Recently Added