Sorting algorithms/Shell sort: Difference between revisions

Content added Content deleted
m (Fixed lang tags.)
Line 5: Line 5:
=={{header|Ada}}==
=={{header|Ada}}==
This is a generic implementation of the shell sort. Ada allows arrays to be indexed by integer or enumeration types starting at any value. This version deals with any kind or value of valid index type.
This is a generic implementation of the shell sort. Ada allows arrays to be indexed by integer or enumeration types starting at any value. This version deals with any kind or value of valid index type.
<lang ada>
<lang ada>generic
generic
type Element_Type is digits <>;
type Element_Type is digits <>;
type Index_Type is (<>);
type Index_Type is (<>);
Line 12: Line 11:
package Shell_Sort is
package Shell_Sort is
procedure Sort(Item : in out Array_Type);
procedure Sort(Item : in out Array_Type);
end Shell_Sort;
end Shell_Sort;</lang>
</lang>
<lang ada>package body Shell_Sort is
<lang ada>package body Shell_Sort is
Line 43: Line 41:
end Sort;
end Sort;


end Shell_Sort;
end Shell_Sort;</lang>
</lang>


=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
Line 52: Line 49:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
<lang algol>MODE TYPE = CHAR;
<lang algol68>MODE TYPE = CHAR;


PROC in place shell sort = (REF[]TYPE seq)REF[]TYPE:(
PROC in place shell sort = (REF[]TYPE seq)REF[]TYPE:(
Line 196: Line 193:
=={{header|D}}==
=={{header|D}}==
From the Python version, uses Phobos of D 1.
From the Python version, uses Phobos of D 1.
<lang d>
<lang d>import std.stdio: writefln;
import std.stdio: writefln;


void shell(T)(T[] seq) {
void shell(T)(T[] seq) {
Line 217: Line 213:
shell(data);
shell(data);
writefln(data); // [-5, 2, 4, 7, 8, 22]
writefln(data); // [-5, 2, 4, 7, 8, 22]
}</lang>
}
</lang>


=={{header|E}}==
=={{header|E}}==
Line 241: Line 236:
=={{header|Forth}}==
=={{header|Forth}}==
{{works with|GNU Forth}}
{{works with|GNU Forth}}
defer less? ' < is less?
<lang forth>defer less? ' < is less?
: shell { array len -- }
1 begin dup len u<= while 2* 1+ repeat { gap }
begin gap 2/ dup to gap while
len gap do
array i cells +
dup @ swap ( temp last )
begin gap cells -
array over u<=
while 2dup @ less?
while dup gap cells + over @ swap !
repeat then
gap cells + !
loop
repeat ;


: shell { array len -- }
create array 8 , 1 , 4 , 2 , 10 , 3 , 7 , 9 , 6 , 5 ,
1 begin dup len u<= while 2* 1+ repeat { gap }
begin gap 2/ dup to gap while
array 10 shell
len gap do
array 10 cells dump
array i cells +
dup @ swap ( temp last )
begin gap cells -
array over u<=
while 2dup @ less?
while dup gap cells + over @ swap !
repeat then
gap cells + !
loop
repeat ;

create array 8 , 1 , 4 , 2 , 10 , 3 , 7 , 9 , 6 , 5 ,

array 10 shell
array 10 cells dump</lang>


=={{header|Fortran}}==
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
{{works with|Fortran|90 and later}}
<lang fortran> MODULE sort
<lang fortran>MODULE sort

CONTAINS

SUBROUTINE Shell_Sort(a)

IMPLICIT NONE
INTEGER :: i, j, increment
REAL :: temp
REAL, INTENT(in out) :: a(:)
increment = SIZE(a) / 2
DO WHILE (increment > 0)
DO i = increment+1, SIZE(a)
j = i
temp = a(i)
DO WHILE (j >= increment+1 .AND. a(j-increment) > temp)
a(j) = a(j-increment)
j = j - increment
END DO
a(j) = temp
END DO
IF (increment == 2) THEN
increment = 1
ELSE
increment = increment * 5 / 11
END IF
END DO
END SUBROUTINE Shell_Sort
CONTAINS

END MODULE sort

PROGRAM Shellsort

USE sort

IMPLICIT NONE
REAL :: array(1000)
CALL RANDOM_SEED
CALL RANDOM_NUMBER(array)
WRITE (*,*) "Unsorted array"
SUBROUTINE Shell_Sort(a)
WRITE (*,*) array
WRITE (*,*)
IMPLICIT NONE
CALL Shell_Sort(array)
INTEGER :: i, j, increment
WRITE (*,*) "Sorted array"
REAL :: temp
WRITE (*,*) array
REAL, INTENT(in out) :: a(:)
increment = SIZE(a) / 2
DO WHILE (increment > 0)
DO i = increment+1, SIZE(a)
j = i
temp = a(i)
DO WHILE (j >= increment+1 .AND. a(j-increment) > temp)
a(j) = a(j-increment)
j = j - increment
END DO
a(j) = temp
END DO
IF (increment == 2) THEN
increment = 1
ELSE
increment = increment * 5 / 11
END IF
END DO
END PROGRAM Shellsort</lang>
END SUBROUTINE Shell_Sort
END MODULE sort
PROGRAM Shellsort
USE sort
IMPLICIT NONE
REAL :: array(1000)
CALL RANDOM_SEED
CALL RANDOM_NUMBER(array)
WRITE (*,*) "Unsorted array"
WRITE (*,*) array
WRITE (*,*)
CALL Shell_Sort(array)
WRITE (*,*) "Sorted array"
WRITE (*,*) array
END PROGRAM Shellsort</lang>


=={{header|Haskell}}==
=={{header|Haskell}}==
Line 352: Line 347:


=={{header|Lisaac}}==
=={{header|Lisaac}}==
<lang Lisaac>
<lang Lisaac>Section Header
Section Header


+ name := SHELL_SORT;
+ name := SHELL_SORT;
Line 398: Line 392:
};
};
};
};
);
);</lang>
</lang>


=={{header|OCaml}}==
=={{header|OCaml}}==
Line 471: Line 464:


This method sorts in place. If you want to preserve your unsorted list, copy it first.
This method sorts in place. If you want to preserve your unsorted list, copy it first.
<lang python>
<lang python>def shell(seq):
def shell(seq):
inc = len(seq) // 2
inc = len(seq) // 2
while inc:
while inc:
Line 484: Line 476:
data = [22, 7, 2, -5, 8, 4]
data = [22, 7, 2, -5, 8, 4]
shell(data)
shell(data)
print data # [-5, 2, 4, 7, 8, 22]
print data # [-5, 2, 4, 7, 8, 22]</lang>
</lang>


=={{header|Ruby}}==
=={{header|Ruby}}==
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Shell_sort"