QB64 Phoenix Edition
Seven Bubble sort for you: which do you choose? - Printable Version

+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://qb64phoenix.com/forum/forumdisplay.php?fid=3)
+---- Forum: Programs (https://qb64phoenix.com/forum/forumdisplay.php?fid=7)
+---- Thread: Seven Bubble sort for you: which do you choose? (/showthread.php?tid=1540)

Pages: 1 2 3 4


RE: Seven Bubble sort for you: which do you choose? - mnrvovrfc - 03-24-2023

(03-22-2023, 10:23 PM)TempodiBasic Wrote: Hey 
I have forgotten the DANILIN perspective...

I've tried to define "count" AS LONG, in one of these programs presented. Also had to change "c" data type from INTEGER to LONG on two of the subprograms. Then set "max" to a hundred thousand. I got a "segmentation fault" from Linux (Spiral KDE based on Debian "Bullseye"). It's because of the recursion. I only have 4GB RAM. Maybe it could work with 32767 elements on a computer with 64GB RAM.


RE: Seven Bubble sort for you: which do you choose? - DANILIN - 03-24-2023

Optimize minimax Select sort from message
https://qb64phoenix.com/forum/showthread.php?tid=1540&pid=14693#pid14693
I have sorts 5000 in 0.22 seconds
I have sorts 32767 in 7 seconds

Bubble sort from message
https://qb64phoenix.com/forum/showthread.php?tid=1540&pid=14341#pid14341
I have sorts 5000 in 0. 6 seconds
I have sorts 32767 in 22 seconds

But I can theoretically speed up bubble sort by another 2...4 times
dividing array into 4...8 parts
and there will still be a buble sorting


RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-26-2023

(03-24-2023, 08:24 AM)david_uwi Wrote: For small data sets (<5000) I always use select sort.
It is easy to code.
It always works.
It always takes the same amount of time.
For larger data set some there are much better routines, but I don't understand how they work - some kind of splitting and pivoting -magic in other words.
Code: (Select All)
DefInt A-S
kdim = 32767
Dim x(kdim)
For i = 1 To kdim
    x(i) = Rnd * 1000
    Print x(i),
Next i
Print
tt = Timer
For j = 1 To kdim \ 2
    jmax = j: xmax = x(j)
    jmin = kdim - j + 1: xmin = x(kdim - j + 1)
    For i = j + 1 To kdim - j + 1
        If x(i) > xmax Then jmax = i: xmax = x(i)
        If x(i) < xmin Then jmin = i: xmin = x(i)
    Next i
    Swap x(j), x(jmax)
    Swap x(kdim - j + 1), x(jmin)
Next j
Print Timer - tt
Input sa$
For i = 1 To kdim
    Print x(i),
Next i
Print

Hi David
thanks to remember me the select sort method.
I think to make a thread about it, and I'll post the link to this your message here in bubble sort land.
Based on my memory this your code shows an optmized algorithm of select sort because I remember a code that runs across the whole array and not only to the first half array.

Here the results after running your code

[Image: immagine-2023-03-26-174154854.png]


As I can observe it performs a discendent/decreasing ordering of the array.
Moreover value are type Single!  But it is better so because forcing to be Integer% we get so many duplicates!