 Shell Sort, Bubble Sort, Sorting in generalSeptember 20 2002 at 1:48 PM  Mac (Premier Login iorr5t) 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.
 
 Responses * FYI: Donald Shell is his full name.  stylez on Sep 21, 2002
 Sample Shell Sort program in QB  Solitaire on Sep 24, 2002
 Merge Sort  Solitaire on Feb 10, 2004
 Radix Sort  De Jef on Mar 5, 2004
 Some sorting theory  Ildûrest on Mar 18, 2004
 Sort Demo that came with original QB4.5 disks  Solitaire on Apr 1, 2004
 Sorting by two variables  Mac on Apr 16, 2006
 Simulated numeric sort using "direct addressing"  Moneo on Jun 8, 2006
 Quicksort without recursive calls  Mac on Jul 10, 2006
 Sorting a list of arrays by userselected fields:  Solitaire on Aug 14, 2006
 Extemely Simple and Intuitive Sort  qbguy on Jan 31, 2008


