Visualization of Sorting Methods
Author Message
Visualization of Sorting Methods

This view from 60,000 feet of some sorting methods was previously
posted as a response to a query. I have been asked to do the same for
the Shell and Heap sorts. From just the rudimentary descriptions of
all the sorts below (except the QuickSort and Heapsort) you can
probably design implementations of these algorithms.

I feel sure there are better descriptions in books and net tutorials
but here is the way I visualize them:

(1) Bubble--Scan the list continually, finding items out of sequence
and swapping places with adjacent items until no swaps are made. This
gives the appearance of bubbles rising to the top surface.

(2) Selection--Search through the list to find the lowest (or highest)
and move it to the top. Reduce the list size by one and find the next
lowest, etc.

(3) Insertion--like picking up playing cards one at a time and placing
them in your hand in the order of a bridge hand.

(4) QuickSort--I'm sure there are examples of this on the net which
explain it better. This sort, credited to C.A.R. Hoare (1962), is a
"divide and conquer" technique where a random pivot value is chosen
and values are placed on both sides of this pivot. The procedure
continually calls itself in a recursive manner while making the sorted
segments smaller and smaller.

(5) Shell--(Donald L. Shell, 1959) This is a declining interval sort.
Shell's first proposal used 8-4-2-1 as the intervals for comparison.
The whole array is scanned first for items separated by 8 places and
exchanges them if out of order. This is repeated until no item is
moved. The interval is then reduced to 4 and so on to 2 and 1. An
interval of 1 between compared items is exactly like a bubble sort,
but many fewer items are moved.

More modern implementations realize that many items need to be moved
farther than 8 places in the first pass. The first interval is
conventionally 1/2 way down the array, reduced to 1/4..1/8.. until
finally an interval of 1. Less well known modifications of this sort
make only one pass per interval to get all the items at that interval
in their proper place. No implementation is recursive. The latter
modification competes with the QuickSort in speed.

(6) HeapSort (TreeSort3)--The novel, clever concept in this approach
is realizing the geometry of a tree with a linear array. This is
achieved in the following manner:

A[4]
/
A[2]
/      \
/         A[5]
A[1]                       and so on
\         A[6]
\      /
A[3]
\
A[7]

The parent of A[2] and A[3] is A[1]. A[2] has the children "nodes" of
A[4] and A[5]. All children nodes are ordered in the same geometric
fashion by their values, i.e. A[3] < A[2], A[5] < A[4] ... would be
one way of ordering. Note that if the parent is A[i], the children are
A[2*i] and A[2*i + 1].

This works like a selection sort but all the remaining items need not
be searched each time, rather just traverse the heap (tree) taking the
branch depending on the value being placed. The algorithm that
performs this is frequently called a sift.

After the heap is formed, it is rearranged with the smallest (or
largest) on top at the root, A[1], the next smallest at A[2] and so
on. In the end, A[1]..A[7]  are in sorted order.

This is a very rapid sort. At 300Mhz, 17,000 random integers (0..9999)
are sorted before your finger gets of the <Enter> key.

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods

Quote:

>(3) Insertion--like picking up playing cards one at a time and placing
>them in your hand in the order of a bridge hand.
...

>(5) Shell--(Donald L. Shell, 1959) This is a declining interval sort.
>Shell's first proposal used 8-4-2-1 as the intervals for comparison.
>The whole array is scanned first for items separated by 8 places and
>exchanges them if out of order. This is repeated until no item is
>moved. The interval is then reduced to 4 and so on to 2 and 1. An
>interval of 1 between compared items is exactly like a bubble sort,
>but many fewer items are moved.

Each separate phase in Shellsort is basically and insertion sort. The
last step when gap is 1 is identical to insertion on sort.

Quote:
>More modern implementations realize that many items need to be moved
>farther than 8 places in the first pass. The first interval is
>conventionally 1/2 way down the array, reduced to 1/4..1/8.. until
>finally an interval of 1. Less well known modifications of this sort
>make only one pass per interval to get all the items at that interval
>in their proper place. No implementation is recursive. The latter
>modification competes with the QuickSort in speed.

It is better not use divide by two. It is more effective if one divides
the gap by 1.7. (gap:=longint(gap)*10 div 17)

Osmo

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods

airnews.net> of Mon, 22 May 2000 21:35:15 seen in

Quote:
>(1) Bubble--Scan the list continually, finding items out of sequence
>and swapping places with adjacent items until no swaps are made. This
>gives the appearance of bubbles rising to the top surface.

How would it be if scans were alternately up and down?  That way, ISTM
that an item slightly out of position in an otherwise sorted array would
be corrected within the first two passes, and the worst case would be no
worse than before.

An explicit mention of Merge Sort might be in order?

--

Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Proper 4-line sig. separator is as above, a line exactly "-- " (SonOfRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods
Hi,

Quote:

>>(1) Bubble--Scan the list continually, finding items out of sequence
>>and swapping places with adjacent items until no swaps are made. This
>>gives the appearance of bubbles rising to the top surface.

> How would it be if scans were alternately up and down?  That way, ISTM
> that an item slightly out of position in an otherwise sorted array would
> be corrected within the first two passes, and the worst case would be no
> worse than before.

Well, *technically* this is not Bubblesort but Shakersort (I think the
analogy should be obvious). IIRC the benefit is rather marginal.

Quote:
> An explicit mention of Merge Sort might be in order?

Since Mergesort has a number of useful applications, I think so. Also,
aside of Heapsort, Mergesort is the only one in the collection with
n*ld(n) complexity. A simple explanation could be: "Divide the table
into two parts and sort each one. Merge the two sorted tables so that
the resulting table is sorted. The merging can be done in linear time
because every item has to be inspected only once. The sorting is
recursive and terminates when only one element has to be sorted."

IMHO, Bucketsort could also be mentioned: "The sorting key has a
cardinality of x. Prepare x 'buckets'. Iterate the table, putting each
item in its respective bucket. After you are done, collect the items
from the buckets in the correct order and reinsert them into the
additional space, dependant on the sorting key.

What about Combsort? ISTR that this was some kind of variation of
Bubblesort, but I can't find any documentation right now.

- Sebastian

--
Add "NOSPAM" to my email to send me junk!

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods

Quote:

>airnews.net> of Mon, 22 May 2000 21:35:15 seen in

>>(1) Bubble--Scan the list continually, finding items out of sequence
>>and swapping places with adjacent items until no swaps are made. This
>>gives the appearance of bubbles rising to the top surface.

>How would it be if scans were alternately up and down?  That way, ISTM
>that an item slightly out of position in an otherwise sorted array would
>be corrected within the first two passes, and the worst case would be no
>worse than before.

A pile of cow dung will not become any tastier no matter how much
pepper you put on it.

Osmo

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods

Quote:

>>(3) Insertion--like picking up playing cards one at a time and placing
>>them in your hand in the order of a bridge hand.
>...

>>(5) Shell--(Donald L. Shell, 1959) This is a declining interval sort.
>>Shell's first proposal used 8-4-2-1 as the intervals for comparison.
>>The whole array is scanned first for items separated by 8 places and
>>exchanges them if out of order. This is repeated until no item is
>>moved. The interval is then reduced to 4 and so on to 2 and 1. An
>>interval of 1 between compared items is exactly like a bubble sort,
>>but many fewer items are moved.

>Each separate phase in Shellsort is basically and insertion sort. The
>last step when gap is 1 is identical to insertion on sort.

>>More modern implementations realize that many items need to be moved
>>farther than 8 places in the first pass. The first interval is
>>conventionally 1/2 way down the array, reduced to 1/4..1/8.. until
>>finally an interval of 1. Less well known modifications of this sort
>>make only one pass per interval to get all the items at that interval
>>in their proper place. No implementation is recursive. The latter
>>modification competes with the QuickSort in speed.

>It is better not use divide by two. It is more effective if one divides
>the gap by 1.7. (gap:=longint(gap)*10 div 17)

>Osmo

As I mentioned, there are modern variations of which this is a minor
one. The more important variant is the modification that makes only
one pass per interval. That runs approximately 3x faster.

Call it what you want. When you are swapping items in an array it is
not an insertion sort in my book, even though it is in some books.

A GAP OF 1 IS EXACTLY WHAT A BUBBLE SORT IS. GET OFF MY CASE. I
RESPONDED TO THE REQUESTS I RECEIVED, NOT INTENDING A COMPLETE
TREATISE ON ANY OR EVERY SORT. JUDGING FROM THE COMPLIMENTS RECEIVED
VIA EMAIL, I SATISFIED SOME PEOPLE WITH THIS LOW BROW OVERVIEW.

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods
On Tue 23 May 2000 11:16:08a,  In article

Quote:

>It is better not use divide by two. It is more effective if one divides
>the gap by 1.7.

Shouldn't that be 1.61803398874989?

Wed, 18 Jun 1902 08:00:00 GMT
Visualization of Sorting Methods

Quote:

>Call it what you want. When you are swapping items in an array it is
>not an insertion sort in my book, even though it is in some books.

You are confusing algorithm and implementation. One sure can implement
insertion sort by using swapping. In this way the insertion sort at
first glance resembles bubble sort but that is only superficial
similarity based on the fact that both compare items next to each other.

The difference is that in bubble soft the inner loop runs through the
unsorted part of the array while in insertion sort it runs through the
sorted part. Also in insertion sort the inner loop terminates when a
first case of items in right order is found (this is just because it
runs through the sorted part). In Bubble sort there is no similar quick
termination in the inner loop. One may add a quick termination in the
outer loop though. This would be used when the inner loop did no swaps.

Quote:

>A GAP OF 1 IS EXACTLY WHAT A BUBBLE SORT IS. GET OFF MY CASE. I
>RESPONDED TO THE REQUESTS I RECEIVED, NOT INTENDING A COMPLETE
>TREATISE ON ANY OR EVERY SORT. JUDGING FROM THE COMPLIMENTS RECEIVED
>VIA EMAIL, I SATISFIED SOME PEOPLE WITH THIS LOW BROW OVERVIEW.

Shouting does not make your statement any more convincing.

Did you somehow think that my messages were some kind of personal attack
against you?

Omso

Wed, 18 Jun 1902 08:00:00 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages