Seven Bubble sort for you: which do you choose?

[TempodiBasic]

Hi QB64 Community

I have heard in the air a spealing that said "Bubble sort!"
It let me remember a old fashioned book of programming in Pascal. An just then this the "bubble gum".
So while I go to Psychoanalyst to set up better my mind here a Demonstration of different ways to build up a Bubble Sort routine...
in sum their are seven different routines... the first is the classical version, then it follows the last_index decreasing, the last_index swaped, the split & compact with different dimensions for splitting and one of the two index optimized manners...
run and choose you preferred BUBBLE SORT algorithm...
here I show the result got running the following code




and here the code:

Code: (Select All)

Const max = 32767
Randomize Timer

Type DATATYPE
    a As Integer
    b As Integer
    c As Integer
End Type

ReDim SortedList(1 To max) As DATATYPE, t(1 To max) As DATATYPE

'The sort will only be done on the value of 'a' (SortedList().a) and the values can range from 1 to 32767.
init SortedList() ' this is the original array created at random
initT SortedList(), t() ' this copies the first array into the second array

Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble t()
Print t(1).a, t(max - 1).a, t(max).a
Color 1
Print " Bubble 1 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t() ' so we use the identical array to be ordered
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble2 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 2
Print " Bubble 2 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble3 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 3
Print " Bubble 3 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble4 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 4
Print " Bubble 4 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble5 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 5
Print " Bubble 5 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble6 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 6
Print " Bubble 6 order"
Print (Timer(.001) - t#)
Color 7


End

Sub bubble (a() As DATATYPE)
    ' bubblesort
    ' we compare 2 sequential elements of a set of elements until no swap has been performed
    ' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
    NoSwap = 0
    While NoSwap = 0
        NoSwap = -1
        For count = 1 To max - 1
            If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
        Next count
    Wend
End Sub

Sub bubble2 (a() As DATATYPE)
    ' bubblesort
    ' we compare 2 sequential elements of a set of elements until no swap has been performed
    ' but we ignore the last elements because they has been already ordered
    ' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
    NoSwap = 0
    Fmax = max
    While NoSwap = 0
        NoSwap = -1
        Fmax = Fmax - 1
        For count = 1 To Fmax
            If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
        Next count
    Wend
End Sub

Sub bubble3 (a() As DATATYPE)
    ' bubblesort
    ' we compare 2 sequential elements of a set of elements until no swap has been performed
    ' but we ignore the last elements because they has been already ordered by swap
    ' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
    NoSwap = 0
    Last = max - 1
    While NoSwap = 0
        NoSwap = -1
        For count = 1 To Last
            If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0: Last = count
        Next count
    Wend
End Sub

Sub bubble4 (a() As DATATYPE)
    ' this is multibubble
    ' we split the array if too big into many subarray ordered by bubble sort
    ' using as max bubble dimension to order 3200 item for array
    stepB = UBound(a) / 3200
    For index = 1 To (UBound(a) - stepB) Step stepB

        ' bubble2 type
        NoSwap = 0
        First = index
        Last = index + stepB - 1
        While NoSwap = 0
            NoSwap = -1
            Last = Last - 1
            For count = First To Last
                If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
            Next count
        Wend

    Next
    bubble2 a() ' the last ordering operation
End Sub



Sub bubble5 (a() As DATATYPE)
    ' this is multibubble
    ' we split the array if too big into many subarray ordered by bubble sort
    ' using as max bubble dimension to order 100 item for array
    stepB = UBound(a) / 100
    For index = 1 To (UBound(a) - stepB) Step stepB

        ' bubble3 type
        NoSwap = 0
        First = index
        Last = index + stepB - 1
        While NoSwap = 0
            NoSwap = -1
            For count = First To Last
                If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0: Last = count
            Next count
        Wend

    Next
    bubble3 a() ' the last ordering operation
End Sub





Sub bubble6 (a() As DATATYPE)
    ' this is multibubble
    ' we split the array if too big into many subarray ordered by bubble sort
    ' using as max bubble dimension to order 1000 item for array
    stepB = UBound(a) / 1000
    For index = 1 To (UBound(a) - stepB) Step stepB

        ' bubble3 type
        NoSwap = 0
        First = index
        Last = index + stepB - 1
        While NoSwap = 0
            NoSwap = -1
            For count = First To Last
                If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0: Last = count
            Next count
        Wend

    Next
    bubble3 a() ' the last ordering operation
End Sub

Sub initT (b() As DATATYPE, a() As DATATYPE)
    For count = 1 To max
        a(count).a = b(count).a
    Next count
End Sub

Sub init (a() As DATATYPE)
    For count = 1 To max
        a(count).a = (Rnd * max - 1) + 1
    Next count
End Sub

Sub ShowArray (A() As DATATYPE)
    For count = 1 To max
        Print A(count).a
    Next count
End Sub

Thanks to make your choice!

[mnrvovrfc]

Take eight sorting routines, these seven and the Quicksort in the QB64 Wiki.

See which ones posted here could produce a lower ratio of speed toward the Quicksort. :/

Just rewriting one of these into selection sort would make it much faster, but still significantly slower than Quicksort with millions of elements.

As Herbert Schildt (I think) once said ruthlessly in one of his books, "However, better routines exist."

[mnrvovrfc]

Not trying to make this contribution in this thread less important. Bubble sort used to be one way to teach programming in general, if not BASIC programming. It was the first sort routine I came across, in the Radio Shack TRS-80 Color Computer manual. I was able to remember only the double FOR... NEXT loop and the comparison out of it, and a bunch of ordinary variables juggled around. It was for a program which could have been expanded easily into a full-screen editor, which would have been something on that very slow 8-bit computer. The original purpose of the program was an "inventory list", held by a string array. So it used "INPUT" to ask for the content of each line. That computer's BASIC instruction set didn't have "LINE INPUT" nor "PRINT USING", therefore the program was rather simple although it wouldn't have run on a 4KB computer.

Now I'm not sure where I read the quotation by someone else I offered earlier. I did have "The Art of C" book by Herbert Schildt. The most fascinating chapter was the one about building a BASIC interpreter. It was too limited for some, but I used it as prototype for a vain project of mine, an interpreter that replaced MS-DOS batch-file language. It had custom file listing, graphics with text, ability to get input from user, ability to do simple math and more. As you could probably imagine, this project made better sense before MS-DOS v5. My interpreter's language wasn't much more tolerable. I failed in particular trying to invent a block-IF, wasn't patient enough to scan the interpreted source code to allow nesting and to allow it with a looping construct. I wanted to jump out of any block I wanted, and I also wanted to support subprograms. It became a total mess I was forced to abandon because I hated programming in C much more than in BASIC or Pascal.

[TempodiBasic]

@mnrvovrfc

Just rewriting one of these into selection sort would make it much faster, but still significantly slower than Quicksort with millions of elements.

yeah, Bubble sort is just a turtlesort, also with Turbo  (Turbo the movie) mods it stays a turtle! With the best improvement we get a 25% of increasing of speed (or said with other words : a 25% or reduction of time used to perform the task).

Bubble sort has the bottleneck in the BubbleGum with it has been made. (the two elements neighbors are linked by gum).  :-)

Quicksort with millions of elements

yeah the turbo ferrari!
But the Porsce made by Steve seems to be faster.


About Quicksort I think to do another thread because some times ago I got some interesting information and variation on the theme.
AIHT  (As I Have Time)

[Kernelpanic]

@mnrvovrfc

As Herbert Schildt (I think) once said ruthlessly in one of his books, "However, better routines exist."
. . .
Now I'm not sure where I read the quotation by someone else I offered earlier. I did have "The Art of C" book by Herbert Schildt.

Well hello, someone who knows Schildt. I learned Modula 2 with his books. Then C became my "favorite language", and his "C command library" is still a help to this day when I try something in C.

[bplus]

Except to learn Basic coding you should not waste time on Bubble sort!

As Steve has mentioned already when it comes to sorting on an integer key, you need only iterate through an array once!

Here is my mods of this idea:

Code: (Select All)

_Title "Sort 3 Integer array on first integer" ' b+ 2023-03-12
Dim As Integer MaxI
MaxI = 32767
Dim three(0 To MaxI, 1 To 3) As Integer
ReDim sort(0 To MaxI, 1 To 3) As Integer

'Init array
Randomize Timer
For i = 0 To MaxI
    three(i, 1) = Int(Rnd * (MaxI))
    three(i, 2) = Int(Rnd * (MaxI))
    three(i, 3) = Int(Rnd * (MaxI))
Next

' show first and last 10
For i = 0 To 9
    Print three(i, 1); three(i, 2); three(i, 3); Tab(40); three(MaxI - i, 1); three(MaxI - i, 2); three(MaxI - i, 3)
Next
Print

' begin processing sort
t# = Timer(.001)
sort3Ints three(), sort()
Print "'Sorted' in:"; Timer(.001) - t#; " secs.)"
For i = 0 To 9
    Print sort(i, 1); sort(i, 2); sort(i, 3); Tab(40); sort(MaxI - i, 1); sort(MaxI - i, 2); sort(MaxI - i, 3)
Next

Sub sort3Ints (three() As Integer, sort() As Integer)
    maxI = UBound(three)
    bas = LBound(three)
    Dim tracker$(0 To maxI)
    Dim integ As Integer
    For i = bas To maxI ' store the indexes that have a certain integer value under tracker$(of certain integer value)
        integ = three(i, 1)
        If tracker$(integ) = "" Then
            tracker$(integ) = _Trim$(Str$(i))
        Else
            tracker$(integ) = tracker$(integ) + "," + _Trim$(Str$(i))
        End If
    Next
    'after only 1 interation through array we have all we need to sort on first integer key!!!
    For i = bas To maxI
        If tracker$(i) <> "" Then 'get index and print
            p = InStr(tracker$(i), ",")
            start = 1
            While p
                index = Val(Mid$(tracker$(i), start, p - start))
                sort(sortI, 1) = three(index, 1)
                sort(sortI, 2) = three(index, 2)
                sort(sortI, 3) = three(index, 3)
                sortI = sortI + 1
                start = p + 1
                p = InStr(start, tracker$(i), ",")
            Wend
            index = Val(Mid$(tracker$(i), start)) ' last index
            sort(sortI, 1) = three(index, 1)
            sort(sortI, 2) = three(index, 2)
            sort(sortI, 3) = three(index, 3)
            sortI = sortI + 1
        End If
    Next

End Sub

OK maybe I am done with edits? sorry

[SMcNeill]

More important than being able to pick between various sorting routines, is learning *WHY* the various routines work, and the principle behind them.

Bubble sorts are often the easiest to understand, and are the sort that most programmers quickly figure out for themselves.  The thinking process behind it is really very simple -- run a loop with the array from the starting element to the finish element and check for the lowest possible value in that array.  Once found, make certain to move it to the start of the array, and then continue on until you run out of elements.

1, 3, 5, 2, 4   <-- let's say this is the array.   To bubble sort, we'd start at the 1 and read each element until the end, and we'd find the lowest value.  (1).  We'd then move it to the start of the array.

(1), 3, 5, 2, 4 <-- then we repeat this process.  Start at the 2nd element (3) and go all the way to the end of the array and look for the lowest value.  (2).  Move that to the 2nd element position.

(1, 2) , 5, 3, 4 <-- repeat the process as above until we're finished.

(1, 2, 3), 5, 4

(1, 2, 3, 4), 5

(1, 2, 3, 4, 5)

And that's basically a bubble sort in action.  As you can see (or visualize perhaps), it's not very efficient.  Each time you get the lowest value, you have to search the whole dataset from start to finish, resulting in a ton of comparisons and swaps going on with your data.  It works, but it doesn't work very efficiently.

**********

The next type of sort which most people will learn to implement is a QuickSort routine.  They tend to jump to it because it's just sooo much faster than a bubble sort, and once they realize a bubble sort has very limited uses, they want to jump to something quick and efficient which they can use anytime they want.

Let's take the same dataset of (1, 3, 5, 2, 4) and run it through a quicksort.  

First, find a *pivot point* -- that's going to be the dividing point where you split the sort.  1 is the lowest value.  5 is the highest.  1 + 5 = 6...  Half of 6 is 3, so we'll make 3 the initial pivot point.

Anything 3 or lower gets put into one array.  Anything higher than 3 goes into a different array.

(1, 3, 2)     ---   (5, 4)

Now, repeat that process with each of those half arrays.  ! + 3 = 4... 2 is the pivot point on the left, 5 + 4 = 9.... 4.5 is the pivot point on the right.

(1, 2) --- (3)  ---- (4) --- (5)

Repeat that process with any array which still has over 2 elements in it..   1 + 2 = 3...  1.5 is the pivot point.

(1) ---- (2) --- (3) ---- (4) ---- (5)

Now just assemble those pieces back to make the final sorted array.

(1, 2, 3, 4, 5)

That's the process behind a Quicksort, in a nutshell.

********************************************

If anyone has any questions about any of the other sorting methods, feel free to ask them and I'll answer if I know them.  There's a zillion sorting methods out there, and I've learned maybe a dozen or so of the most commonly used ones.  For me, I think the importance should be more on understanding the CONCEPT behind the routines, rather than to just know the routine themselves.  Anyone can copy/paste code into a program.  It's only when we understand WHAT we've copy/pasted that we can actually say we've learnt and grown as programmers.

[Kernelpanic]

More important than being able to pick between various sorting routines, is learning *WHY* the various routines work, and the principle behind them.

That is the crucial point!
Faster sorting is done using the index of records. It works similar to sorting via pointers as in C. But I would have to deal with that first.

[SMcNeill]

More important than being able to pick between various sorting routines, is learning *WHY* the various routines work, and the principle behind them.

That is the crucial point!
Faster sorting is done using the index of records. It works similar to sorting via pointers as in C. But I would have to deal with that first.

That's one big issue when dealing with sorting -- blanket statements such as the above aren't always true.  Sorting via index may -- or may not -- be faster than sorting the actual data.  Without a valid dataset to compare such a statement against, any blanket speed performance statement has to be suspect for validity. 

For example, let's say my data is just 10 integer values.   (1, 3, 5, 2, 4, 8, 9, 7, 0, 6)   Now, is it going to be faster to shuffle those 2-byte integer values around in memory, or would it be faster to shuffle a 2-byte index which points to those values?

Not surprisingly, it'd be faster to move the data itself Array(X) instead of the referencing array (Array(Index(X)).  Both are moving integer data about in memory, but where the first directly addresses that integer data, the second has to address an set of pointers first, to see what the data is, and then move the integer pointers to the proper place.

************************

Where indexing is done is in cases where:

1) It's vital that the data remains static and unmoving.

OR

2) It's faster to move the reference pointer than it is to move the actual data itself around in memory.  (Which is something you often see with user defined types or larger strings in memory.)

But, indexes aren't the end-all be-all answer for speed for sorting purposes.  In *many* cases, they're faster than any other method, but not in *all* situations.  You really need a working data set to find the best solution to what works best and fastest for it.

---

For an example of a very limited case sort which is generally going to outperform everything under the sun, take a look at a Binary Insertion Sort with previously sorted data.

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)   <-- -Sorted Data.  You want to add 3.5 to that data as a new element.
Then you check the data from the midpoint of each extreme, narrowing in on where it goes by halves:
1 to 10... midpoint 5  <-- goes left of that 5.
1 to 4... midpoint 2 >-- goes right of that 2.
3 to 4... midpoint 3 >-- goes right of that 3.

3 passes and you now know that the data goes after the 3.   In one move, you _MEMCOPY the first three elements of the array, add the new element, and then _MEMCOPY the rest of the array.

(1, 2, 3) +  (3.5) + (4, 5, 6, 7, 8, 9, 10) = (1, 2, 3, 3.5, 4, 5, 6, 7, 8, 9, 10)

You're not going to get any faster than that, in most cases.  (Unfortunately, it's a very limited use case which depends on the data basically being sorted to begin with and which you're only interested in adding new data to the existing data set.)

Without actual data to work with, it's impossible to say which sorting method is going to be the best or the fastest.  It's the reason why there's so many different methods out in the wild world of programming -- it's always an ease of implementation verses a need for performance with any given set of data. 

[bplus]

Code: (Select All)

_Title "Only 1 pass to sort this out!"
d$ = "1,3,5,2,4,8,9,7,0,6,2,4,8,9,7,0,6,1,3,5,2,8,9,7,0,6,2"
Dim tracker(9) As Integer

p = InStr(d$, ",")
start = 1
While p
    index = Val(Mid$(d$, start, p - start))
    tracker(index) = tracker(index) + 1
    start = p + 1
    p = InStr(start, d$, ",")
Wend
index = Val(Mid$(d$, start)) ' last index

Print "sorted:"
For i = 0 To 9
    If tracker(i) Then
        For j = 1 To tracker(i)
            Print i;
        Next
    End If
Next