QB / QB64 Discussion Forum      Other Subforums, Links and Downloads
 

 Return to Index  

Shell Sort, Bubble Sort, Sorting in general

September 20 2002 at 1:48 PM
  (Premier Login iorr5t)
Forum Owner

 
To explain what the Shell sort is, it is useful to first explain what the QBasic Forum sort is and why it is the only one we tend to use. The short answer is that the QBasic Forum sort is good enough for our work and is simple to code.

I am calling our sort "the QBasic Forum sort" rather than the name we usually use, namely "bubble sort". That is because it is not a bubble sort.

Here is why we should use the name "selection sort" instead of "bubble sort":

Definitions taken from http://www.scifaiku.com/tom/programs/sorts.html

Exchange Sort *** The exchange sort is done by comparing every two numbers in the list, and swapping them if the second number is less than the first.
     FOR i = 1 TO sMax
          FOR j = 1 TO sMax
               IF d%(i) > d%(j) THEN SWAP d%(i), d%(j)
          NEXT j
     NEXT i
(This is what is incorrectly referred to on the QBasic forum as an "inefficient bubble sort")

Selection Sort *** A selection sort is a very similar idea to an exchange sort. For a given list, select the smallest element of the list and swap it with the first element of the list. Then do a selection sort on the remaining list.
     FOR i = 1 TO sMax - 1
          FOR j = i TO sMax
               IF d%(i) > d%(j) THEN SWAP d%(i), d%(j)
          NEXT j
     NEXT i
(This is what is incorrectly referred to on the QBasic forum as a "bubble sort".)

Bubble Sort *** A bubble sort makes several passes on the list. On each pass, compare every two adjacent elements. If they're in the wrong order, swap them. Stop when you make a pass and no swaps are made.
     DO
          swapped = 0
          FOR i = 1 TO sMax - 1
               IF d%(i) > d%(i + 1) THEN swapped = 1: SWAP d%(i), d%(i + 1): NEXT i
     LOOP WHILE swapped = 1
(This is a real bubble sort, but don't feel bad if you've been led astray – Many programming sites mix this up with the selection sort.)

So to get back to the point: What is a Shell sort?

Shell Sort *** Here we sort by shells of decreasing size. Say for instance we use the sizes 8,5,3,2,1. First, every list of every 8 elements is sorted, that is, those elements numbered [1,9,17,...], [2,10,18,...], ..., [8,16,24,...]. Then shells of size 5, 3, and 2 are sorted. Finally, the whole list (every 1 element) gets sorted. The elements within each shell are sorted by any given sort algorithm, even a shell sort.

Well, that was the definition given. It leaves much to be desired, but is the closest to a correct definition I found looking around. One problem with this definition is that it talks about "shells of decreasing size", implying that the reason it is called a "Shell sort" is because of these shells. Poppycock! It is called a Shell sort because some programmer named Mr. Shell invented it in 1959. If his name were Otto Larsen, then we would be calling it the Larsen sort.

The second problem with the definition is that it lists the numbers 8,5,3,2,1 as if they are random numbers. They are in fact Fibonacci numbers (in inverse order). For a good Shell sort, you want to start with the biggest Fibonacci number that fits. For a list of 1000, you would use 987, 610, 377, 233, 144, 89, 55, 34, 23, 13, 8, 5, 3, 2.

A review of various sorting methods can be found at
http://www.mvps.org/vbnet/index.html?code/sort/qscompare.htm
It showed that it took 17 seconds to sort some array in VB using the QBasic Forum sort, but zero seconds using Shell sort. This was a peculiar shell sort, though. It seemed to focus on the number "3".

The point is that there are MUCH faster sorting algorithms that the QBasic Forum sort. See
http://linux.wku.edu/~lamonml/algor/sort/sort.html
for a really good treatment of this subject.

But better sorts are complicated to code and we often do not need such speed. I ran a QBasic Forum sort on an array with 1000 entries. It took about 5 seconds. Irritating to be sure, but bearable. And, most of our sorting problems involve much less data. For example, maybe you want to sort your telephone book by telephone number instead of last name. But your telephone book only has 130 entries. So the QBasic Forum sort would take a tenth of a second. It is no wonder that we don't mess around with the coding of complex sorts.

Well, this concludes this general discussion of sorts. Below is a description of the Shell sort for a simple case. Someone is welcome to write a QBasic program to do this kind of sort. I am too lazy.

Mac

Sort this: 9876543210 (This is a list in inverse order to see what is involved)

Applicable Fibonacci series: 8,5,3,2 (Since 13 will not fit)
(The {} below is just to show where the Fibonacci number of elements ends)

Sort {} 98765432 {} 10
Try to follow this: We sort 9 and 1 (The first element and the first+8th element.)
This gives {} 18765432 {} 90
Now we sort 8 and 0. Right?
This gives {} 10765432 {} 98
There is nothing else to sort on this pass as there is no corresponding element for 7, etc.
Final result: 1076543298

Sort {} 10765 {} 43298 {} (Right? 5 is the next Fibonacci number)
{} 10765 {} 43298 {} <== 1 and 4 already in order
{} 10765 {} 43298 {} <== 0 and 3 already in order
{} 10265 {} 43798 {} <== 2 and 7 were out of order and required sorting
{} 10265 {} 43798 {} <== 6 and 9 already in order
{} 10265 {} 43798 {} <== 5 and 8 already in order
Result: 1026543798

Sort {} 102 {} 654{} 379 {} 8
{} 102 {} 354{} 679 {} 8 OK 1,3,6,8 in order
{} 102 {} 354{} 679 {} 8 OK 0,5, and 7 were already in order
{} 102 {} 354{} 679 {} 8 OK So were 2,4,and 9
Result: 1023546798

Sort {} 10 {} 23 {} 54 {} 67 {} 98
{} 10 {} 23 {} 54 {} 67 {} 98 Whoa! 12569 were already in order.
{} 10 {} 23 {} 54 {} 67 {} 98 So were 03478 (We were just lucky)

The final pass is to go through the entire list by pairs and fix any that are out of order.
0123456789

That is how Shell's sort works.

Note that in the next to last pass, we had to sort 12569, a list of 5 elements. If that were a long list, we could use Shell sort to sort that list, too! You can see how the algorithm can get complex.

 
 Respond to this message   
Responses

 Copyright © 1999-2014 Network54. All rights reserved.   Terms of Use   Privacy Statement  

Newbies usually go to www.qbasic.com and click on The QBasic Forum
Forum regulars have their own ways, which include The QBasic Community Forums