Please enable JavaScript.
Coggle requires JavaScript to display documents.
ORDINAMENTO - Coggle Diagram
ORDINAMENTO
ALGORITMI QUADRATICI
SELECTION SORT
FUNZIONAMENTO
CALCOLA IL MINIMO DI N-i ELEMENTI
PORTA IL MINIMO ALL'INIZIO i
OPERA IN LOCO
LOCO = MEMORIA COSTANTE
STABILE
MANTIENE ORDINE ELEMENTI UGUALI
BUBBLE SORT
FUNZIONAMENTO
CONFRONTA A 2 A 2
PORTA IL PIU' GRANDE ALLA FINE
COMPLESSITA'
MIGLIORE
LINEARE
SE SALVIAMO INDICE ULTIMO SCALBIO
PEGGIORE E MEDIA
QUADRATICA
OPERA IN LOCO
STABILE
INSERTION SORT
FUNZIONAMENTO
SCANSIONE 1 AD 1
INSERIMENTO ORDINATO
COMPLESSITA'
MIGLIORE
LINEARE
PEGGIORE
QUADRATICA
STABILE
OPERA IN LOCO
OPERA ON LINE
POSSIAMO USARLO NON AVENDO ANCORA L'INTERO INPUT
ALGORITMI COMPLESSITA'
n lg(n)
MERGE SORT
FUNZIONAMENTO
DIVIDE ET IMPERA
DIVIDE
SPEZZA IN 2 SOTTOARRAY
CALCOLA q=[(p-r)/2]
IMPERA
SOTTOARRAY ORDINATI RICORSIVAMENTE
COMBINA
SOTTOARRAY FUSI
ORDINATI CON MERGE()
HEAP SORT
STRUTTURA
HEAP BINARIO
ALBERO BINARIO QUASI COMPLETO
PROPRIETÀ HEAP-ORDER
MAX-HEAP
VALORE FIGLIO < = VALORE NODO < = VALORE PADRE
MAX-HEAPIFY
COMPLESSITA' O(lg(n))
COME FUNZIONA
NON FA NULLA
SE i E' MAX HEAP
SE I SOTTOALBERI DI I RISPETTANO MAX HEAP ORDER
SCAMBIA
SE i NON E' MAX
CERCHIAMO L'ELEMENTO MAX E LO SCAMBIAMO CON I
RICONTROLLIAMO SE VIENE RISPETTATO MAX HEAP ORDER
BUILD-MAX-HEAP
TRASFORMA
DA ARRAY
A MAX-HEAP
ESEGUE MAX-HEAPIFY
DA META' ALBERO
ALLA RADICE
COMPLESSITA'
O(n)
HEAPSORT(A)
BUILD-MAX-HEAP(A)
SPOSTA I MAX
DA INIZIO ARRAY
A FINE ARRAY
MAX-HEAPIFY AD OGNI SCAMBIO
COMPLESSITA'
O(nlg(n))
QUICK SORT
PARTITION
NUMERI < PIVOT
NUMERI > PIVOT
PIVOT
COMPLESSITA' THETA(n)
COMPLESSITA'
CASO PEGGIORE
O(n^2)
CASO MEDIO
IPOTESI DISTRIBUZIONE PIVOT UNIFORME
Θ(n lg(n))
ALGORITMO RANDOMIZZATO
LOWER BOUND
ALBERO CONFRONTI
n! FOGLIE
CASO PEGGIORE
log(n!)
COUNTING SORT
CODICE
PRIMO FOR
NUMERI UGUALI ALL'INDICE
SECONDO FOR
NUMERI MINORE UGUALE ALL'INDICE
