Smoothsort: differenze tra le versioni

Versione delle 01:30, 14 mar 2013

Versione attuale delle 11:32, 10 nov 2022

(11 versioni intermedie di 6 utenti non mostrate)

Riga 1:

{{Infobox Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|imageimmagine =[[Image: Smoothsort.gif
|none|didascalia = Lo Smoothsort durante l'ordinamento di una lista già abbastanza ordinata ma con qualche elemento fuori sequenza.]]

|struttura dati = [[Array]]

|caption=Lo Smoothsort durante l'ordinamento di una lista già abbastanza ordinata ma con qualche elemento fuori sequenza.

|tempo = <math>O(n\log n)</math>

|data=[[Array]]

|timetempo migliore = <math>O(n\log n)</math>

|best-timespazio = <math>O(n)</math> totale, <math>O(1)</math> ausiliario

|ottimale = Quando i dati sono già ordinati

|space=<math>O(n)</math> totale, <math>O(1)</math> ausiliario

|completo =

|optimal=Quando i dati sono già ordinati

|complete=

}}

In [[informatica]] lo '''Smoothsort'''<ref>[httphttps://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF ewd796a<!-- Titolo generato automaticamente -->]</ref><ref>[httphttps://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)<!-- Titolo generato automaticamente -->]</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&nbsp;''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&nbsp;''n''), indifferentemente dal livello di ordinamento iniziale.

==Analisi==

La lista da ordinare viene divisa in una stringa di [[Heap (struttura dati)|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:

* qualsiasi lista di qualsiasi dimensione può essere divisa in sezioni di dimensione L(x).

Riga 23:

* 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 suisuoi 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.

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.

Riga 30:

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 effettuando 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==

==Note==

Ignoring (for the moment) Dijkstra's optimisations, two operations are necessary - increase the string by adding one element to the right, and decrease the string by removing the right most element (the root of the last heap), preserving the heap and string conditions.

<references/>

==Collegamenti esterni==

===Grow the string by adding an element to the right===

* {{cita web|http://www.enterag.ch/hartwig/order/smoothsort.pdf|Commented transcription of EWD796a}}

{{ordinamento}}

* If the last two heaps are of size L(x+1) and L(x) (ie: consecutive leonardo numbers), the new element becomes the root node of a bigger heap of size L(x+2). This heap will not necessarily have the heap property.

{{portale|informatica}}

* If the last two heaps of the string are not consecutive Leonardo numbers, then the rightmost element becomes a new heap of size 1. This 1 is taken to be L(1), unless the rightmost heap already has size L(1), in which case the new one-element heap is taken to be of size L(0).

After this, the heap and string properties must be restored. To do this,

# the rightmost heap (the one that has just been created) becomes the "current" heap

# while there is a heap to the left of the current heap and its root is larger than the current root '''and''' both of its child heap roots

#* then swap the new root with the root on the heap to the left (this will not disturb the heap property of the current heap). That heap then becomes the current heap.

# Perform a "filter" operation on the current heap to establish the heap property:

#*while the current heap has a size greater than 1 and either child heap of the current heap has a root node greater than the root of the current heap

#** Swap the greater child root with the current root. That child heap becomes the current heap.

The filter operation is greatly simplified by the use of leonardo numbers, as a heap will always either be a single node, or will have two child heaps. One does not need to manage the condition of one of the child heaps not being present.

====Optimisation====

* If the new heap is going to become part of a larger heap by the time we are done, then don't bother establishing the string property: it only needs to be done when a heap has reached its final size.

** To do this, look at how many elements are left after the new heap of size L(x). If there are more than L(x-1)+1, then this new heap is going to be merged.

* Do not maintain the heap property of the rightmost heap. If that heap becomes one of the final heaps of the string, then maintaining the string property will restore the heap property. Of course, whenever a new heap is created, then the rightmost heap is no longer the rightmost and the heap property needs to be restored.

===Shrink the string by removing the rightmost element===

If the rightmost heap has a size of 1 (ie, L(1) or L(0)), then nothing needs to be done. Simply remove that rightmost heap.

If the rightmost heap does not have a size of 1, then remove the root, exposing the two sub-heaps as members of the string. Restore the string property first on the left one and then on the right one.

====Optimisation====

* When restoring the string property, we do not need to compare the root of the heap to the left with the two child nodes of the heaps that have just been exposed, because we know that these newly exposed heaps have the heap property. Just compare it to the root.

==Java implementation==

This code uses '''lo''' and '''hi''' as the bounds of the array ''inclusive''. Note that this is not the usual convention.

<source lang="java5">

// by keeping these constants, we can avoid the tiresome business

// of keeping track of Dijkstra's b and c. Instead of keeping

// b and c, I will keep an index into this array.

static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,

177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,

35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,

1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,

48315633, 78176337, 126491971, 204668309, 331160281, 535828591,

866988873 // the next number is > 31 bits.

};

public static <C extends Comparable<? super C>> void sort(C[] m,

int lo, int hi) {

int head = lo; // the offset of the first element of the prefix into m

// These variables need a little explaining. If our string of heaps

// is of length 38, then the heaps will be of size 25+9+3+1, which are

// Leonardo numbers 6, 4, 2, 1.

// Turning this int a binary number, we get b01010110 = x56. We represent

// this number as a pair of numbers by right-shifting all the zeros and

// storing the mantissa and exponent as "p" and "pshift".

// This is handy, because the exponent is the index into L[] giving the

// size of the rightmost heap, and because we can instantly find out if

// the rightmost two heaps are consecutive leonardo numbers by checking

// (p&3)==3

int p = 1; // the bitmap of the current standard concatenation >> pshift

int pshift = 1;

while (head < hi) {

if ((p & 3) == 3) {

// Add 1 by merging the first two blocks into a larger one.

// The next Leonardo num is one bigger.

sift(m, pshift, head);

p >>>= 2;

pshift += 2;

} else {

// adding a new block of length 1

if (LP[pshift - 1] >= hi - head) {

// this block is its final size.

trinkle(m, p, pshift, head, false);

} else {

// this block will get merged. Just make it trusty.

sift(m, pshift, head);

}

if (pshift == 1) {

// LP[1] is being used, so we add use LP[0]

p <<= 1;

pshift--;

} else {

// shift out to position 1, add LP[1]

p <<= (pshift - 1);

pshift = 1;

}

}

p |= 1;

head++;

}

trinkle(m, p, pshift, head, false);

while (pshift != 1 || p != 1) {

if (pshift <= 1) {

// block of length 1. No fiddling needed

int trail = Integer.numberOfTrailingZeros(p & ~1);

p >>>= trail;

pshift += trail;

} else {

p <<= 2;

p ^= 7;

pshift -= 2;

// ok. This block gets broken into three bits. The rightmost

// bit is a block of length 1. The left hand part is split into

// two, a block of length LP[pshift+1] and one of LP[pshift].

// Both these two are appropriately heapified, but the root

// nodes are not nessesarily in order. We therefore semitrinkle

// both

// of them

trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);

trinkle(m, p, pshift, head - 1, true);

}

head--;

}

}

private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,

int head) {

// we do not use Floyd's improvements to the heapsort sift, because we

// are not doing what heapsort does - always moving nodes from near

// the bottom of the tree to the root.

C val = m[head];

while (pshift > 1) {

int rt = head - 1;

int lf = head - 1 - LP[pshift - 2];

if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)

break;

if (m[lf].compareTo(m[rt]) >= 0) {

m[head] = m[lf];

head = lf;

pshift -= 1;

} else {

m[head] = m[rt];

head = rt;

pshift -= 2;

}

}

m[head] = val;

}

private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,

int pshift, int head, boolean isTrusty) {

C val = m[head];

while (p != 1) {

int stepson = head - LP[pshift];

if (m[stepson].compareTo(val) <= 0)

break; // current node is greater than head. Sift.

// no need to check this if we know the current node is trusty,

// because we just checked the head (which is val, in the first

// iteration)

if (!isTrusty && pshift > 1) {

int rt = head - 1;

int lf = head - 1 - LP[pshift - 2];

if (m[rt].compareTo(m[stepson]) >= 0

|| m[lf].compareTo(m[stepson]) >= 0)

break;

}

m[head] = m[stepson];

head = stepson;

int trail = Integer.numberOfTrailingZeros(p & ~1);

p >>>= trail;

pshift += trail;

isTrusty = false;

}

if (!isTrusty) {

m[head] = val;

sift(m, pshift, head);

}

}

</source>

-->

==Riferimenti==

<references/>

* [http://www.enterag.ch/hartwig/order/smoothsort.pdf Commented transcription of EWD796a]

{{ordinamento}}

[[Categoria:Algoritmi di ordinamento]]

[[Categoria:Heap]]