Tutorial 28

 ---- 28 Shell sort

//------- Insertion Sort Code to Understand the base FIRST..

#include <bits/stdc++.h>

using namespace std;

void insertionSort(int arr[], int n)

{

int i, key, j;

for (i = 1; i < n; i++) 

    {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) 

        {

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

}

void printArray(int arr[], int n)

{

int i;

for (i = 0; i < n; i++)

cout << arr[i] << " ";

cout << endl;

}

// Driver code

int main()

{

int arr[] = { 12, 11, 13, 5, 6 };

int N = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, N);

printArray(arr, N);

return 0;

}

////-------Now, lets understand the Shell Sort!

#include <iostream>

using namespace std;

// Shell sort

void shellSort(int array[], int n) {

  // Rearrange elements at each n/2, n/4, n/8, ... intervals

  for (int interval = n / 2; interval > 0; interval /= 2) 

  {

    for (int i = interval; i < n; i += 1) {

      int temp = array[i];

      int j;

      for (j = i; j >= interval && 

      array[j - interval] > temp; j -= interval)

     {

        array[j] = array[j - interval];

      }

      array[j] = temp;

    }

  }

}

// Print an array

void printArray(int array[], int size) {

  int i;

  for (i = 0; i < size; i++)

    cout << array[i] << " ";

  cout << endl;

}

// Driver code

int main() {

  int data[] = {9, 8, 3, 7, 5, 6, 4, 1};

  int size = sizeof(data) / sizeof(data[0]);

  shellSort(data, size);

  cout << "Sorted array: \n";

  printArray(data, size);

}