<< Chapter < Page Chapter >> Page >

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.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Data structures and algorithms. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10765/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?

Ask