Jump to content
IGNORED

SortViz - vizualization of sorting algorithms on Atari 8-bit computer


amarok

Recommended Posts

I am glad to present you SortViz my second program written in MadPascal.

 

SortViz is an application which visualizes variety of sorting algorithms. The idea is not mine and there are a lot of videos on YouTube presenting the same subject. But as far as I know, there was no such thing on an 8-bit computer until now.

 

Please note that I created SortViz just for fun and the implementation is not optimized to be efficient or scalable. At this point there are 16 different sorting algorithms included: Insertion sort, Selection sort, Quick sort, Merge sort, Bubble sort, Coctail sort, Gnome sort, Circle sort, Comb sort, Pancake sort, Shell sort, Odd-Even sort, Bitonic sort, Radix sort, Heap sort and Double selection sort. There are also available different methods for data shuffling.

 

SortViz shows each read and write access to the data during sorting or shuffling by green and red markers on the left and right side of the data area. Also the current number of read and write operations is shown. It is possible to change the speed of processing by decreasing or increasing the delay or even pause and resume the processing as well.

 

There are two ways to present the data by a set of horizontal lines which represent the stored numbers or by the image. You can exchange the view using TAB key. It is also possible to run all sorting algorithms in a sequence as a demo by pressing Return key.

 

You can see the SortViz in action on the video below or you can play with the program on your own by executable file which I attached.

 

 

All source codes of the program are available on my gitlab, please follow the link below:
https://gitlab.com/amarok8bit/sortviz

 

SortViz (WIP1).xex

  • Like 19
  • Thanks 3
Link to comment
Share on other sites

5 hours ago, amarok said:

I am glad to present you SortViz my second program written in MadPascal.

 

SortViz is an application which visualizes variety of sorting algorithms. The idea is not mine and there are a lot of videos on YouTube presenting the same subject. But as far as I know, there was no such thing on an 8-bit computer until now.

 

Please note that I created SortViz just for fun and the implementation is not optimized to be efficient or scalable. At this point there are 16 different sorting algorithms included: Insertion sort, Selection sort, Quick sort, Merge sort, Bubble sort, Coctail sort, Gnome sort, Circle sort, Comb sort, Pancake sort, Shell sort, Odd-Even sort, Bitonic sort, Radix sort, Heap sort and Double selection sort. There are also available different methods for data shuffling.

 

SortViz shows each read and write access to the data during sorting or shuffling by green and red markers on the left and right side of the data area. Also the current number of read and write operations is shown. It is possible to change the speed of processing by decreasing or increasing the delay or even pause and resume the processing as well.

 

There are two ways to present the data by a set of horizontal lines which represent the stored numbers or by the image. You can exchange the view using TAB key. It is also possible to run all sorting algorithms in a sequence as a demo by pressing Return key.

 

You can see the SortViz in action on the video below or you can play with the program on your own by executable file which I attached.

 

 

All source codes of the program are available on my gitlab, please follow the link below:
https://gitlab.com/amarok8bit/sortviz

 

SortViz (WIP1).xex 21.11 kB · 7 downloads

SICK !!!!

 

Yes, been done before, but... boy, as cool as it can be!!

 

Runs pretty well on Incognito/800, even from SDX... just needs a bit of cleanup on exit, to regain a "clean" E: session. For the rest, amazing!!!

 

WELL DONE !!!

Edited by Faicuai
  • Thanks 1
Link to comment
Share on other sites

Cool thing. Just for fun and interest I included my version of ripple sort into the code. I know ripple is not fastest, but we had fun back in beginning of 90's at school in 'Informatik' class. My ripple version has been fastest of all ;)

procedure PPsRippleSort;
var
          i,j: Byte;
          pos: Byte;
          test,test2,hold: Byte;

begin

 for i:=0 to MAX_INDEX - 1 do begin
     test:=GetValue(i);
     hold:=test;
     pos:=i;
     for j:=i+1 to MAX_INDEX do begin
         if aborted then Exit;
         test2:=GetValue(j);
	 if test2<test then begin
            test:=test2;
            pos:=j;
         end;
     end;
     SetValue(i, test);
     SetValue(pos, hold);
 end;
end;

Start 'my' sort code with Z key: SortViz_with_PPsRipple.xex

 

btw, I noticed that this programme needs to be started with BASIC disabled - maybe add simple 'mva #$ff portb' at start will solve this.

 

PS: looking a bit deeper into the sources, I think what we called ripple sort is here called selection sort - so I outbid the code with my version, too ;)

Edited by pps
added PS
  • Like 1
Link to comment
Share on other sites

I remember having to do a variety of sorts in the computer class in high school.  The computer lab had Atari 800s.  ?

 

I did one that modified the BASIC code to sort the data statements themselves.  I don't remember which sorting algorithm it was, but it would print out the data statements on the screen with a CONT at the bottom, position the cursor above them, somehow halt the program (it's been 37 years, of course I can't remember the specifics!) resulting in a bunch of Returns to enter the new data statements into memory (overwriting the existing ones).  It repeated this for each iteration of the loop, with the end result being if you listed the program, all of the data in the data statements (one per line, IIRC) was in sorted order.  I *think* I called it the Idiotic Sort.  ?

 

 

Edit:  Found it!

 

It wasn't IDIOTIC SORT, It was Moronic Sort (Filename MORONICS.ORT)!  Remember, I was a smart-ass teenager when I wrote this....

 

BTW:  Line 113 prints 6 "up" arrows to move the cursor up 6 lines.

Second edit:  All of those :? are actually ":?" (ColonQuestionMark without the quotes).  Strange how one didn't convert near the end of line 33.  Looks like it only converts if there is a space before the :.

So line 5 prints 9 blank lines, 48 does 3 blank lines, 120 does 3 blank lines, and line 140 does 4 blank lines.

 

 

5 ? :? :? :? :? :? :? :? :?
10 REM BACK IN YOUR FACE
20 REM HA HA HA HA HA HA HA HA HA HA
30 DIM Q1$(11),Q2$(11)
31 Q1=1990
32 ? "ORIGINAL ORDER"
33 FOR Q48=1 TO 10:READ Q1$:? Q1$:NEXT Q48:? :? :?
35 FOR Q10=1 TO 9
36 Q1=1990
37 FOR Q11=1 TO 10-Q10
50 Q1=Q1+10
60 RESTORE Q1
70 READ Q1$,Q2$
80 FOR Q12=1 TO 10
90 IF Q1$(Q12,Q12)=Q2$(Q12,Q12) THEN NEXT Q12
92 IF Q1$(Q12,Q12)<Q2$(Q12,Q12) THEN Q12=10:NEXT Q12:GOTO 120
100 ? Q1;" DATA ";Q2$
110 ? Q1+10;" DATA ";Q1$
112 ? "POKE 842,12:G.120"
113 ? ""
114 POKE 842,13:STOP 
120 ? :? :NEXT Q11
130 NEXT Q10
140 ? :? :? :? "ALL DONE"
145 RESTORE 
150 FOR Q20=1 TO 10:READ Q1$:? Q1$:NEXT Q20
2000 DATA GEORGIE    .
2010 DATA FRANKIE    .
2020 DATA SUSIE      .
2030 DATA MELISSA    .
2040 DATA BRYAN      .
2050 DATA JAMES      .
2060 DATA BRENT      .
2070 DATA SCOTT      .
2080 DATA KATHLEEN   .
2090 DATA HERBERT    .

 

Edited by StickJock
Found old program!
Link to comment
Share on other sites

Another sloooooooow one ready to try:

procedure einfuegen;

var       i,j,test,pos:byte;

begin
 for i:=0 to MAX_Index -1 do begin
     test:=GetValue(i);
     pos:=i;
     for j:=i+1 to MAX_Index do
         if GetValue(j)<test then begin
            test:=GetValue(j);
            pos:=j;
         end;
     for j:=pos-1 downto i do SetValue(j+1, GetValue(j));
     SetValue(i, test);
 end;
end;

This is what our teacher programmed ;) einfuegen := insertion

But it is different to insertion sort.

 

He used it as base for another algorithm (not adapted to the source here, but cut+paste from my MadPascal programme (that based on old TurboPascal source from then):

{----------------------------------------------------------------------}
procedure einfueg(von,bis:integer;
                 var feld:field);
var       i,j,test,pos:word;

begin
 for i:=von to bis-1 do begin;
     test:=feld[i];
     pos:=i;
     for j:=i+1 to bis do
         if feld[j]<test then begin
            test:=feld[j];
            pos:=j;
         end;
     for j:=pos-1 downto i do feld[j+1]:=feld[j];
     feld[i]:=test;
 end;
 gettime(h1,m1,s1,hund);
end;
{----------------------------------------------------------------------}
procedure mischsort(test:field);

var      feld:field;
         dummy:boolean;
         v,i,links,rechts,lgr,rgr:word;


begin

 write('Sortieren mit Mischen:                ');

 gettime(h,m,s,hund);
 lgr:=max div 2;
 rgr:=lgr+1;
 einfueg(1,lgr,test);
 einfueg(rgr,max,test);
 i:=1;
 links:=i;
 rechts:=rgr;
 dummy:=false;
 repeat
       if test[links]<test[rechts] then begin
          feld[i]:=test[links];
          inc(i);
          inc(links);
          if links=rgr then begin
             for v:=rechts to max do begin
                 feld[i]:=test[v];
                 inc(i);
             end;
             dummy:=true;
          end;
       end
       else begin
          feld[i]:=test[rechts];
          inc(i);
          inc(rechts);
          if rechts>max then begin
             for v:=links to rgr do begin
                 feld[i]:=test[v];
                 inc(i);
             end;
             dummy:=true;
          end;
       end;
 until dummy=true;
 gettime(h1,m1,s1,hund);
end;
{----------------------------------------------------------------------}

Mischsort := mix sort

 

It is for sure a lot faster than his einfuegen. I failed to adapt it for correct use here in first try, but I'm tired now ;) Maybe tomorrow, or anyone else.

Edited by pps
Link to comment
Share on other sites

Thank you very much for your comments. I am glad you like it.

 

@pps, I am very impressed how quick you introduced your implemenation of Ripple Sort into SortViz - well done! Ripple sort is very similar to Selection sort but more efficient with less number of read access. If you agree I can introduce your implementation in the next version of SortViz.

 

In the comming days I would like to increase the number of sorting algorithms. So if you whish you can post your suggestions here even with source codes. I will try to integrate it with SortViz.

 

@Faicuai, thank you for you suggestion concerning cleaning up the screen after closing the application. I will check it.

 

@pps, @tebe, thank you for your tip for solving the problem with Basic. Where I need to add {$define basicoff}? I supposed that on the beginning of the main source file would be enough. Am I right?

 

 

  • Like 1
Link to comment
Share on other sites

48 minutes ago, amarok said:

Thank you very much for your comments. I am glad you like it.

 

@pps, I am very impressed how quick you introduced your implemenation of Ripple Sort into SortViz - well done! Ripple sort is very similar to Selection sort but more efficient with less number of read access. If you agree I can introduce your implementation in the next version of SortViz.

 

In the comming days I would like to increase the number of sorting algorithms. So if you whish you can post your suggestions here even with source codes. I will try to integrate it with SortViz.

 

@Faicuai, thank you for you suggestion concerning cleaning up the screen after closing the application. I will check it.

 

@pps, @tebe, thank you for your tip for solving the problem with Basic. Where I need to add {$define basicoff}? I supposed that on the beginning of the main source file would be enough. Am I right?

 

 

It was not hard work, as I tested a bit with MadPascal some time ago and had converted some of my old school programmes - one of them was the sort algorithm programme. Some small adaptions had to be done, but most work was to snip in all the needed structures into your code ;)

 

I discovered that your scroller and maybe other text runs through a 4kB border soon. When I added the entry for einfuegen_sort I posted above, all the texts get corrupted. So you have to manage the location where texts begin, if you want to add more entries.

1688181899_corruptedtexts.png.747969559015247570e6cd97bed3a014.png

 

The Basic option has to be set in the main file. But It doesn't work for me at test I just did. @tebe Do you have any idea, what could be wrong? I added into sortviz.pas just as seen in picture and as this did not work, I tested it also in main code just after begin, but same thing, booting with basic on will give errors. (compiled with 'fresh downloaded MP1.63)

basicoff.thumb.jpg.782a235f4d08f58a9c17b65ade15697f.jpg

Edited by pps
typos typos typos ;(
Link to comment
Share on other sites

Could still not run the teacher's version correct. I'm sure we tested the code back in the days if it sorts correct, but atm it looks not fine... Maybe someone changed his code a bit or I am just blind atm, what's wrong.

 

Here's another version of ripple sort, that a classmate coded. Code is shorter than mine, but beeing an 8bit man, I know[ed] -even back than- that speed matters ;)

procedure ripplesort2;

var i,n,k,tausch:byte;

begin
 for i:=0 to MAX_INDEX-1 do begin
     n:=i;
     for k:=i+1 to MAX_INDEX do
         if GetValue(n)>GetValue(k) then n:=k;
     if n>i then begin
        tausch:=GetValue(i);
        SetValue(i,GetValue(n));
        SetValue(n,tausch);
     end;
 end;
end;

This is best example that you should not always take care of short code. Esp. this line takes many reads in the array:

if GetValue(n)>GetValue(k) then n:=k;

Another reaad in the array comes then:

tausch:=GetValue(i);

Better would have been to do that last call before the k-loop and then just compare tausch with the k-Value. That's the way I did. But my code maybe could run as fast, if I just used direct compare of test to the j-value instead using test2 before. At least this would reduce the needed space, as test2 is not needed then.

 

And no, I'm not best in optimizing. Have to learn a lot.

Edited by pps
Link to comment
Share on other sites

On 4/13/2021 at 1:47 PM, Atlan_Roland said:

Did anybody figure out how/where to apply the {$define basicoff} ?

 

Couldn't get it work neither in a project of mine. (using the latested MP build taken from tebe's github page)

anywhere

 

uses ......

{$define basicoff}

 

https://github.com/tebe6502/Mad-Pascal/blob/master/base/atari/basicoff.asm

Edited by tebe
  • Thanks 1
Link to comment
Share on other sites

On 4/11/2021 at 5:49 PM, pps said:

I discovered that your scroller and maybe other text runs through a 4kB border soon. When I added the entry for einfuegen_sort I posted above, all the texts get corrupted. So you have to manage the location where texts begin, if you want to add more entries.

@amarok: forget this, I had not updated this in core.pas:

  CAPTIONS_COUNT = 38;

 

Link to comment
Share on other sites

  • 2 weeks later...

I've just published SortViz WIP demo 2.

 

Below you can find a list of changes:

  • added Odd-Even merge sort, Tim sort, Dual pivot quick sort and Cycle sort,
  • added Help screen with some keyboard shortucts (activated by Help key),
  • turning the Basic off by {$define basicoff},
  • some small improvements.

I also prepared a video with 20 of sorting algorithms:

 

 

SortViz_WIP2.xex

Edited by amarok
Added xex file
  • Like 10
  • Thanks 1
Link to comment
Share on other sites

This is such a cool visualizer - I wonder why nothing like this was shown when I was taking computer science courses?  Congratulations on finding Pancake sort - I didn't think there was anything worse than the bubble sort except maybe randomness :)

  • Thanks 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...