Download - Quick Sort

Transcript

ALGORITMI ALGORITMI DI DI

ORDINAMENTOORDINAMENTO

QUICKSORTQUICKSORT

QUICKSORT è un algoritmo divide et impera

Una strategia divide et imperadivide et impera consiste nel suddividere un problema in sottoproblemi, nel risolvere i sottoproblemi, e nel ricomporli per ottenere la soluzione del problema originale•Idea

Si divide il vettore A in due sotto-vettori, che contengono rispettivamente tutti gli elementi maggiori e minori di (per esempio) A[0], cioè il primo elemento del vettore detto perno (pivot)Si ripete ricorsivamente la divisione…

QUICKSORTQUICKSORT

3 12 5786

3 5786412

1 32

Si ripartisce il vettore rispetto ad A[0] 4

Si divide rispetto a 3

1 2

8765

Si divide rispetto a 6

5 87

4 5783612

QUICKSORTQUICKSORT

QUICKSORT: L’OPERAZIONE QUICKSORT: L’OPERAZIONE PIVOTPIVOT• Come si divide il vettore?

Si usano due indici i, j che scorrono il vettore da sinistra e da destra, rispettivamente( L’indice i scorre fino a quando A[i] A[0] - L’indice j scorre fino a quando A[j] = A[0] )Si effettua lo scambio fra A[i] e A[j] e quindi si procede come sopra

4 5713682

i j

Si scorrono i, j confrontando con 4

4 5713682

i j

Si scambiano gli elementi

4 5783612

i j

Si scorrono i, j confrontando con 4

4 5783612

i j

Si scambiano gli elementi

4 5786312

3 5786412

Alla fine si scambia il perno con l’elemento in posizione j

IMPLEMENTIAMIMPLEMENTIAMO:O:

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

QUICKSORTQUICKSORT

40 20 10 80 60 50 7 30 100

Consideriamo un array di n interi da ordinare:

SCEGLIAMO L’ELEMENTO PIVOT SCEGLIAMO L’ELEMENTO PIVOT Esistono diversi modi per scegliere l’elemento pivot. In questo esempio, useremo il primo elemento dell’array.

SUDDIVIDIAMO L’ARRAYSUDDIVIDIAMO L’ARRAYOttenuto il pivot, ripartire gli elementi dell’array in modo che

risultino: 1. Un sotto-vettore contenente elementi >= pivot 2. Un altro sotto-vettore contenente elementi < pivot

Attiviamo il ciclo di partizionamento attraverso lo scambio di elementi minori o maggiori del pivot.

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot = 0

QUICKSORTQUICKSORT

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

pivot = 0

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

i j

QUICKSORTQUICKSORTWhile i < j

pivot = 0

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

While i < j

pivot = 0

40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

Scambia arr[pivot] con arr[j]

While i < j

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

pivot = 0

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

QUICKSORTQUICKSORT

Scambia arr [pivot] con arr [j]

While i < j

1. While arr [i] <= arr [pivot]i++

2. While arr [j] > arr [pivot]j--

3. Se i < jscambia arr [i] con arr [j]

RISULTATO DELLA RISULTATO DELLA PARTIZIONEPARTIZIONE

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= array[pivot] > array[pivot]

QUICKSORTQUICKSORT

RICORSIONE: RICORSIONE: SOTTO-VETTORISOTTO-VETTORI

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= array[pivot] > array[pivot]

QUICKSORTQUICKSORT

void qsort(int arr[20], int inf, int sup);int main(){ int arr[30]; int i,size; printf("Inserisci il numero di elementi da ordinare: "); scanf("%d",&size); printf("Inserisci i %d elementi : \n",size); for(i=0; i<size; i++) scanf("%d",&arr[i]); qsort(arr,0,size-1); printf("Gli elementi ordinati con QuickSort sono: \n"); for(i=0; i<size; i++) printf("%d\t",arr[i]); getch(); return 0;}

void qsort(int arr[20], int inf, int sup){ int i,j,pivot,tmp; if(inf<sup) { pivot=inf; i=inf; j=sup; while(i<j) { while(arr[i]<=arr[pivot] && i<sup) i++; while(arr[j]>arr[pivot]) j--; if(i<j) { tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } } tmp=arr[pivot]; arr[pivot]=arr[j]; arr[j]=tmp; qsort(arr,inf,j-1); qsort(arr,j+1,sup); }}

QUICKSORT IN CQUICKSORT IN C

Top Related