Perhaps the most crucial property of Shellsort is that the elements remain k-sorted even as the gap diminishes. For instance, if a list was 5-sorted and then 3-sorted, the list is now not only 3-sorted, but both 5- and 3-sorted. If this were not true, the algorithm would undo work that it had done in previous iterations, and would not achieve such a low running time.
Depending on the choice of gap sequence, Shellsort has a proven worst-case running time of O(n2) (using Shell's increments that start with 1/2 the array size and divide by 2 each time), O(n3 / 2) (using Hibbard's increments of 2k − 1), O(n4 / 3) (using Sedgewick's increments of 9(4i) − 9(2i) + 1, or 4i + 1 + 3(2i) + 1), or O(nlog2n), and possibly unproven better running times. The existence of an O(nlogn) worst-case implementation of Shellsort remains an open research question.
The best known sequence is 1, 4, 10, 23, 57, 132, 301, 701. Such a Shell sort is faster than an insertion sort and a heap sort , but if it is faster than a quicksort for small arrays (less than 50 elements), it is slower for bigger arrays. Next gaps can be computed for instance with :
nextgap = round(gap * 2.3)
Shell sort algorithm in c/c++
Shell sort is commonly used in programming languages ; this is an implementation of the algorithm in C / C++ for sorting an array of integers. The increment sequence used in this example code gives an O (n2) worst-case running time.
void shell_sort(int A[], int size)
{
int i, j, increment, temp;
increment = size / 2;
while (increment>0)
{
for (i=increment; i<size; i++)
{
j = i;
temp = A[i];
while ((j>= increment)&&(A[j-increment]>temp))
{
A[j] = A[j - increment];
j = j - increment;
}
A[j] = temp;
}
if (increment == 2)
increment = 1;
else
increment = (int) (increment / 2.2);
}
}
Shell sort algorithm in java
The Java implementation of Shell sort is as follows:
public static void shellSort(int[] a) {
for ( int increment = a.length / 2;
increment>0;
increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
for (int i = increment; i<a.length; i++) {
for (int j = i; j>= increment&&a[j - increment]>a[j]; j -= increment) {
int temp = a[j];
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}
Shell sort algorithm in python
Here it is:
def shellsort(a):
def new_increment(a):
i = int(len(a) / 2)
yield i
while i != 1:
if i == 2:
i = 1
else:
i = int(numpy.round(i/2.2))
yield i
for increment in new_increment(a):
for i in xrange(increment, len(a)):
for j in xrange(i, increment-1, -increment):
if a[j - increment]<a[j]:
break
temp = a[j];
a[j] = a[j - increment]
a[j - increment] = temp
return a
6.2.2. heap sort
(From Wikipedia, the free encyclopedia)
Heapsort is a comparison-based sorting algorithm , and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort , it has the advantage of a worst-case O (n log n) runtime. Heapsort is an in-place algorithm , but is not a stable sort .
Overview
Heapsort inserts the input list elements into a heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.