Shell Sort

Download Shell Sort

---

//

//  main.cpp

//  Shell_Sort

//

//  Created by Zhenlin Pei on 12/23/18.

//  Copyright © 2018 Zhenlin Pei. All rights reserved.

//

// C++ implementation of Shell Sort

#include <iostream>

using namespace std;

/* function to sort arr using shellSort */

int shellSort(int arr[], int n)

{

    // Start with a big gap, then reduce the gap

    for (int gap = n / 2; gap > 0; gap /= 2) {

        // Do a gapped insertion sort for this gap size.

        // The first gap elements a[0..gap-1] are already in gapped order

        // keep adding one more element until the entire array is

        // gap sorted

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

            // add a[i] to the elements that have been gap sorted

            // save a[i] in temp and make a hole at position i

            int temp = arr[i];

            

            // shift earlier gap-sorted elements up until the correct

            // location for a[i] is found

            int j;

            for (j = i; j >= gap && arr[j – gap] > temp; j -= gap)

                arr[j] = arr[j – gap];

            

            // put temp (the original a[i]) in its correct location

            arr[j] = temp;

        }

    }

    return 0;

}

void printArray(int arr[], int n)

{

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

        cout << arr[i] << ” “;

}

int main()

{

    int arr[] = { 12, 34, 54, 2, 3 };

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

    

    cout << “Array before sorting: \n”;

    printArray(arr, n);

    

    shellSort(arr, n);

    

    cout << “\nArray after sorting: \n”;

    printArray(arr, n);

    

    return 0;

}

---