Versione delle 11:17, 4 mag 2010 modifica Leo72 (discussione \| contributi) Utenti autoverificati 9 247 modifiche Nessun oggetto della modifica ← Differenza precedente		Versione delle 00:44, 5 mag 2010 modifica annulla Leo72 (discussione \| contributi) Utenti autoverificati 9 247 modifiche Nessun oggetto della modifica Differenza successiva →
Riga 12: In [[informatica]] lo '''Smoothsort'''<ref>http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF</ref><ref>http://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html</ref> (metodo) è un [[algoritmo di ordinamento]] particolarmente indicato per ordinare liste di dati già parzialmente ordinate. Lo Smoothsort è una variante dell'[[Heap sort]] sviluppata da [[Edsger Dijkstra]] nel [[1981]]: come l'Heap sort anche lo Smoothsort presenta il limite computazionale massimo pari a [[O-grande\|O]](''n'' log ''n''). Lo Smoothsort, però, si avvicina ad un tempo O(''n'') se [[algoritmi di ordinamento adattivi\|i dati in ingresso sono già parzialmente ordinati]], mentre l'Heap sort mediamente impiega O(''n'' log ''n''), indifferentemente dal livello di ordinamento iniziale. <!--▼ ~~==Overview==~~ The array to be sorted is divided up into a string of heaps, each heap having a size equal to one of the [[Leonardo numbers]] L(n). The division process is simple - the leftmost nodes of the array are made into the largest heap possible, and the remainder is likewise divided up. It can be proved that ==Panoramica== * Any array of any length can so be divided up into sections of size L(x). La lista da ordinare viene divisa in una stringa di [[heap]], ognuna delle quali di dimensione pari ad uno dei [[numero di Leonardo\|numeri di Leonardo]] L(n). Il processo di divisione è semplice: i nodi più a sinistra della lista sono divisi nell'heap più grande possibile, ed i rimanenti sono divisi allo stesso modo. Si può dimostrare che: : Proof: trivially - the smallest L(0) is 1. No two heaps will have the same size. The string will therefore be a string of heaps strictly descending in size. Also, a bit array can be used to keep track of which Leonardo numbers are being used as heap sizes (most implementations use bit-fiddling to accomplish this). : Proof: The Leonardo numbers L(n) grow more slowly than 2<sup>n</sup>, and so for any array there will always be an L(n) that is greater than half the size of the array. The exception is the array of size 2, but can be divided into two heaps of size L(1) and L(0), which are both 1 by definition. No two heaps will have sizes that are consecutive Leonardo numbers, except for possibly the final two. : Proof: if there is anything left - even a single element - after using two consecutive Leonardo numbers L(x+1) and L(x), we could have combined them to make a larger chunk of size L(x+2). Since we didn't, there can be nothing left after two heaps of size L(x+1) and L(x). qualsiasi lista di qualsiasi dimensione può essere divisa in sezioni di dimensione L(x). Each heap, having a size of L(x), is structured from left to right as a sub-heap of size L(x-1), a sub-heap of size L(x-2), and a root node, with the exception of heaps with a size of L(1) and L(0) (which by definition are 1). Each heap maintains the heap property that a root node is always >= the root nodes of its child heaps (and therefore >= all nodes in its child heaps), and the string of heaps as a whole maintains the string property that the root node of each heap is >= the root node of the heap to the left. : Verifica: banalmente, la più piccola sezione L(0) è 1. Non possono esserci 2 heap con la stessa dimensione. La stringa sarà dunque una stringa di heap con dimensioni forzatamente in ordine decrescente. Si può inoltre utilizzare un [[array]] di bit per tenere traccia di quali numeri di Leonardo sono usati come dimensioni degli heap (molte implementazioni utilizzano a tale scopo i bit meno significativi). : Verifica: i numeri di Leonardo L(n) crescono meno rapidamente di 2<sup>n</sup>, per cui per ogni array ci sarà sempre un L(n) la cui dimensione sarà più grande della metà di quella dell'array. L'eccezione è l'array di dimensione 2, ma che può essere diviso in 2 heap di dimensione L(1) e L(0) che sono, per definizione, entrambi di valore 1. Non possono esserci 2 heap le cui dimensioni siano due numeri consecutivi di Leonardo, eccetto per gli ultimi due. * Verifica: se fosse rimasto qualcosa, anche un singolo elemento, dopo aver usato due numeri di Leonardo consecutivi L(x+1) e L(x), potremmo averli combinati insieme per formare una porzione più grande di dimensione L(x+2). Ma siccome non lo abbiamo fatto, non può essere rimasto nulla dopo due heap di dimensione L(x+1) e L(x). Ogni heap, la cui dimensione è L(x), è strutturata da sinistra a destra come un heap secondario di dimensione L(x-1), un heap secondario di dimensione L(x-2) ed un nodo radice, ad eccezione degli heap di dimensione L(1) e L(0) (che hanno valore 1 per definizione). Ogni heap mantiene la proprietà degli heap per cui un nodo radice è sempre maggiore o uguale ai nodi radice dei suoi heap figli (e quindi maggiore o uguale a tutti i nodi nei sui heap figli), e la stringa di heap in toto mantiene la proprietà delle stringhe per cui il nodo radice di ogni heap è maggiore o uguale al nodo radice dell'heap alla sua sinistra. The consequence of this is that the rightmost node in the string will always be >= all of the other nodes, and importantly - an array that is already sorted needs no rearrangement to be made into a valid series of heaps. This is the source of the adaptive qualities of the algorithm. Come conseguenza di ciò si ha che il nodo più a destra nella stringa è sempre maggiore o uguale a tutti gli altri nodi e, molto importante, un array che è già ordinato non richiede aggiustamenti per essere distribuito in una serie di heap validi. Questa è la caratteristica adattiva dell'algoritmo. The algorithm is simple. We start by dividing up our unsorted array into a single heap of one element, followed by an unsorted portion. A one-element array is trivially a valid sequence of heaps. This sequence is then grown by adding one element at a time to the right, performing swaps to keep the sequence property and the heap property, until it fills the entire original array. L'algoritmo è semplice. Si inizia dividendo la nostra lista non ordinata in un singolo heap di un elemento, seguito da una porzione non ordinata. Una lista di un elemento è banalmente una sequenza valida di heap: questa sequenza viene poi incrementata aggiungendo un elemento per volta alla sua destra, effettuando gli scambi del caso per tenere la proprietà della sequenza e la proprietà dell'heap, finché non ricopre l'intera lista iniziale. From this point on, the rightmost element of the sequence of heaps will be the largest element in any of the heaps, and will therefore be in its correct, final position. We then reduce the series of heaps back down to a single heap of one element by removing the rightmost node (which stays in place) and performing re-arrangements to restore the heap condition. When we are back down to a single heap of one element, the array is sorted. A questo punto l'elemento più a destra della sequenza di heap sarà l'elemento più grande in qualsiasi heap e sarà perciò nella sua posizione corretta e definitiva. Si riducono quindi le serie di heap fino ad un singolo heap di un solo elemento rimuovendo il nodo più a destra (che sta a posto) ed efettuando un riarrangiamento per ripristinare la condizione di heap. Quando siamo tornati nella condizione di un singolo heap con un solo elemento, allora la lista è ordinata. ▲<!-- ==Operations==

Smoothsort: differenze tra le versioni