Animation: Shellsort

Animation Systems Collection--Animations Collection

Description

Shellsort is one of the more unusual sorting algorithms. The basic idea is to insert new elements into a sorted sequence, much like with Insertion Sort.

The reason for the high complexity of Insertion Sort is that elements are only moved by one position. Shellsort tries to sort the elements quicker by moving the elements in larger steps. To do this the elements are h-sorted, i.e. the input sequence is sorted in h partial sequences consistent of all elements which have the distance of h to each other, e.g. for h=4 the sequences are 0, 4, 8; 1, 5, 9; 2, 6, 10 and 3,7,11.

These sequences are now sorted separately using Insertion Sort.

If the index sequence of h is chosen correctly (i.e. especially at the end the elements need to be h=1 sorted) the complete sequence will be sorted.

The calculation of the complexity of Shellsort is very complicated and is dependent on the index sequence of h.

The "pre-sorting" into h-sorted sequences only brings a benefit if there are at least 18 elements, so that is not seen in the animation.

Screen Shot(s):

Start - determine h

Test the first pair - in correct order

Mark pair for swapping

After swapping the elements

Classification

• Algorithms
• Sorting Algorithms

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Shellsort
Animation URL	http://www.animal.ahrgr.de/Anims/en/shellsort.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Marc-Daniel Haunschild
Date	1999-05-11
File Size size	5565 Byte
Number of Accesses:	19023
Added to DB by	Guido Rößling
Average Rating	5.1056(142 submitted ratings)
Language:	en
Number of Accesses:	19023

BibTeX bibliographic entry for citations:

@Misc{Haunschild:1999,
   author = {Marc-Daniel Haunschild},
   title = {Shellsort},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/shellsort.aml}},
 }