de.weaut.sortDemo

Class ShellSort

java.lang.Object

de.weaut.sortDemo.SortApp.SortAlgorithm

de.weaut.sortDemo.ShellSort

public final class ShellSort
extends SortApp.SortAlgorithm

Shell sort algorithm demonstration.

Shellsort is a simple extension of insertion sort which gains speed by allowing exchanges of elements that are far apart. The idea is to rearrange the array to give it the property that every hth element (starting anywhere) yields a sorted array. Such an array is said to be h-sorted.

By h-sorting for some large values of h, we can move elements in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values h which ends in 1 will produce a sorted array.

Note: Invented by Donald Lewis Shell [CACM, July, 1959, pages 30-32]

Author Jason Harrison, his version 1.1, 12 Apr 2000

Modif. 15.11.2005, Albrecht Weinert (a-weinert.de) :
SortApp.SortAlgorithm + minor improvements.

Version:

V.16, 16.03.2019

Author:

Albrecht Weinert

Field Summary

Fields inherited from class de.weaut.sortDemo.SortApp.SortAlgorithm

stopRequested

Constructor Summary

Constructors

Constructor and Description
ShellSort()

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Start as application.
void	sort(int[] a) The real sorting method.

Methods inherited from class de.weaut.sortDemo.SortApp.SortAlgorithm

getMaxPossiVal, pause, pause, pause, startMe, stop, swap

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ShellSort

public ShellSort()

Method Detail

sort

public void sort(int[] a)

Description copied from class: SortApp.SortAlgorithm

The real sorting method.

This method has to sort the array provided as parameter. Every substantial algorithmic step has to be marked by calling one of the callback methods SortApp.SortAlgorithm.pause(int, int), SortApp.SortAlgorithm.pause(int), SortApp.SortAlgorithm.pause() directly or indirectly by utilising SortApp.SortAlgorithm.swap(int, int) for element exchanges within the array having been provided to this sort implementation.
This pausing does all else like counting steps, displaying the sorting state and else.

As substantial step to be treated this way we see

• Assignments respectively swaps within the array to be sorted
  and (only in a first loop through the array) also
• a reading / comparing access to to one or two elements.

Specified by:

sort in class SortApp.SortAlgorithm

main

public static void main(java.lang.String[] args)

Start as application.

See Also:

SortApp.SortAlgorithm.startMe()