Sorting with animation (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp)
Hi Mikl__
Congrats, very nice work :thumbsup:
Biterider
Thank you, Biterider!
Hi Mikl,
You put a lot of work into this - my compliments, it's beautiful! If you run out of ideas, check BitSort (http://masm32.com/board/index.php?topic=10555.msg116704#msg116704) ;-)
Grazie mille jj2007, cercherò sicuramente di capire BitSort! E felice anno nuovo!
:thumbsup:
Very cool to watch. :thumbsup:
Thank you, mabdelouahab and Siekmanski!
سنه جديده سعيده!
Gelukkig nieuwjaar!
Quote from: Mikl__ on December 31, 2022, 12:41:49 AM
Thank you, mabdelouahab and Siekmanski!
سنه جديده سعيده!
Gelukkig nieuwjaar!
Mikl__
新年快乐 :biggrin: Traditional Chinese :tongue: To add to your foreign language greetings collection. :biggrin:
And congrats on this project, nice!
Hi, zedd151! This for You!
(https://png.pngtree.com/png-clipart/20220923/ourmid/pngtree-new-year-spring-festival-2023-chinese-new-year-lunar-new-year-png-image_238163.png)
Second part (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-2?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp#post-435836)
Third part (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-3?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp#post-435879)
Quote from: Mikl__ on January 05, 2023, 02:15:30 PM
Third part (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-3?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp#post-435879)
Google translates StoogeSort as "Silly sorting" :badgrin:
Well done,
Mikl :thumbsup:
Fourth part (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-4?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp#post-435993)
Fifth part (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-5?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp)
Fantastic :thumbsup:
Quote from: Mikl__ on January 18, 2023, 12:49:21 AM
Fifth part (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-5?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=ru&_x_tr_pto=wapp)
Hi
Mikl,
Sounds good but I can't see an animation, and the "translated" zip archive isn't found... :sad:
QuoteA multiple run through the array is performed, neighboring elements are compared and, if necessary, swapped. When the end of the array is reached, the direction is reversed. While moving to the beginning of the array, we find the maximum element and change it with the element that is at the end of the array. This pushes the minimum element to the beginning of the array. While moving to the end of the array, we find the minimum element and change it with the element that is at the beginning of the array. In this case, the maximum element is pushed to the end of the array. Thus, simultaneously during one pass, the maximum and minimum elements of the end and beginning of the array are filled.
https://en.wikipedia.org/wiki/Cocktail_shaker_sort
(https://upload.wikimedia.org/wikipedia/commons/e/ef/Sorting_shaker_sort_anim.gif)
Hi JJ!
Just now I realise how was that:
https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5
lol. I had never heard of that sorting algorithm before (cocktail shaker sort). But I once made a sorting algorithm that I called a bidirectional sort which worked very similarly (reversing direction, etc) if not very slowly. :biggrin:
Nice graphic of its implementation. Thankfully I had stopped experimenting with home brew sorting algos in favor of tried and trued methods, which of course are always much faster than anything I could dream up. It was fun though.
Quote from: HSE on January 18, 2023, 01:46:28 AM
Hi JJ!
Just now I realise how was that:
https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5
Thanks, Hector, works like a charm :thumbsup:
QuoteSounds good but I can't see an animation, and the "translated" zip archive isn't found...
Hi
jj2007!
This is especially for you!
Thanks, Mikl :thumbsup:
Insertion sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436194)
(https://wasm.in/attachments/insertionsort-gif.7766/)
Very nice animation, Mikl :thumbsup:
Insertion sort (binary search) (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436224)
Pairwise Insertion Sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436232)
Pigeonhole Sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436235)
Bucket sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436177)
Thanos sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436159)
Double Selection Sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436275)
Beautiful, Mikl :thumbsup:
Attention: not everybody has a 1920px wide screen. An invoke SystemParametersInfo, SPI_GETWORKAREA, addr rect, 0 is the easiest way to check.
Bingo Sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436281) (Bingo Bongo Sort (https://wasm.in/styles/smiles_s/mosking.gif))
(https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcSSIzHN0W6Ns3Qq8ag026mcfH_cSqPjzqLbs2HqUN77JDsLuE4gbxpW0SRKP_gE72EI8mg&usqp=CAU)
Ciao jj2007! Devi aver visto questa commedia con Adriano Celentano e Carole Bouquet?
I like Celentano, but I haven't seen all his movies. They are often a bit dumb, in contrast to his excellent songs...
Patience Sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436402)
Patience Sort ver.2 (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436404)
QuoteI made it so that you can see HOW the "stacks of cards" are formed.
"Cards" (elements of an unordered array) are arranged in several stacks, so that in each stack the elements constitute an ordered sequence - several ordered sub-arrays are created from the existing unsorted array. Preferably, the number of these sub-arrays should be smaller and the sub-arrays should be longer. This is done as follows:
The first "card" is the beginning of the first stack.
In this stack we shift cards one by one, until the next shifted card is less than or equal to the value of the top card in the stack.
Each stack is a stack - we do not work with the whole stack, but only with the top card, which is the last one placed.
If the current card is greater than the lowest card in the stack, the current card opens a new stack.
The next card is placed in the leftmost stack we can put in.
As a result, the cards are stacked in several stacks. In each stack the cards are in descending order, with the card with the lowest value at the top.
Sort out the sub-arrays from left to right. The topmost card in the left sub-array is the current minimum, return the minimum to the original array. Each time you choose a card from the stacks in the left subarrays, the minimum is chosen, moved to the empty space, and from there moved to the main array.
By combining work with an ascending-ordered queue and descending-ordered stacks we get all elements from minimum to maximum.
Solitaire sorting of an array of N
elements we need additional memory of size N2
. If we sort an array of elements sorted from smallest to largest, we get N
stacks with a single card in the stack. If we sort an array of elements sorted from larger to smaller - we get one stack of N
cards. For an unsorted array you need additional memory of size N24
or maybe even less.
Translated with www.DeepL.com/Translator (free version)
Ciao jj2007!
Thanks for responding. Now I fight with "library sorting" ("Insertion sort with O(n log n)" or "gapped insertion sort". The algorithm was proposed by Michael A.Bender, Martín Farach-Colton and Miguel Mosteiro). I have a description of the algorithm and code writied in php and C with errors. But I'm stuck and for two weeks there is no normal solution now.
Hello sir Mikl;
I found a source code in comments of this video. Feel free to remove drawings and change mt (random generator) to your matrix data.
https://www.youtube.com/watch?v=b7PF_FvEsug
Hi Mineiro! Judging by the video, this is what I need. Can I see the source text?
Olá Dom Mineiro! A julgar pelo vídeo, é disso que preciso. Posso ver o texto original?
hello sir Mikhail;
I do not own the original text by that person, but found primary source paper:
https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaMo06-librarysort.pdf
I assume that the source code was prepared by that person's teacher.
It seems to me that he modified the code to visualize the behavior of the algorithm.
Used mt.h, Mersenne Twister from the link below for random number generation:
http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/emt19937ar.html
Here is the source code attached:
Muito obrigado ao Don Mineiro!
You're welcome.
I assembled that program in Linux with debug information. Then I disassembled with 2 different programs, radare2 and objdump. I'm attaching both disassembly, maybe can be usefull.
PS: I disabled draw from source code, that was taking long time to print each screen.
The linux calling convention is:
call rdi rsi rdx rcx r8 r9
The program result:
1945 elementos ;elements
qtd movimentacoes = 6249 ;moves
qtd comparacoes = 8420 ;comparations
Obrigado Dom Mineiro!
Sleep sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436533)
Spaghetti sort (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436534)
Well done,
Mikl :thumbsup:
(https://upload.wikimedia.org/wikipedia/commons/thumb/2/21/Spaghetti_sort.gif/220px-Spaghetti_sort.gif)
Spaghetti sort, second opinion (https://cstheory.stackexchange.com/questions/7042/is-spaghetti-sort-really-on-even-as-a-thought-experiment):
QuoteThe folklore analysis of spaghetti sort assumes a model where one can extract the longest noodle in constant time, perhaps by lowering a horizontal plate ("hand") over the vertical noodles until it stops, and then extracting the noddle touching the plate. (Apparently the plate is pastamagnetic.) Within this perfectly well-defined theoretical model, the analysis is clean and obviously correct.
So is the pastamagnetic-plate model reasonable? For up to a few hundred strands of spaghetti, sure. Beyond that, obviously not. So should we make the model more reasonable by taking the physical costs of moving the plate, sensing collisions, or choosing the right noodle? What about the (nonzero!) physical cost of keeping all the noddles vertical (or at least parallel), and keeping the sensing plate and the table horizontal (or at least parallel to each other but not the noodles)? Should we worry about the measuring process causing micro-fractures that change the exact length of the noddles, or the implication from quantum mechanics that there is no such thing as "exact length"? Holy crap, is the spaghetti-sorting problem even well-defined?!
No, this way lies madness. The original theoretical analysis is predictive within the context for which the algorithm was designed — manually sorting a handful of pasta #8. That the analysis does not generalize to significantly larger values of 𝑛 or other types of pasta does not make the analysis "incorrect". It merely limits its scope.
Library sort (Gapped Insertion sort) ver.1 (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436540)
Library sort ver.2 (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-5#post-436541)
Well done, Mikl :thumbsup:
Now it would be nice to see benchmarks comparing all sort algorithms. Don't worry, it's not a serious request ;-)
Сiao jj2007!
If you will look at the previous sorts, then there I displayed how many comparisons and swapings were used. There were the same number of elements in the array was 137 in almost all sortings. Sortings were doing with positive numbers with values from 1 to 511. I indicated the time complexity in a brief description for each sort.
Table with sortings (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-4#post-436091)
I wanted to do all the sortings (81) from this table in assembler, but then I realized that I couldn't do it alone...
Translated table (https://wasm-in.translate.goog/threads/sortirovki-s-animaciej.34674/page-4?_x_tr_sl=ru&_x_tr_tl=en&_x_tr_hl=en&_x_tr_pto=wapp#post-436091)
Spaghetti sort ver.2 (https://wasm.in/threads/sortirovki-s-animaciej.34674/page-6#post-436561)