From Algorithm wiki
 Related content:
|
|
|
[edit] Introduction
- Shellsort, named after its inventor, Donald Shell, was one of the first algorithms to break the quadratic time barrier, although it was not until several years after its initial discovery that a subquadratic time bound was proven. As suggested in the previous section, it works by comparing elements that are distant; the distance between comparisons decreases as the algorithm runs until the last phase, in which adjacent elements are compared.
[edit] Pseudocode
Shell Sort (Sorting the array A[size])
Determine the number of segments by dividing the number of cells by two.
While the number of segments are greater than zero
{
For each segment, we do an Insertion Sort.
(think on how to write the loops here efficiently... )
Divide the number of segments by two.
}
[edit] C Code
#include <stdlib.h>
#include <stdio.h>
#define NUM_ITEMS 100
void shellSort(int numbers[], int array_size);
int numbers[NUM_ITEMS];
int main()
{
int i;
//seed random number generator
srand(getpid());
//fill array with random integers
for (i = 0; i < NUM_ITEMS; i++)
numbers[i] = rand();
//perform shell sort on array
shellSort(numbers, NUM_ITEMS);
printf("Done with sort.\n");
for (i = 0; i < NUM_ITEMS; i++)
printf("%i\n", numbers[i]);
return 0;
}
void shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;
increment = 3;
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 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}
[edit] C++ Code
template <typename Type> inline
void Shell(Type *pF, Type *pL)
{
int h;
Type *pI, *pJ;
Type v;
for (h=1; h<pL-pF-1; h=3*h+1); // h : 1, 4, 13, ...
for (; h>0; h/=3) {
for (pI=pF+h-1; ++pI<pL;) {
v = *pI;
for (pJ=pI; pJ>=pF+h && v<*(pJ-h); pJ-=h) {
*pJ = *(pJ-h);
}
*pJ = v;
}
}
}
[edit] Java Code
[edit] Java Code1
public void Shell_Sort(int[] array) {
int t = 0;
if (array.length % 2 == 0)
t = array.length >> 1;
else
t = (array.length >> 1) + 1;
while (t >= 1) {
for (int i = t,temp = 0; i < array.length; i++) {
for (int j = i - t; j >= 0; j =j - t) {
if (array[j] > array[j + t]) {
temp = array[j];
array[j] = array[j + t];
array[j + t] = temp;
}
}
}
if (t == 1)
break;
if (t % 2 == 0)
t = t >> 1;
else
t = (t >> 1) + 1;
}
}
[edit] Java Code2
class ShellSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
for (int incr = a.length / 2; incr > 0; incr /= 2) {
for(int i = incr; i < a.length; i++) {
int j = i - incr;
while(j >= 0) {
compex(j, j+incr);
pause();
if (a[j] > a[j+incr]) {
int T = a[j];
a[j] = a[j+incr];
a[j+incr] = T;
j -= incr;
}
else {
j = -1;
}
}
pause();
}
}
}
}
[edit] Python Code
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]
[edit] Visual C++ Code
#include<iostream>
#include<iomanip>
#include<conio.h>
using namespace std;
using namespace System;
void main()
{
const int tam=20;
int i, nd, j, inc;
float x[tam], temp;
do
{
cout<<"\n\tDigite el numero de datos (2 a "<<tam<<"): ";
cin>>nd;
}
while ((nd<=1)||(nd>tam));
cout<<"\n";
for (i=0; i<nd; i++)
{
cout<<"\tDato ("<<i+1<<"): ";
cin>>x[i];
}
for(inc=1; inc<nd;inc=(inc*3)+1);
while (inc>0)
{
for (i=inc; i<nd; i++)
{
j=i;
temp = x[i];
while ((j >= inc) && (x[j-inc] > temp))
{
x[j] = x[j - inc];
j = j - inc;
}
x[j] = temp;
}
inc /= 2;
}
for (i=0; i<nd; i++)
{
cout<<"\n\tDato ("<<i+1<<"): "<<x[i];
}
getch();
}
[edit] PHP Code
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);
[edit] C# Code
using System;
public class ShellSorter
{
public void Sort(int [] list)
{
int inc;
for(inc=1;inc<list.Length;inc=3*inc+1);
for(;inc>0;inc/=3)
{
for(int i=inc;i<list.Length;i+=1)//ceci car le tableau commence par 0
{
int t=list[i];
int j=i;
while((j>=inc)&&(list[j-inc]>t))
{
list[j]=list[j-inc];
j-=inc;
}
list[j]=t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
ShellSorter sh=new ShellSorter();
sh.Sort(iArrary);
for(int m=0;m<=13;m++)
Console.WriteLine("{0}",iArrary[m]);
}
}
[edit] VB Code
This section needs your Code!
[edit] Perl Code
sub shellsort{
my $array = shift; # Recibimos una referencia a un array
my $i; # Índice del elemento a comparar
my $j; # Índice del elemento actual a comparar
my $shell; # Tamaño del incremento
# Calculamos el valor del incremento
for($shell=1; $shell<@$array; $shell=2*$shell+1){;}
do{
$shell = int(($shell-1 )/2);
# Para todos los elementos, elegidos con un incremento
for($i = $shell; $i < @$array; ++$i){
for($j = $i - $shell;
$j >= 0 && $array->[$j] > $array->[$j + $shell];
$j -= $shell){
# Intercambiamos valores
@$array[$j, $j + $shell] = @$array[$j + $shell, $j];
}
}
}while $shell>1;
}
[edit] Pascal Code
procedure shellsort(a: array of char, arrlength:integer);
// 3 rows: 13, 4, 1
label 0;
var i,j,h,v:integer;
begin
h := 1;
repeat h := 3*h+1 until h > arrlength;
repeat
h := h div 3;
for i:= h + 1 to arrlength do
begin
v := a[i];
j := i;
while a[j-h] > v do
begin
a[j] := a[j-h];
j:= j-h;
if j >=h then goto 0
end; //while
0: a[j] := v;
end; // for
until h = 1;
end; //shellsort
[edit] Prolog Code
This section needs your Code!
[edit] Ruby Code
def shell_sort!(ary)
size = ary.size - 1
h = 1
h = 3*h + 1 while 9*h < size
while h > 0
for i in h..size
tmp = ary[i]
j = i - h
while j >= 0 and ary[j] > tmp
ary[j+h] = ary[j]
j -= h
end
ary[j+h] = tmp
end
h /= 3
end
ary
end
[edit] Basic Code
By Dave Stratford
DEF PROC_ShellSort(Size%)
Gap% = Size% / 2
WHILE Gap% > 0
FOR I% = Gap% TO Size%
J% = I%
Temp% = data%(I%)
WHILE J%>Gap% AND data%(J%-Gap%)>Temp%
data%(J%) = data%(J%-Gap%)
J%-=Gap%
ENDWHILE
IF I% <> J% data%(J%) = Temp%
NEXT I%
Gap% = Gap% / 2
ENDWHILE
ENDPROC
Related content:
