Home » C++ programming language

Implement shell sort using C++ program

In this article, we are going to learn what is shell short in Data Structure and how to implement it using a C++ program?
Submitted by Shubham Singh Rajawat, on July 24, 2017

What is shell sort?

Shell sort is a generalization of insertion sort in which the exchange of far element is possible unlike insertion sort with the help of an element ‘gap’ and make the list gap-sorted we will keep decreasing gap until gap becomes 1 which means the last step will be a normal insertion sort.

Algorithm

Step 1: Initialize the value of gap.

Step 2: Divide the list into smaller sub-lists of equal interval gap.

Step 3: Sort each sub-list using insertion sort.

Step 4: Repeat until the list is sorted.

Shell sort implementation using C++ program

#include <iostream>
using namespace std;

/*Method to sort the list/array*/
void shellSort(int sort[], int size) {
  for (int gap = size / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < size; i++) {
      int temp = sort[i];
      int j;
      for (j = i; j >= gap && sort[j - gap] > temp; j -= gap) {
        sort[j] = sort[j - gap];
      }
      sort[j] = temp;
    }
  }
}

// main program
int main() {
  int size;

  cout << "Enter the size of the array :";
  cin >> size;

  int sort[size];
  for (int i = 0; i < size; i++) {
    cin >> sort[i];
  }

  shellSort(sort, size);

  cout << "Array after sorting is :";
  for (int i = 0; i < size; i++) {
    cout << sort[i] << " ";
  }

  cout << endl;

  return 0;
}

Output

FIRST INPUT:
Enter the size of the array :6
87 15 34 99 56 44
Array after sorting is :15 34 44 56 87 99

SECOND INPUT :
Enter the size of the array :10
13 54 36 87 36 42 11 68 91 9
Array after sorting is :9 11 13 36 36 42 54 68 87 91