amarok Posted April 9, 2021 Share Posted April 9, 2021 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 19 3 Quote Link to comment Share on other sites More sharing options...
VinsCool Posted April 9, 2021 Share Posted April 9, 2021 Perfectly appropriate since Youtube keeps recommending me these kind of videos for some reason, lol Quote Link to comment Share on other sites More sharing options...
+Allan Posted April 9, 2021 Share Posted April 9, 2021 Cool. Looking forward to playing around with this. 1 1 Quote Link to comment Share on other sites More sharing options...
+Stephen Posted April 10, 2021 Share Posted April 10, 2021 That's great - can't wait to show my teammates at work. 1 Quote Link to comment Share on other sites More sharing options...
Faicuai Posted April 10, 2021 Share Posted April 10, 2021 (edited) 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 April 10, 2021 by Faicuai 1 Quote Link to comment Share on other sites More sharing options...
devwebcl Posted April 10, 2021 Share Posted April 10, 2021 Incredible demo, kudos! I like the Knuth Shuffle ? 1 Quote Link to comment Share on other sites More sharing options...
pps Posted April 10, 2021 Share Posted April 10, 2021 (edited) 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 April 10, 2021 by pps added PS 1 Quote Link to comment Share on other sites More sharing options...
StickJock Posted April 10, 2021 Share Posted April 10, 2021 (edited) 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 April 10, 2021 by StickJock Found old program! Quote Link to comment Share on other sites More sharing options...
pps Posted April 10, 2021 Share Posted April 10, 2021 (edited) 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 April 10, 2021 by pps Quote Link to comment Share on other sites More sharing options...
tebe Posted April 10, 2021 Share Posted April 10, 2021 3 hours ago, pps said: I noticed that this programme needs to be started with BASIC disabled - maybe add simple 'mva #$ff portb' at start will solve this. add {$define basicoff} 1 3 Quote Link to comment Share on other sites More sharing options...
pps Posted April 11, 2021 Share Posted April 11, 2021 10 hours ago, tebe said: add {$define basicoff} Of course, the grand master of code @tebe has thought about it Quote Link to comment Share on other sites More sharing options...
amarok Posted April 11, 2021 Author Share Posted April 11, 2021 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? 1 Quote Link to comment Share on other sites More sharing options...
pps Posted April 11, 2021 Share Posted April 11, 2021 (edited) 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. 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) Edited April 11, 2021 by pps typos typos typos ;( Quote Link to comment Share on other sites More sharing options...
pps Posted April 11, 2021 Share Posted April 11, 2021 (edited) 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 April 11, 2021 by pps Quote Link to comment Share on other sites More sharing options...
tebe Posted April 11, 2021 Share Posted April 11, 2021 6 hours ago, pps said: (compiled with 'fresh downloaded MP1.63) 1.6.3? actually 1.6.5 is fresh Quote Link to comment Share on other sites More sharing options...
Atlan_Roland Posted April 13, 2021 Share Posted April 13, 2021 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) Quote Link to comment Share on other sites More sharing options...
tebe Posted April 14, 2021 Share Posted April 14, 2021 (edited) 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 April 14, 2021 by tebe 1 Quote Link to comment Share on other sites More sharing options...
pps Posted April 17, 2021 Share Posted April 17, 2021 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; Quote Link to comment Share on other sites More sharing options...
amarok Posted April 29, 2021 Author Share Posted April 29, 2021 (edited) 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 April 29, 2021 by amarok Added xex file 10 1 Quote Link to comment Share on other sites More sharing options...
+Stephen Posted May 3, 2021 Share Posted May 3, 2021 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 1 Quote Link to comment Share on other sites More sharing options...
Recommended Posts
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.