Shell Sort

  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;
// Part of Cosmos by OpenGenus Foundation
void shellSort(vector<int> &ar)
{
  size_t j;
  for (size_t gap = ar.size() / 2; gap > 0; gap /= 2)
    {
      for (size_t i = gap; i < ar.size(); i++)
      {
          int temp = ar[i];
          for (j = i; j >= gap && temp < ar[j - gap]; j -= gap)
          {
            ar[j] = ar[j - gap];
          }
          ar[j] = temp;
      } 
    }
}
int main()
{
  vector<int> inputArray;
  cout << "Enter the elements of the array: ";
  for(int i;cin>>i;)
  {
    inputArray.push_back(i);
  }
  shellSort(inputArray);
  for(size_t i=0;i<inputArray.size();i++)
  {
    cout<<inputArray[i]<<" ";
  }
  cout<<endl;
  return 0;
}

  // Java implementation of ShellSort
// Part of Cosmos by OpenGenus Foundation
class ShellSort
{
    /* An utility function to print array of size n*/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    /* function to sort arr using shellSort */
    int sort(int arr[])
    {
        int n = arr.length;
        // 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;
    }
     // Driver method
    public static void main(String args[])
    {
        int arr[] = {12, 34, 54, 2, 3};
        System.out.println("Array before sorting");
        printArray(arr);
        ShellSort ob = new ShellSort();
        ob.sort(arr);
        System.out.println("Array after sorting");
        printArray(arr);
    }
} 

  # Part of Cosmos by OpenGenus Foundation
def shell_sort(alist):
    sub_list_count = len(alist) // 2
    while sub_list_count > 0:
        for start in range(sub_list_count):
            gap_insertion_sort(alist, start, sub_list_count)
        sub_list_count = sub_list_count // 2
def gap_insertion_sort(alist, start, gap):
    for i in range(start + gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position - gap] > currentvalue:
            alist[position] = alist[position - gap]
            position = position - gap
        alist[position] = currentvalue
alist = [91, 91, 82, 45, 48, 35, 83, 70, 97]
print("Before: ", alist)
shell_sort(alist)
print("After: ", alist)

  package main
import (
    "fmt"
)
func main() {
    var n int
    fmt.Println("Please enter the lenght of the array:")
    fmt.Scan(&n)
    X := make([]int, n)
    fmt.Println("Now, enter the elements X0 X1 ... Xn-1")
     for i := 0; i < n; i++ {
        fmt.Scanln(&X[i])
    }
    fmt.Printf("Unsorted array: %v\n", X)
    fmt.Printf("Sorted array: %v\n", BubbleSort(X))  
}
func shellSort(array []int) {
  h := 1
  for h < len(array) {
    h = 3 * h + 1
  }
  for h >= 1 {
    for i := h; i < len(array); i++ {
      for j := i; j >= h && array[j] < array[j - h]; j = j - h {
        algoutils.Swap(array, j, j - h)
      }
    }
    h = h/3
  }
}

  // Part of Cosmos by OpenGenus Foundation
function shellSort (a) {
  for (var h = a.length; h > 0; h = parseInt(h / 2)) {
    for (var i = h; i < a.length; i++) {
      var k = a[i];
      for (var j = i; j >= h && k < a[j - h]; j -= h)
        a[j] = a[j - h];
      a[j] = k;
    }
  }
  return a;
}

  /* Part of Cosmos by OpenGenus Foundation */
//
//  shell_sort.m
//  Created by DaiPei on 2017/10/9.
//
#import <Foundation/Foundation.h>
@interface ShellSort : NSObject
- (void)sort:(NSMutableArray<NSNumber *> *)array;
@end
@implementation ShellSort
- (void)sort:(NSMutableArray<NSNumber *> *)array {
    for (int h = (int)array.count / 2; h > 0; h /= 2) {
        for (int i = h; i < array.count; i++) {
            NSNumber *k = array[i];
            int j;
            for (j = i; j >= h && [k compare:array[j - h]] == NSOrderedAscending; j -= h) {
                array[j] = array[j - h];
            }
            array[j] = k;
        }
    }
}
@end
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int n = 0;
        NSLog(@"What is the size of the array?");
        scanf("%d", &n);
        NSMutableArray *array = [NSMutableArray arrayWithCapacity:n];
        NSLog(@"Enter elements of the array one by one:");
        for (int i = 0; i < n; i++) {
            int tmp;
            scanf("%d", &tmp);
            [array addObject:@(tmp)];
        }
        ShellSort *ss = [[ShellSort alloc] init];
        [ss sort:array];
        NSLog(@"%@", array);
    }
    return 0;
}

/* Part of Cosmos by OpenGenus Foundation */
//
//  shell_sort.swift
//  Created by DaiPei on 2017/10/11.
//
import Foundation
func shellSort(_ array: inout [Int]) {
    var h = array.count / 2
    while h > 0 {
        for i in h..<array.count {
            let key = array[i]
            var j = i
            while j >= h && key < array[j - h] {
                array[j] = array[j - h]
                j -= h
            }
            array[j] = key
        }
        h /= 2
    }
}