BlitzCoder Code Database

BlitzCoder Essentials

•Home Page
•About BlitzCoder
•Contributors
•Terms of Use
•Email Us

Main Areas

•BlitzCoder Chat
•Discussions
•Articles/Tutorials
•Code Database
•Link Database
•Showcase Area
•Worklogs
•Competitions

Special Areas

•Undocumented

Other Blitz Sites

•Blitz Basic Home
•Blitz Showcase
•BlitzPlay Library

BlitzCoder Code Archives Page

Main Codes Page

"Quicksort Algorithm Demo", by kawaguy

This demo is to implement fast Quicksort Algorithm.

Use a keyed structure (type) for records to be sorted. In this example, random numbers are used for the demo purpose.

For 10,000 records, sorting takes approx. 6/10 of a second on my machine as compared to Bubblesort, approx. 4 secs. If you do the timing yourself, be sure to comment out DebugLog commands.

Code

; Quicksort Algorithm Demo
; Based on Algorithms + Data Structures = Programs by Nicklaus Wirth, 1976
; Adopted for BlitzBASIC by Geo Massar (aka KawaGuy)

; Version 5 - sorting items via an array of pointers with key$ 
; 17 Sep 2003

Const N = 99

Type item
    Field key$
    Field value
    ; Field some other stuff
End Type

Dim a.item(N)  ; has to be outside of functions

Function Quicksort()
    ; copy items to an array
    q.item = First item
    For i = 1 To N
        a(i) = q
        q = After q
    Next
    
    ; sort away :)
    Sort(1, N)
    
    ; append new items from sorted array
    For i = 1 To N
        q = New item
        q\key = a(i)\key
        q\value = a(i)\value
        ; more stuff (be sure to copy everything)
    Next
    
    ; remove old items
    For i = 1 To N
        q = First item
        Delete q
    Next
End Function

Function Sort(l, r)
    i = l : j = r
    x.item = a((l+r)/2)
    Repeat
        While a(i)\key < x\key
            i = i + 1
        Wend
        While x\key < a(j)\key
            j = j - 1
        Wend
        If i <= j Then 
            w.item = a(i) : a(i) = a(j) : a(j) = w ; swap pointers
            i = i + 1 : j = j - 1
        End If
    Until i > j
    If l < j Then Sort(l, j) ; recursive calls!
    If i < r Then Sort(i, r)
End Function

; ------------
; Main program
; ------------

DebugLog "Before sorting..."

; Create a queue of items with random numbers
For i = 1 To N
    queue.item = New item
    queue\value = Rand(1000)
    ; more stuff here
    queue\key = RSet(Str(queue\value), 4) ; right-justified
    DebugLog queue\value
Next

DebugLog ""
DebugLog "After sorting ..."

Quicksort

; Show the result on Debug Log page (press F9 key)
For queue.item = Each item
    DebugLog queue\value
Next

End

Code software created by Krylar's Kreations