Date post: | 29-Jun-2015 |
Category: |
Education |
Upload: | salvatore-cianciabella |
View: | 90 times |
Download: | 1 times |
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
j
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.
40
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]
i
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]
j
40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i
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]
j
40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i
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]
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