Реализации алгоритмов/Сортировка/Шелла
Псевдокод
правитьЗАДАЧА Шелл(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
КОН
КОН Шелл;
/* Пример из книги Герберта Шилдта */
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;
}
}
}
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;
}
}
}
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
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;
}
}
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;
}
}
}
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;
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);
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
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
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
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";
}
}
}
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;
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;
------------------------------------------------------------------------------------