Trusted answers to developer questions
Trusted Answers to Developer Questions

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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring