Реализации алгоритмов/Сортировка/Шелла

Псевдокод

ЗАДАЧА Шелл(a=: РЯД ИЗ ЦЕЛ);
ПЕР
  b,i,j,k,h: ЦЕЛ;
УКАЗ
  b:=РАЗМЕР(a);
  k:=b ДЕЛИТЬ 2;
  ПОКА k>0 ВЫП
    ОТ i:=1 ДО b-k ВЫП
      j:=i;
      ПОКА (j>=1) И (a[j]>a[j+k]) ВЫП
        h:=a[j];
        a[j]:=a[j+k];
        a[j+k]:=h;
        УМЕНЬШИТЬ(j);
      КОН;
    КОН;
    k:=k ДЕЛИТЬ 2
  КОН
КОН Шелл;

Cи

/* Пример из книги Герберта Шилдта */
void shell(char *items, int count)
{
  register int i, j, gap, k;
  char x, a[5];

  a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

  for(k=0; k < 5; k++) {
    gap = a[k];
    for(i=gap; i < count; ++i) {
      x = items[i];
      for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)
        items[j+gap] = items[j];
      items[j+gap] = x;
    }
  }
}

C++

int increment(long inc[], long size) {
// inc[] массив, в который заносятся инкременты
// size размерность этого массива
 int p1, p2, p3, s;

  p1 = p2 = p3 = 1;
  s = -1;
  do {// заполняем массив элементов по формуле Роберта Седжвика
    if (++s % 2) {
      inc[s] = 8*p1 - 6*p2 + 1;
    } else {
      inc[s] = 9*p1 - 9*p3 + 1;
      p2 *= 2;
      p3 *= 2;
    }
	p1 *= 2;
// заполняем массив, пока текущая инкремента хотя бы в 3 раза меньше количества элементов в массиве
  } while(3*inc[s] < size);

  return s > 0 ? --s : 0;// возвращаем количество элементов в массиве
}

template<class T>
void shellSort(T a[], long size) {
// inc инкремент, расстояние между элементами сравнения
// i и j стандартные переменные цикла
// seq[40] массив, в котором хранятся инкременты
  long inc, i, j, seq[40];
  int s;//количество элементов в массиве seq[40]

  // вычисление последовательности приращений
  s = increment(seq, size);
  while (s >= 0) {
	//извлекаем из массива очередную инкременту
	inc = seq[s--];
// сортировка вставками с инкрементами inc
    for (i = inc; i < size; i++) {
      T temp = a[i];
// сдвигаем элементы до тех пор, пока не дойдем до конца или не упорядочим в нужном порядке
      for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)
        a[j+inc] = a[j];
// после всех сдвигов ставим на место j+inc элемент, который находился на i месте
      a[j+inc] = temp;
    }
  }
}

VBA

Sub Sort(Mus() As Long)
  Dim i As Long, k As Long, Pos As Long
  Dim l As Long, r As Long, n As Long, tmp As Long

  l = LBound(Mus)
  r = UBound(Mus)
  n = r - l + 1
  k = 1
  Do
    k = k * 3 + 1
  Loop Until k > n

  Do
    k = k \ 3
    For i = (k + l) To r
       Pos = i
       tmp = Mus(i)
       Do While Mus(Pos - k) > tmp
         Mus(Pos) = Mus(Pos - k)
         Pos = Pos - k
         If (Pos - k) < l Then Exit Do
       Loop
       Mus(Pos) = tmp
    Next
  Loop Until k = 1
End Sub

C#

 public void ShellSorting(int[] arr)
        {
            int j;
            int step = arr.Length / 2;
            while (step > 0)
            {
                for (int i = 0; i < (arr.Length - step); i++)
                {
                    j = i;
                    while ((j >= 0) && (arr[j] > arr[j + step]))
                    {
                        Swap(arr, j, j + step);
                        j = j - step;
                    }
                }
                step = step / 2;
            }
        }

Этот более быстрый

private void shellSort(int[] vector)
        {
            int step = vector.Length / 2;
            while (step > 0)
            {
                int i, j;
                for (i = step; i < vector.Length; i++)
                {
                    int value = vector[i];
                    for (j = i - step; (j >= 0) && (vector[j] > value); j -= step)
                        vector[j + step] = vector[j];
                    vector[j + step] = value;
                }
                step /= 2;
            }
        }

Java

void sort_shell(int[] a){
   int i, j, k, h, m=0, b=a.length;
   int[] d = { 1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11969, 27901,
               84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
               58548857, 157840433, 410151271, 1131376761, 2147483647 };
   while (d[m] < b) ++m;
   while (--m >= 0){
      k = d[m];
      for (i = k; i < b; i++){     // k-сортировка
         j=i;
         h=a[i];
         while ((j >= k) && (a[j-k] > h)){
              a[j]=a[j-k];
              j -= k;
         }
         a[j] = h;
      }
   }
}

Object Pascal (Delphi)

var
  incr: array [0..23] of integer = (1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711,
  11969, 27901, 84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
  58548857, 157840433, 410151271, 1131376761, 2147483647);

type arInt = array of integer;
procedure ShellSort(var Arr: arInt);
  var
     C: Boolean;
     G: Integer;
     I: Integer;
     J: Integer;
     Tmp: Integer;
     len: Integer;
     cur_inc: integer;
begin
  len := Length(Arr) - 1;
  cur_inc := 0;
  while 3 * incr[cur_inc + 1] <= Length(Arr) do
    inc(cur_inc);
  repeat
    g := incr[cur_inc];
    i := g;
    repeat
      j := i - g;
      c := True;
      repeat
        if arr[j] <= arr[j + g] then
          c := False
        else
        begin
          Tmp := Arr[j];
          Arr[j] := Arr[j+g];
          Arr[j+g] := Tmp;
        end;
        dec(j, g);
      until  not ((j >= 0) and C);
      inc(i);
    until  not (i <= len);
    dec(cur_inc);
  until  not (cur_inc <> -1);
end;

PHP

 function ShellSort($elements,$length) {
     $k=0;
     $gap[0] = (int) ($length / 2);

     while($gap[$k] > 1) {
         $k++;
         $gap[$k]= (int)($gap[$k-1] / 2);
     }//end while

     for($i = 0; $i <= $k; $i++){
         $step=$gap[$i];

         for($j = $step; $j < $length; $j++) {
             $temp = $elements[$j];
             $p = $j - $step;
             while($p >= 0 && $temp < $elements[$p]) {
                 $elements[$p + $step] = $elements[$p];
                 $p= $p - $step;
             }//end while
             $elements[$p + $step] = $temp;
         }//endfor j
     }//endfor i

     return $elements;
 }// end function

 // Exmaple
 // $SortedElements=shellsort($UnsortedElements,length of list(an integer));
 // e.g: $elements=shellsort($elements,10);

Python

  import numpy
  def shellsort(a):
      def new_increment(a):
          i = int(len(a) / 2)
          yield i
          while i != 1:
              if i == 2:
                  i = 1
              else:
                  i = int(numpy.round(i/2.2))
              yield i
      for increment in new_increment(a):
          for i in xrange(increment, len(a)):
              for j in xrange(i, increment-1, -increment):
                  if a[j - increment] < a[j]:
                      break
                  a[j],a[j - increment] = a[j - increment],a[j]
      return a

Ruby

n = mass.size - 1
d = n/2
while d >= 1
n.downto(0) do |i|
 0.upto(i-d) do |j|
   mass[j], mass[j+d] = mass[j+d], mass[j] if mass[j] > mass[j+d]
 end
end
d /= 2
end
puts mass

Perl

use warnings;
use strict;
use feature 'say';

my @array = (5, 3, 7, 9, 2, 1, 6, 5, 3, 7, 9, 3, 4);

say "@array - initial";

for (my $k = int @array / 2; $k > 0; $k = int $k / 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 (my $i = $k; $i < @array; ++$i) {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        my $temp = $array[$i];
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        my $j;
        for ($j = $i; $j >= $k && $array[$j - $k] > $temp; $j -= $k) {
            $array[$j] = $array[$j - $k];
        }
        # put temp (the original a[i]) in its correct location
        $array[$j] = $temp;
    }
    say "@array";
}

#5 3 7 9 2 1 6 5 3 7 9 3 4 - initial
#4 3 3 7 2 1 5 5 7 9 9 3 6
#4 2 1 5 3 3 6 5 3 7 9 7 9
#1 2 3 3 3 4 5 5 6 7 7 9 9

Perl (вариант 2)

use feature 'say';

my @a = qw{5 3 7 9 2 1 6 5 3 7 9 3 4};
say "@a - initial";

for(my $k = int($#a / 2); $k > 0; $k = int($k / 2)){
	for my $i (0..($#a - $k)){
		for(my $j = $i; $j >= 0 && $a[$j] > $a[$j + $k]; --$j){
			($a[$j + $k], $a[$j]) = ($a[$j], $a[$j + $k]);
			say "@a";
		}
	}
}

Perl 6

my @a = <5 3 7 9 2 1 6 5 3 7 9 3 1>;
loop (my $k = @a.elems div 2; $k > 0; $k div= 2) {
	for 0..@a.elems - $k -> $l is copy {
		@a[$l, $l + $k] = @a[$l + $k, $l] if @a[$l] > @a[$l + $k] while --$l >= 0 ;
	}
}
say @a;

PLSQL

type sort_lst is table of integer; 
----------------------Шеллосортировка-----------------------------------------------
Function Shell_sort(in_list IN sort_lst) return sort_lst
  IS   
   l_list sort_lst := sort_lst();
   l_length pls_integer;
   b pls_integer; k number; h pls_integer; j pls_integer;
   v pls_integer := 1 ;
begin  
    l_list := in_list;
    b := l_list.last;
    k:= b/2;
     while k>=1 loop
       for i in 1..b-k loop
           j:=i;    
          if round(j+k) <= l_list.last then --чтобы не выйти за пределы массива PL SQL
               while (j>=1) and (l_list(j)>l_list((j+k))) loop 
                  h:= l_list(j);
                  l_list(j):=l_list(j+k);
                  l_list(j+k):=h;
                  j:=j-1;
               end loop;  
          end if;     
       end loop;
       k:=k/2;  
     end loop;            
   return l_list;                                     
end Shell_sort;
------------------------------------------------------------------------------------