Sorting algorithms/Shell sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 20:33, 10 December 2008

In this task, the goal is to sort an array of elements using the Shell sort algorithm, a diminishing increment sort. The Shell sort is named after its inventor, Donald Shell, who published the algorithm in 1959. Shellsort is a sequence of interleaved insertion sorts based on an increment sequence. The increment size is reduced after each pass until the increment size is 1. With an increment size of 1, the sort is a basic insertion sort, but by this time the data is guaranteed to be almost sorted, which is insertion sort's "best case". Any sequence will sort the data as long as it ends in 1, but some work better than others. Empirical studies have shown a geometric increment sequence with a ratio of about 2.2 work well in practice. [1] Other good sequences are found at the Online Encyclopedia of Integer Sequences.

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. <ada> generic

  type Element_Type is digits <>;
  type Index_Type is (<>);
  type Array_Type is array(Index_Type range <>) of Element_Type;

package Shell_Sort is

  procedure Sort(Item : in out Array_Type);

end Shell_Sort; </ada> <ada>package body Shell_Sort is

  ----------
  -- Sort --
  ----------

  procedure Sort (Item : in out Array_Type) is
     Increment : Natural := Index_Type'Pos(Item'Last) / 2;
     J : Index_Type;
     Temp : Element_Type;
  begin
     while Increment > 0 loop
        for I in Index_Type'Val(Increment) .. Item'Last loop
           J := I;
           Temp := Item(I);
           while J > Index_Type'val(Increment) and then Item (Index_Type'Val(Index_Type'Pos(J) - Increment)) > Temp loop
              Item(J) := Item (Index_Type'Val(Index_Type'Pos(J) - Increment));
              J := Index_Type'Val(Index_Type'Pos(J) - Increment);
           end loop;
           Item(J) := Temp;
        end loop;
        if Increment = 2 then
           Increment := 1;
        else
           Increment := Increment * 5 / 11;
        end if;
     end loop;
  end Sort;

end Shell_Sort; </ada>

C

This implementation uses an array of pre-defined increments <c>#include <ansi_c.h>

define ARRAYSIZE 100000 /* or whatever */

void shellsort (int a[], int length);

int main (int argc, char *argv[]) {

 int intArray[ARRAYSIZE], i, increment; 

 for(i=0; i<=ARRAYSIZE-1; i++)
  intArray[i] = rand();
  shellsort(intArray, ARRAYSIZE);

}

void shellsort (int a[], int length) {

 int i, j, k, temp, increment;
 static int incSequence[] = {412771, 165103, 66041, 26417, 10567, 4231, 1693, 673, 269, 107, 43, 17, 7, 3, 1};

 for (k = 0; k < sizeof(incSequence)/sizeof(int); k++)
 {
   if (incSequence[k]*2 > length) continue;
   increment = incSequence[k];   
   for (i=increment; i < length; i++)
   {
     temp = a[i];
     for (j = i - increment; j >= 0; j -= increment)
     {
       if (a[j] <= temp) break;
       a[j + increment] = a[j];
     }
     a[j + increment] = temp;
   }
 }

}</c>

D

From the Python version, uses Phobos of D 1. <d> import std.stdio: writefln;

void shell(T)(T[] seq) {

   int inc = seq.length / 2;
   while (inc) {
       foreach (i, el; seq) {
           while (i >= inc && seq[i - inc] > el) {
               seq[i] = seq[i - inc];
               i -= inc;
           }
           seq[i] = el;
       }
       inc = inc == 2 ? 1 : cast(int)(inc * 5.0 / 11);
   }

}

void main() {

   int[] data = [22, 7, 2, -5, 8, 4].dup;
   shell(data);
   writefln(data); // [-5, 2, 4, 7, 8, 22]

} </d>

Forth

Works with: GNU 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 ;

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

array 10 shell
array 10 cells dump

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

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

Java

Translation of: Fortran

This method will sort in place. If you want to preserve your unsorted array, use a copy of the array as an argument to this method. <java>public static void shell(int[] a) { int increment = a.length / 2; while (increment > 0) { for (int i = increment; i < a.length; i++) { int j = i; int temp = a[i]; while (j >= increment && a[j - increment] > temp) { a[j] = a[j - increment]; j -= increment; } a[j] = temp; } if (increment == 2) { increment = 1; } else { increment *= (5.0 / 11); } } }</java>

Python

Translation of: Java

This method sorts in place. If you want to preserve your unsorted list, copy it first. <python> def shell(seq):

   inc = len(seq) // 2
   while inc:
       for i, el in enumerate(seq):
           while i >= inc and seq[i - inc] > el:
               seq[i] = seq[i - inc]
               i -= inc
           seq[i] = el
       inc = 1 if inc == 2 else int(inc * 5.0 / 11)

data = [22, 7, 2, -5, 8, 4] shell(data) print data # [-5, 2, 4, 7, 8, 22] </python>

@@ Line 1: / Line 1: @@
 {{task|Sorting Algorithms}}{{Sorting Algorithm}}
 In this task, the goal is to sort an array of elements using the Shell sort algorithm, a diminishing increment sort. The Shell sort is named after its inventor, Donald Shell, who published the algorithm in 1959. Shellsort is a sequence of interleaved insertion sorts based on an increment sequence. The increment size is reduced after each pass until the increment size is 1. With an increment size of 1, the sort is a basic insertion sort, but by this time the data is guaranteed to be almost sorted, which is insertion sort's "best case". Any sequence will sort the data as long as it ends in 1, but some work better than others. Empirical studies have shown a geometric increment sequence with a ratio of about 2.2 work well in practice.
-[http://www.cs.princeton.edu/~rs/shell/]
+[http://www.cs.princeton.edu/~rs/shell/]  Other good sequences are found at the [http://www.research.att.com/~njas/sequences/?q=shell+sort Online Encyclopedia of Integer Sequences].
 =={{header|Ada}}==