ALGORITMI

ALGORITMI

BUBBLE SORT O QUICK SORT?

PRESENTAZIONE DI DILETTA CIUCCI 3°G

START

Indice

indice

Spiegazione semplice

02

01

Cos'è Bubble sort?

Quick sort

03

Esempio passo per passo

05

Differenze

06

04

Come funziona Quick Sort?

BUBBLE SORT

Cos'è?

E' un metodo di ordinamento che funziona confrontando due numeri vicini e scambiandoli se sono nel posto sbagliato. Questo processo si ripete più volte fino a quando tutti i numeri sono ordinati.

SPIEGAZIONE

Confronta il primo numero con il secondo, se il primo è più grande li scambia

Fa la stessa cosa con il secondo e il terzo

Continua fino alla fine dell'array: alla fine di ogni giro il numero più grande è al suo posto

ASPETTI NEGATIVI

Bubble sort è un algoritmo semplice ma poco efficiente per grandi quantità di dati. In questo caso utilizziamo Quick Sort.

QUICK SORT

Cos'è?

E' un algoritmo di ordinamento molto efficiente. Viene usato spesso perchè molto più rapido di Bubble Sort specialmente con grande quantità di dati.

COME FUNZIONA

Sceglie un elemento dell'array chiamato PIVOT

Divide l'array in due parti: A sinistra i numeri più piccoli del PIVOT a destra quelli più grandi

Ordina le due parti nello stesso modo

Ricombina le due parti ordinate per ottenere il risultato finale

esempio

IMMAGINIAMO DI VOLER ORDINARE QUESTO ARRAY7 , 2 , 1 , 6 , 8 , 5 , 3 , 4 A- Scegli un pivot ---> 4 B- dividi l'array in due parti Sinistra (numeri<4): 2 , 1 , 3 destra (numeri>4): 7 , 6 , 8 , 5 C- ORDINA LE DUE PARTI 2 , 1 , 3 ---> 1 , 2 , 3 7 , 6 , 8 , 5 ---> 5 , 6 , 7 , 8 d- unisce le due parti 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8

differenze

Bubble sort

quick sort

-Più lento perchè confronta e scambia gli elementi più volte, utile solo per pochi elementi.-Algoritmo semplice e intuitivo -Utilizzato solo a scopo didattico

-Più veloce perchè divide in due parti e ordina, perfetto per grandi quantità di dati, anche milioni.-Algoritmo ricorsivo -Utilizzato come metodo principale di ordinamento