Sorting with animation

[Mikl__]

Double Selection Sort

[jj2007]

Beautiful, Mikl

Attention: not everybody has a 1920px wide screen. An invoke SystemParametersInfo, SPI_GETWORKAREA, addr rect, 0 is the easiest way to check.

[Mikl__]

Bingo Sort (Bingo Bongo Sort )


Ciao jj2007! Devi aver visto questa commedia con Adriano Celentano e Carole Bouquet?

[jj2007]

I like Celentano, but I haven't seen all his movies. They are often a bit dumb, in contrast to his excellent songs...

[Mikl__]

Patience Sort

Patience Sort ver.2

[jj2007]

I 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)

[Mikl__]

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.

[mineiro]

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

[Mikl__]

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?

[mineiro]

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:

[Mikl__]

Muito obrigado ao Don Mineiro!

[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:

Code Select Expand


1945 elementos                       ;elements
qtd movimentacoes = 6249      ;moves
qtd comparacoes = 8420         ;comparations


[Mikl__]

Obrigado Dom Mineiro!

[Mikl__]

Sleep sort

Spaghetti sort

[jj2007]

Well done, Mikl



Spaghetti sort, second opinion:

The 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.