Working on sorting algorithms.  I thought I had some of these coded in the
past....   But I guess I'll just rewrite them.

Out of:

Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Merge Sort
Shell Sort
Heap Sort

I got the first 4 coded, and was thinking about timing them.

(Also, the way Quick sort is recursive, it's not straightforward to code and
keep the original unsorted array unmodified - so I think I'll make that a
macro-within-a-macro.)

My idea was to have a "wrapper", where a timing macro would take a sorting macro
as an argument, log the start time, run the macro, log the end time, and then
spit the elapsed time out to the #debug stream.

Here's what I'm doing at 7am, which obviously does NOT work, but it illustrates
the idea with pseudocode / unworkingcode.

#macro Print () #debug "inner macro \n\n" #end

#macro Test (optional Directive)

 Directive

#end

Test (Print())





Do we think there might be a way to bamboozle the parser into letting one macro
run another macro, being passed in as an argument?   ParseString perhaps?

Post a reply to this message

Why not just a case select inside a loop and trigger each macro with the
counter?

"Bald Eagle" <cre### [at] netscapenet> wrote:
> Working on sorting algorithms.  I thought I had some of these coded in the
> past....   But I guess I'll just rewrite them.
>
> Out of:
>
> Bubble Sort
> Selection Sort
> Insertion Sort
> Quick Sort
> Merge Sort
> Shell Sort
> Heap Sort

Post a reply to this message

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> ...
> Here's what I'm doing at 7am, ...

and before the second coffee ?  :-)


> Do we think there might be a way to bamboozle the parser into letting one macro
> run another macro, being passed in as an argument?   ParseString perhaps?

my 'Foreach()' does that, and if your data is in arrays, you might be able to
just use it as is, or just "strip it to the guts" for your own code.


regards, jr.

<https://drive.google.com/file/d/1-uadHHQ3K0sgdxyHmBCTznlPYNrnBgM9/view?usp=sharing>

Post a reply to this message

Yes, 7am, before I even finished FIRST coffee   :O

All good ideas - I like options.

Anyway, I got that all ... sorted  :D

#macro TimeElapsed (Macro)
 #local Start = now*ms;
 Parse_String (Macro)
 #local End = now*ms;
 #local Elapsed = End-Start;

 Elapsed

#end

and now I just put the macro call in quotes, so it's a string.

#declare Speed = TimeElapsed ("#declare BubbleSorted = BubbleSort
(UnsortedArray)");



Merge sort crashed and burned with only 50 numbers, due to "Too many nested
symbol tables" - so I'll have to figure a way around that, or find some better
code to implement for that one.


I'm now on Shell sort, and behold this abomination:
#for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

I'm gonna try to divine the true meaning of that, and hopefully code up a
workable SDL version of that mess ... later.


Here's how everything is working so far:

Unsorted Array
5.627, 76.839, 25.256, 92.322, 57.569, 81.538, 25.734, 93.770, 88.249, 82.370,
7.027, 77.468, 47.888, 57.584, 36.548, 35.987, 88.602, 39.002, 60.983, 7.921,
 91.258, 84.739, 6.044, 76.053, 47.104, 10.234, 89.598, 41.787, 67.629, 94.756,
84.110, 5.537, 21.075, 5.596, 89.346, 7.762, 19.062, 7.116, 1.259, 10.329,
 1.728, 46.853, 88.009, 22.901, 94.856, 35.860, 9.052, 4.031, 37.408, 65.470,



Bubble Sorted Array
1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
 36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
 88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,

Bubble sorting 50 items took 12.00 ms.



Selection Sorted Array
1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
 36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
 88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,

Selection sorting 50 items took 7.00 ms.



Insertion Sorted Array
1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
 36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
 88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,

Insertion sorting 50 items took 9.00 ms.



Quick Sorted Array
1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
 36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
 88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,

Quick sorting 50 items took 4.00 ms.

Post a reply to this message

Le 2023-01-19 à 15:29, Bald Eagle a écrit :
> Yes, 7am, before I even finished FIRST coffee   :O
> 
> All good ideas - I like options.
> 
> Anyway, I got that all ... sorted  :D
> 
> #macro TimeElapsed (Macro)
>   #local Start = now*ms;
>   Parse_String (Macro)
>   #local End = now*ms;
>   #local Elapsed = End-Start;
> 
>   Elapsed
> 
> #end
> 
> and now I just put the macro call in quotes, so it's a string.
> 
> #declare Speed = TimeElapsed ("#declare BubbleSorted = BubbleSort
> (UnsortedArray)");
> 
> 
> 
> Merge sort crashed and burned with only 50 numbers, due to "Too many nested
> symbol tables" - so I'll have to figure a way around that, or find some better
> code to implement for that one.
> 
> 
> I'm now on Shell sort, and behold this abomination:
> #for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
> 
> I'm gonna try to divine the true meaning of that, and hopefully code up a
> workable SDL version of that mess ... later.
> 
> 
> Here's how everything is working so far:
> 
> Unsorted Array
> 5.627, 76.839, 25.256, 92.322, 57.569, 81.538, 25.734, 93.770, 88.249, 82.370,
> 7.027, 77.468, 47.888, 57.584, 36.548, 35.987, 88.602, 39.002, 60.983, 7.921,
>   91.258, 84.739, 6.044, 76.053, 47.104, 10.234, 89.598, 41.787, 67.629, 94.756,
> 84.110, 5.537, 21.075, 5.596, 89.346, 7.762, 19.062, 7.116, 1.259, 10.329,
>   1.728, 46.853, 88.009, 22.901, 94.856, 35.860, 9.052, 4.031, 37.408, 65.470,
> 
> 
> 
> Bubble Sorted Array
> 1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
> 9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
>   36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
> 65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
>   88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,
> 
> Bubble sorting 50 items took 12.00 ms.
> 
> 
> 
> Selection Sorted Array
> 1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
> 9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
>   36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
> 65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
>   88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,
> 
> Selection sorting 50 items took 7.00 ms.
> 
> 
> 
> Insertion Sorted Array
> 1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
> 9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
>   36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
> 65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
>   88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,
> 
> Insertion sorting 50 items took 9.00 ms.
> 
> 
> 
> Quick Sorted Array
> 1.259, 1.728, 4.031, 5.537, 5.596, 5.627, 6.044, 7.027, 7.116, 7.762, 7.921,
> 9.052, 10.234, 10.329, 19.062, 21.075, 22.901, 25.256, 25.734, 35.860, 35.987,
>   36.548, 37.408, 39.002, 41.787, 46.853, 47.104, 47.888, 57.569, 57.584, 60.983,
> 65.470, 67.629, 76.053, 76.839, 77.468, 81.538, 82.370, 84.110, 84.739, 88.009,
>   88.249, 88.602, 89.346, 89.598, 91.258, 92.322, 93.770, 94.756, 94.856,
> 
> Quick sorting 50 items took 4.00 ms.
> 
> 

And, the winner is Quick Sort followed closely by Selection Sort.

Increase the size to 70 and watch Bubble sort get even worst. Quick sort 
will take about 5 ms, while bubble will probably take over 24 ms.

Post a reply to this message

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> ...
> Here's how everything is working so far:

out of interest, what (timings) do you get when you use an already sorted array
as inputs?


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:

> out of interest, what (timings) do you get when you use an already sorted array
> as inputs?


Very good question.   Good thing you asked it too.

Unsorted array:

   Bubble sorting 1000 items took 2.35 sec

Selection sorting 1000 items took 1.13 sec

Insertion sorting 1000 items took 1.57 sec

    Quick sorting 1000 items took 88.01 ms

    Shell sorting 1000 items took 112.01 ms

     Heap sorting 1000 items took 208.01 ms


Sorted array

   Bubble sorting 1000 items took 1.55 sec

Selection sorting 1000 items took 1.12 sec

Insertion sorting 1000 items took 9.00 ms

    Quick sorting ***crashes with too many nested symbol tables***

    Shell sorting 1000 items took 60.00 ms

     Heap sorting 1000 items took 222.01 ms


So, there's still more work to be done to figure out how best to avoid this sort
of thing.

I noticed while coding shell and heap that I needed to use floor () to fix some
divisions, and remove a "-1" to increase the upper bound of a loop to make sure
that everything got fully and properly sorted.   So there's obviously a number
of issue under the hood that make coding in SDL much different than coding in
C++ or other languages.

These might be some low-level operations that ought to be investigated by
someone who codes in C or C++, to compare the outputs of simple divisions, etc.

Although there are more sorting algorithms that I'd like to get converted, I'll
post the current code here for archival purposes, and for folks too look at the
code and use the algorithms in their scene files.   Caveat emptor.

- BE

Post a reply to this message

Attachments:
Download 'sorting.inc.txt' (12 KB)