Shell sorting

SHELL SORTSHELL SORT
Generalization ofGeneralization of
insertioninsertion

Introduction
Shell sort is one of the oldest sorting
algorithm devised by Donald Shell in
1959.
Shell sort is also called the
diminishing increment sort.
The shell sort was introduced to
improve the efficiency of simple
insertion sort .Group 4 02/07/18 05:22 AM

In insertion sort, we move elements only
one position ahead. When an element has
to be moved far ahead, many movements
are involved.
The shell sort improved the insertion sort
by comparing elements far apart, then
elements less far apart and finally
comparing adjacent elements.
The shell sort algorithm avoids large shifts
as in the case of insertion sort, if the
smaller values is to the far right and has to
be moved to the far left.
Group 4 02/07/18 05:22 AM

The shell sort improved insertion sort by
breaking the original list into a number of
smaller sublist, each of which is sorted
using an insertion sort.
The unique way these sublists are chosen is
through the key to the shell sort.
Instead of breaking the list into sublists of
contiguous items, the shell sort uses an
incremental i, sometimes called the gap or
interval to create a sublist by choosing all
items that i items apart.
Group 4 02/07/18 05:22 AM

The idea of shell Sort is to allow exchange
of far items
Group 4 02/07/18 05:22 AM

key terms
Gap or interval: the spacing between elements
or the distance between items being
sorted. As we progress, the gap decreases
and that is why Shell Sort is also called
Diminishing Gap Sort.
Swap: exchanging one thing for another.
(interchange, exchange, switch). When an
element is swapped, the move the position of
the swapped item.
Sort: the arrangement of data in a prescribed
sequence.
Group 4 02/07/18 05:22 AM

Integer (INT): a whole number; a number
that is not a fraction.
Sub-list: a list gotten from a larger list. For
instance, in sets a sub-set is gotten from the
universal set.
Shuttle sort: A sorting method based on
swaps of pairs of numbers. Swapping may be
done or no swapping may be required. The
sort works from left to right, reconsidering
earlier pairs when a swap is made.
Group 4 02/07/18 05:22 AM

How Shell Sort Works
steps
Group 4 02/07/18 05:22 AM

There are many ways of choosing the
next gap.
In any item, objects are compared with less
than (<), equal (=) or greater then (>) in
cases where strings may be applied.
Group 4 02/07/18 05:22 AM

1. Count the number of elements in
a given array. E.g an array
containing
35, 33,42,10,14,19,27,44
This array has how many
elements?
Ans: 8Group 4 02/07/18 05:22 AM

We make a virtual sub-list of all values
located at the interval of 4 position.
The values for the 4 sub-list for the first
gap.
{35, 14}, {33, 19}, {42, 27} and {10, 44}
How comes
Group 4 02/07/18 05:22 AM

{35, 14}if 35>14 then we
swap in there position
otherwise is left.
Next {33, 19} if 33>19 then
swap to their position.
Next {42, 27} if 42>27 then
swap.
Next {10, 44} if 10> 44 swap
otherwise remain in the same
position.
We compare values in each
sub-list and swap them (if
necessary) in the original
array.
The new
array after
pass 1: Group 402/07/18 05:22 AM

Example 1
Consider the following element in an array
A: 54,26,93,17,77,31,44,55,20
Using shell sort, let us sort the array using
gap of 3.
Sub-list 1{54,17,44)
Sub-list 2 {26,77,55)
Sub-list 3 {93,31,20)
Then compare the sub-lists and swap
We shall have
02/07/18 05:22 AMGroup 4

Example 2
Consider the following unsorted
array A with elements
80, 93, 60, 12, 42, 30, 68, 85, 10
Sort using the Shell sort.
Group 4 02/07/18 05:22 AM

No of comparison: 6
No of swaps: 4
Group 402/07/18 05:22 AM

Example 3
Consider an array T with
the following elements
8, 2, 5, 4, 7, 1, 3, 6,
Sort using Shell sort.
Group 4 02/07/18 05:22 AM

Total numbers of element 8. InitiallyGap = 4
Number of comparison: 4
Number of swap: 3
Group 402/07/18 05:22 AM

3 1 5 2 8 67 4
7 1 3 54 68 2
Group 402/07/18 05:22 AM

Example 4
sorting elements that are far apart
Consider an array with elements
40, 2, 1, 43, 3, 65, 0, -1, 58, 3,42, 4
Using initial gap as 5
Group 4 02/07/18 05:22 AM

40
2 1 43 3 65 0 -1 58 3 42 4
40 0 -1 43 3 42 2 1 58 3 65 4
2 0 -1 3 1 4 40 3 42 43 65 58
-1
0 1 2 3 3 4 40 42 43 58 65
Original:
After 5-sort:
After 3-sort:
After 1-sort:
Group 402/07/18 05:22 AM

Before and after sorting with gap = 7
Before and after sorting with gap = 3
Example 5
Group 402/07/18 05:22 AM

Class work
Q1.
Given the following list of numbers:
[5, 16, 20, 12, 3, 8, 9, 17, 19, 7]
Which answer illustrates the contents
of the list after all swapping is
complete for a gap size of 3?
02/07/18 05:22 AM

02/07/18 05:22 AMGroup 4
(A) [5, 3, 8, 7, 16, 19, 9, 17, 20, 12]
• (Correct! Each group of numbers represented by index
positions 3 apart are sorted correctly)
(B) [3, 7, 5, 8, 9, 12, 19, 16, 20, 17]
• (Incorrect. This solution is for a gap size of two.)
(C) [3, 5, 7, 8, 9, 12, 16, 17, 19, 20]
• (Incorrect. This is list completely sorted, you have gone
too far.)
(D) [5, 16, 20, 3, 8, 12, 9, 17, 20, 7]
(Incorrect. The gap size of three indicates that the group
represented by every third number e.g. 0, 3, 6, 9 and 1, 4, 7
and 2, 5, 8 are sorted not groups of 3.)

Best case
The best case is when the array is already
sorted in the right order.
The number of comparisons is almost zero and
swapping.
Average case
Less comparison and swamping
Worst case
More comparison and swapping
Group 4 02/07/18 05:22 AM

Advantages
1. Shell sort is easy to implement but not
easier than insertion sort.
2. Shell sort can be sorted for a gap greater
than one and thus less exchange than
insertion sort hence, fast.
3. Efficient for medium size lists.
4. It is easy to understand.
5. It is easy to implement.
Group 4 02/07/18 05:22 AM

Disadvantages
1. It is a complex algorithm and its not nearly
as efficient as the merge, heap and quick
sorts.
2.
Group 4 02/07/18 05:22 AM

Algorithm
The difference between insertion sort from
the shell sort are
– There is one additional loop (the outer loop)-
each run processes one increment.
– The middle and the most inner loops are same
as in the insertion sort with gap = 1.
Group 4 02/07/18 05:22 AM

Group 4
Let A be a linear array of n elements, A [1], A [2], A
[3], ...... A[ n ] and Incr be an array of sequence of
span to be incremented in each pass. X is the number
of elements in the array Incr. Span is to store the span
of the array from the array Incr.
1. Input n numbers of an array A
2. Initialise i = 0 and repeat through step 6 if ( i < x )
3. Span = Incr[ i ]
4. Initialise j = span and repeat through step 6 if ( j < n )
( a ) Temp = A[ j ]
5. Initialise k = j-span and repeat through step 5 if ( k > = 0) and
(temp < A [ k ])
( a ) A [ k + span] = A [ k ]
6. A [ k + span] = temp
7. Exit

02/07/18 05:22 AM Group 4
Summary

Shell Sort Algorithm
1. Set gap to n/2
2. while gap > 0
3. for each element from gap to end, by
gap
4. Insert element in its gap-separated sub-
array
5. if gap is 2, set it to 1
6. otherwise set it to gap / 2.2
Group 4 02/07/18 05:22 AM

Shell Sort Algorithm: Inner
Loop
set nextPos to position of element to insert
3.2 set nextVal to value of that element
3.3 while nextPos > gap and
element at nextPos-gap is > nextVal
3.4 Shift element at nextPos-gap to
nextPos
3.5 Decrement nextPos by gap
3.6 Insert nextVal at nextPos
Group 4 02/07/18 05:22 AM

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
# Start with the largest gap and work down to a gap of 1
For each (gap in gaps)
{
# Do a gapped insertion sort for this gap size.
# The first gap elements a[0..gap-1] are already in gapped order
# keep adding one more element until the entire array is gap sorted
for (i = gap; i < n; i += 1)
{
# add a[i] to the elements that have been gap sorted
# save a[i] in temp and make a hole at position i
temp = a[i]
# shift earlier gap-sorted elements up until the correct location for a[i] is found
for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
{
a[j] = a[j - gap]
}
# put temp (the original a[i]) in its correct location
a[j] = temp
}
}
Group 402/07/18 05:22 AM

int j, p, gap;
comparable tmp;
for (gap = N/2; gap > 0; gap = gap/2)
for ( p = gap; p < N ; p++)
{
tmp = a[p];
for (j = p; j >= gap && tmp < a[j- gap]; j = j - gap)
a[j] = a[j-gap];
a[j] = tmp;
}
}
Group 4 02/07/18 05:22 AM

Shell sorting

Recommended

More Related Content

What's hot (20)

Similar to Shell sorting (20)

More from TUC (12)

Recently uploaded (20)

Shell sorting