Shell sort

From CodeCodex

Related content:


Implementations[edit]

C[edit]

void shellSort(int numbers[], int array_size)
{
  int i, j, increment, temp;

  increment = array_size / 2;
  while (increment > 0)
  {
    for (i=0; i < array_size; i++)
    {
      j = i;
      temp = numbers[i];
      while ((j >= increment) && (numbers[j-increment] > temp))
      {
        numbers[j] = numbers[j - increment];
        j = j - increment;
      }
      numbers[j] = temp;
    }
    if (increment == 2)
    	increment = 1;
    else 
    	increment = increment * 5 / 11;
  }
}

Original source: [1]

D[edit]

import std.stdio;

void shellSort(T)(T[] items) {
    int inc = items.length / 2;
    while (inc) {
        for (int i; i < items.length; i++) {
            int j = i;
            T temp = items[i];
            while (j >= inc && items[j-inc] > temp) {
                items[j] = items[j - inc];
                j -= inc;
            }
            items[j] = temp;
        }
        inc = inc/2 ? inc/2 : (inc==1 ? 0 : 1);
    }
}

void main() {
    auto a = [35, -8, 11, 1, 68, 0, 3];
    shellSort(a);
    writefln(a); // [-8,0,1,3,11,35,68]
}

Python[edit]

def shellSort(items):
    inc = len(items) / 2
    while inc:
        for i in xrange(len(items)):
            j = i
            temp = items[i]
            while j >= inc and items[j-inc] > temp:
                items[j] = items[j - inc]
                j -= inc
            items[j] = temp
        inc = inc/2 if inc/2 else (0 if inc==1 else 1)

a = [35, -8, 11, 1, 68, 0, 3];
shellSort(a)
print a # [-8, 0, 1, 3, 11, 35, 68]

Ruby[edit]

def shell_sort(items)
  inc = items.size / 2
  while inc > 0
    inc.upto(items.size-1){|i|
      j = i
      temp = items[i]
      while j >= inc and items[j-inc] > temp
        items[j] = items[j - inc]
        j -= inc
      end
      items[j] = temp
    }
    inc = (inc==2 ? 1 : inc*10/22)
  end
  items
end

a = [35, -8, 11, 1, 68, 0, 3]
shell_sort(a)
p a  #=> [-8, 0, 1, 3, 11, 35, 68]

Seed7[edit]

const proc: shellSort (inout array elemType: arr) is func
  local
    var integer: i is 0;
    var integer: j is 0;
    var integer: increment is 0;
    var elemType: help is elemType.value;
  begin
    increment := length(arr) div 2;
    while increment > 0 do
      for i range 1 to length(arr) do
        j := i;
        help := arr[i];
        while j > increment and arr[j - increment] > help do
          arr[j] := arr[j - increment];
          j -:= increment;
        end while;
        arr[j] := help;
      end for;
      increment := increment div 2;
    end while;
  end func;

Original source: [2]