Masm32 SDK description, downloads and other helpful linksMessage to All Guests
Started by Mikl__, December 30, 2022, 09:02:57 AM
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 N24or maybe even less.
1945 elementos ;elementsqtd movimentacoes = 6249 ;movesqtd comparacoes = 8420 ;comparations
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.