0.6 Sorting  (Page 10/20)

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.