Shell sort ( Shell sort ) - sorting algorithm , which is an improved option for sorting inserts . The idea of the Shell method is to compare elements that are not only nearby, but also at a certain distance from each other. In other words, this is sorting by inserts with preliminary “rough” passes. A similar method for improving bubble sorting is called comb sorting .
| Shell Sort | |
|---|---|
 Sort in steps 23, 10, 4, 1. | |
| Author | |
| Destination | Sorting algorithm |
| Data structure | Array |
| Worst time | O ( n 2 ) |
| Best time | O ( n log 2 n ) |
| Average time | depends on the steps chosen |
| Memory overhead | O (n) total, O (1) optional |
Content
Description
When sorting Shell, values are first compared and sorted among themselves, at a certain distance from each other (about choosing a value see below ). After this, the procedure is repeated for some lower values. , and Shell sorting is completed by ordering the elements when (i.e. normal sorting by inserts ). The efficiency of Shell sorting in certain cases is ensured by the fact that the elements “fall faster” fall into place (in simple sorting methods, for example, bubble sorting, each rearrangement of two elements reduces the number of inversions in the list by a maximum of 1, and when sorting Shell, this number may be greater )
Despite the fact that Shell sorting is in many cases slower than fast sorting , it has several advantages:
- lack of memory requirements for the stack;
- no degradation due to unsuccessful data sets - quick sorting easily degrades to O (n²), which is worse than the worst guaranteed time for Shell sorting.
History
Shell sorting was named after its inventor, Donald Shell , who published this algorithm in 1959 .
Example
Let the list be given and it is sorted by the Shell method, and as values selected .
The first step is sorting the sublists. made up of all elements , differing by 5 positions, i.e. sublists , , , , .
In the resulting list, in the second step, the sublists are again sorted from the elements spaced by 3 positions.
The process ends with the usual sorting by inserts of the resulting list.
Gap Length Selection
The average runtime of the algorithm depends on the lengths of the gaps - on which there will be sortable elements of the original array with capacity at every step of the algorithm. There are several approaches to choosing these values:
- The sequence of spacing lengths originally used by Shell: in the worst case, the complexity of the algorithm is ;
- Hibbard-proposed sequence: all values ; such a sequence of steps leads to an algorithm of complexity ;
- Sedgwick proposed sequence: if i is even and if i is odd. When using such increments, the average complexity of the algorithm is: , and in the worst case order . When using the Sedgwick formula, we should focus on the value inc [s-1] if 3 * inc [s]> size. [1] ;
- Pratt's proposed sequence: all values ; in this case, the complexity of the algorithm is ;
- the empirical sequence of Marcin Tsiur (sequence A102549 in OEIS ): ; is one of the best for sorting an array with a capacity of up to about 4000 elements. [2] ;
- empirical sequence based on Fibonacci numbers : ;
- all values , ; such a sequence of steps leads to an algorithm of complexity .
C ++ Implementation
template < typename RandomAccessIterator , typename Compare >
void shell_sort ( RandomAccessIterator first , RandomAccessIterator last , Compare comp )
{
for ( typename std :: iterator_traits < RandomAccessIterator > :: difference_type d = ( last - first ) / 2 ; d ! = 0 ; d / = 2 )
// need a loop for first = a [0..d-1]
for ( RandomAccessIterator i = first + d ; i ! = last ; ++ i )
for ( RandomAccessIterator j = i ; j - first > = d && comp ( * j , * ( j - d ) ); j - = d )
std :: swap ( * j , * ( j - d ) );
}
C implementation
void ShellSort ( int array [], int size ) // * Δk = (bΔk − 1) / 2 Δ0 = N
{
int step , i , j , tmp ;
// Select step
for ( step = size / 2 ; step > 0 ; step / = 2 )
// Listing items that are sorted at a specific step
for ( i = step ; i < size ; i ++ )
// Rearrange the elements inside the sublist until the i-th is sorted
for ( j = i - step ; j > = 0 && array [ j ] > array [ j + step ]; j - = step )
{
tmp = array [ j ];
array [ j ] = array [ j + step ];
array [ j + step ] = tmp ;
}
}
Java Implementation
public class ShellSort
{
public void sort ( int [] arr )
{
for ( int inc = arr . length / 2 ; inc > = 1 ; inc = inc / 2 ;)
for ( int step = 0 ; step < i ; step ++)
insertionSort ( arr , step , inc );
}
private void insertionSort ( int [] arr , int start , int inc )
{
int tmp ;
for ( int i = start ; i < arr . length - 1 ; i + = inc )
for ( int j = Math . min ( i + inc , arr . length - 1 ); j - inc > = 0 ; j = j - inc )
if ( arr [ j - inc ] > arr [ j ])
{
tmp = arr [ j ];
arr [ j ] = arr [ j - inc ];
arr [ j - inc ] = tmp ;
}
else break ;
}
}
Python implementation
def shellSort ( array ):
increment = len ( array ) // 2
while increment > 0 :
for startPosition in range ( increment ):
gapInsertionSort ( array , startPosition , increment )
print ( "After incrementing the size by" , increment , "array:" , array )
increment // = 2
def gapInsertionSort ( array , low , gap ):
for i in range ( low + gap , len ( array ), gap ):
currentvalue = array [ i ]
position = i
while position > = gap and array [ position - gap ] > currentvalue :
array [ position ] = array [ position - gap ]
position = position - gap
array [ position ] = currentvalue
Notes
- ↑ J. Incerpi, R. Sedgewick , “Improved Upper Bounds for Shellsort,” J. Computer and System Sciences 31, 2, 1985.
- ↑ Marcin Ciura Best Increments for the Average Case of Shellsort
Links
- D. Knut . The art of programming. Volume 3. Sort and search, 2nd ed. Ch. 5.2.1. ISBN 5-8459-0082-4
- Animated Shell Sort Algorithm
- Presentation of Shell's sorting algorithm as a dance (video)