Good Old Shellsort

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Good Old Shellsort

Post by Munair »

While it might look as simple as 1+1=2, sorting routines found on the internet are not always correct. Take shellsort for example, a sorting algorithm which on average is among the best and also simplest. What we see very often at the beginning is something like this:

Code: Select all

max = upperbound \ 2
while max > 0
...
Suppose you have an array with two elements (0..1). The division upperbound \ 2 returns 0 so the next statement while max > 0 prevents those two elements from being sorted. It's very simple, yet we see this A LOT and the error doesn't surface as long as we do test runs with many elements.

So I went back to an old QuickBASIC book to see how a correct Shellsort looks like (I used it a lot in those days):

Code: Select all

sub Shellsort(arr())
n1 = lbound(arr)
n2 = ubound(arr)

max = n2 - n1 + 1

while max > 1
  max = max \ 2
  do
    nswap = false
    for i = n1 to n2 - max
      j = i + max
      if arr(i) > arr(j) then
        swap arr(i), arr(j)
        nswap = true
      end if
    next
  loop while nswap
wend

end sub
Very simple and very effective. I also ported this code successfully to a Pascal project. Whenever I need to sort a list or array and the type or object doesn't provide one, I implement this Shellsort. No need to go through the hazzle of creating a universal one. ;)
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: Good Old Shellsort

Post by dafhi »

inspired by this thread

Code: Select all

const           w = 640
const           h = 480

sub Bar(a() as single, x as long, alpha as ubyte = 255)
  line ( x, 0 ) - ( x, int( a(x)*h ) ), rgb(alpha, a(x)*alpha, 0)
End Sub

sub show_lines(a() as single, i as long, j as long, alpha as ubyte = 255)
  bar a(), i, alpha
  bar a(), j, alpha
End Sub

sub rand_vals(a() as single, quant as long = 0)
  if quant < 1 then quant = 5*h
  for i as long = 0 to ubound(a)
    a(i) = int(rnd*(quant+1))/quant
  Next
 
  '' display values
  cls
  for x as long = 0 to ubound(a)
    bar a(), x
  Next
End Sub

sub Shellsort(arr() as single)
 
  var n1 = lbound(arr)
  var n2 = ubound(arr)
  var max = n2 - n1 + 1
  var nswap = false
 
  do
    max = max \ 2
    do
      nswap = false
      for i as long = n1 to n2 - max
        var j = i + max
        if arr(i) > arr(j) then
          show_lines arr(), i, j, 0
          swap arr(i), arr(j)
          show_lines arr(), i, j
          nswap = true
          sleep 5,1
        end if
        if inkey<>"" then exit sub
      next
    loop while nswap
  loop until max = 1

end sub

screenres w,h,32

dim as single   a(w - 1)

var quant = 16

rand_vals a(), quant
shellsort a()

sleep
Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Re: Good Old Shellsort

Post by Munair »

A bit more optimized main loop (in case there is only one element):

Code: Select all

while max > 1
  ...
wend
or

Code: Select all

do while max > 1
  ...
loop
I remember a benchmark between several sorting algorithms. Bubblesort could be very fast, but also be very slow depending on the amount of sorting that needs to be done. Quitcksort same thing, although much better. On average Shellsort seemed to be the best. I will try to find that benchmark so I can post it here.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Good Old Shellsort

Post by jj2007 »

Munair wrote:I remember a benchmark between several sorting algorithms.
I posted a link in the Visual Sorts thread. Fascinating stuff, they sort terabytes in a minute... and merge sort is the winner!
Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Re: Good Old Shellsort

Post by Munair »

jj2007 wrote:
Munair wrote:I remember a benchmark between several sorting algorithms.
I posted a link in the Visual Sorts thread. Fascinating stuff, they sort terabytes in a minute... and merge sort is the winner!
Thanks.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: Good Old Shellsort

Post by dafhi »

Last edited by dafhi on Dec 02, 2017 20:36, edited 5 times in total.
Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Re: Good Old Shellsort

Post by Munair »

@dafhi: it looks like the quicksort skipped a few numbers.
Post Reply