Algoritmi - Ordinamento non in-place con alberi binari

Forum - Algoritmi - Ordinamento non in-place con alberi binari

lorelapo (Ex-Member)
Expert

Messaggi: 355
Iscritto: 28/02/2007

Postato alle 23:10
Venerdì, 25/05/2007

Ho scritto un programma che usa strutture di appoggio per ordinare, in questo caso specifico alberi binari.
Il suo funzionamento è semplice :
1)Si parte da un vettore nel nostro esempio sarà questo :

5-4-8-1-86-7

2)Si "inalbera" il vettore in un modo molto semplice
la radice dell'albero corrisponderà sempre all'elemento 0 del vettore per cui l'albero all'inizio sarà così.

5
+--+--+

3)Si mette nell'albero l'i-esimo elemento del vettore come così:
.1)Se l'elemento da inserire è maggiore o uguale alla radice dell'albero in questione si mette nel ramo sinistro, altrimenti nel destro
.2)Se il ramo è vuoto allora si piazza il valore lì altrimenti si ripete .1
4)Si ripete 3 fino alla fine del vettore
5)Ora abbiamo l'albero magicamente ordinato ma così ci serve a poco allora si "reinvettora" l'albero visitandolo simmetricamente e sovrascrivendo il vettore originale cioè
.1)Se il ramo sinistro non è nullo ripeto .1 con lui
.2)"invettoro" il valore della radice
.3)Se il ramo destro non è nullo ripeto .1 con lui
6)Vettore ordinato
Proviamo ora
Inalberazione

5
  +---+--+
  8      4
+-+-+    +-+
86  7      1

Allora iniziamo a visitare l'albero
-L'albero sinistro è nullo ? no allora lo visito
--L'albero sinistro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (1)
---L'albero destro è nullo ? si allora ritorno
--Aggiungo la radice (4)
--L'albero destro è nullo ? si allora ritorno
-L'albero destro è nullo ? no allora lo visito
--L'albero sinistro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (7)
---L'albero destro è nullo? si allora ritorno
--Aggiungo la radice (8)
--L'albero destro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (86)
---L'albero destro è nullo ? ritorno
--ritorno
-ritorno
Ora guardate la sequenza di numeri che ci siamo ritrovati
1-4-7-8-86
Ordinati!!!
Volevo solo proporre l'algoritmo e chiedere se qualcuno ne sà il nome così posso pubblicare il programma con il suo nome.Scusate la lunghezza del topic.Grazie.

Ultima modifica effettuata da lorelapo il 25/05/2007 alle 23:12

andry89mm (Member)
Pro

Messaggi: 128
Iscritto: 21/12/2006

Postato alle 12:53
Venerdì, 01/06/2007

Una versione in C++ del "tuo" algoritmo è stato messo un pò di mesi fa nella sezione sorce C++ ; non ricordo se lo misi io o angelo_3x (un mio compagno di classe..)ed utilizza il classico algoritmo ricorsivo.Avevo realizzato anche una versione non ricorsiva, se la ritrovo la pubblico.
Sono davvero interessanti gli alberi comunque..

lorelapo (Ex-Member)
Expert

Messaggi: 355
Iscritto: 28/02/2007

Postato alle 10:11
Sabato, 02/06/2007

Non ho detto che è mio, ho solo chiesto il suo nome. Comunque lo trovo molto interessante.

andry89mm (Member)
Pro

Messaggi: 128
Iscritto: 21/12/2006

Postato alle 17:04
Sabato, 02/06/2007

lo so , anch'io lo trovo un argomento parecchio interessante : gli alberi (non solo binari ) sono molto utilizzati in informatica.
Tienimi aggiornato se trovi il nome preciso dell'argomento..

_Andrea_

Ultimo (Member)
Guru

Messaggi: 877
Iscritto: 22/05/2010

Postato alle 17:01
Lunedì, 26/07/2010

Il nome dovrebbe essere quick sort, su wikipedia viniene spiegato come funziona

If ok Then GOTO Avanza else GOTO Inizia