Download - Quick Sort
![Page 1: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/1.jpg)
ALGORITMI ALGORITMI DI DI
ORDINAMENTOORDINAMENTO
QUICKSORTQUICKSORT
![Page 2: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/2.jpg)
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
![Page 3: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/3.jpg)
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
![Page 4: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/4.jpg)
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
![Page 5: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/5.jpg)
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.
![Page 6: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/6.jpg)
40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
pivot = 0
QUICKSORTQUICKSORT
![Page 7: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/7.jpg)
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]
![Page 8: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/8.jpg)
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
![Page 9: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/9.jpg)
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
![Page 10: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/10.jpg)
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
![Page 11: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/11.jpg)
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]
![Page 12: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/12.jpg)
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]
![Page 13: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/13.jpg)
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]
![Page 14: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/14.jpg)
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
![Page 15: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/15.jpg)
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
![Page 16: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/16.jpg)
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
![Page 17: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/17.jpg)
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
![Page 18: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/18.jpg)
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
![Page 19: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/19.jpg)
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
![Page 20: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/20.jpg)
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
![Page 21: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/21.jpg)
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
![Page 22: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/22.jpg)
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
![Page 23: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/23.jpg)
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
![Page 24: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/24.jpg)
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
![Page 25: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/25.jpg)
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
![Page 26: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/26.jpg)
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
![Page 27: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/27.jpg)
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
![Page 28: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/28.jpg)
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
![Page 29: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/29.jpg)
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
![Page 30: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/30.jpg)
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]
![Page 31: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/31.jpg)
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
![Page 32: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/32.jpg)
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
![Page 33: Quick Sort](https://reader034.vdocumenti.com/reader034/viewer/2022052601/5590e7591a28ab17148b45bd/html5/thumbnails/33.jpg)
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