Quick Sort

download Quick Sort

of 33

  • date post

    29-Jun-2015
  • Category

    Education

  • view

    86
  • download

    1

Embed Size (px)

description

Algoritmo di ordinamento

Transcript of Quick Sort

  • 1. AALLGGOORRIITTMMIIDDIIOORRDDIINNAAMMEENNTTOOQQUUIICCKKSSOORRTT

2. QQUUIICCKKSSOORRTTQUICKSORT un algoritmo divide et imperaUna strategia ddiivviiddee eett iimmppeerraa consiste nel suddividere unproblema in sottoproblemi, nel risolvere i sottoproblemi,e nel ricomporli per ottenere la soluzione del problemaoriginaleIdeaSi divide il vettore A in due sotto-vettori, che contengonorispettivamente 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 3. 4 2 1 6 3 8 7 53 2 1 4 6 8 7 53 2 1 6 8 7 51 2 3Si ripartisce il vettore rispetto ad A[0] = 4Si divide rispetto a 31 2Si divide rispetto a 65 6 7 85 7 8QQUUIICCKKSSOORRTT 4. QQUUIICCKKSSOORRTT:: LLOOPPEERRAAZZIIOONNEE PPIIVVOOTT Come si divide il vettore?Si usano due indici i, j che scorrono il vettore da sinistra e da destra, rispettivamente( Lindice i scorre fino a quando A[i] < A[0] - Lindice j scorre fino a quando A[j] >= A[0] )Si effettua lo scambio fra A[i] e A[j] e quindi si procede come sopraSi scorrono i, j confrontando con 44 2 8 6 3 1 7 5i jSi scambiano gli elementi4 2 8 6 3 1 7 5i jSi scorrono i, j confrontando con 44 2 1 6 3 8 7 5i jSi scambiano gli elementi4 2 1 6 3 8 7 5i jAlla fine si scambia il perno con lelemento in posizione j4 2 1 3 6 8 7 5j3 2 1 4 6 8 7 5 5. While i < j QQUUIICCKKSSOORRTTIIMMPPLLEEMMEENNTTIIAAMMOO::1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]Consideriamo un array di n interi da ordinare:4020 10 80 60 50 7 30 100SSCCEEGGLLIIAAMMOO LLEELLEEMMEENNTTOO PPIIVVOOTTEsistono diversi modi per scegliere lelemento pivot.In questo esempio, useremo il primo elemento dellarray.SSUUDDDDIIVVIIDDIIAAMMOO LLAARRRRAAYYOttenuto il pivot, ripartire gli elementi dellarray in modo che risultino:1. Un sotto-vettore contenente elementi >= pivot2. Un altro sotto-vettore contenente elementi < pivotAttiviamo il ciclo di partizionamento attraverso lo scambio di elementi minorio maggiori del pivot. 6. QQUUIICCKKSSOORRTT40 20 10 80 60 50 7 30 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jpivot = 0 7. QQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j] 8. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]j 9. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]j 10. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]j 11. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j] 12. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j] 13. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j] 14. 1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]i jQQUUIICCKKSSOORRTTWhile i < jpivot = 0 15. While i < j40 20 10 30 60 50 7 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 16. While i < j40 20 10 30 60 50 7 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 17. While i < j40 20 10 30 60 50 7 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 18. While i < j40 20 10 30 60 50 7 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 19. While i < j40 20 10 30 60 50 7 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 20. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 21. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 22. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 23. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 24. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 25. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 26. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 27. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 28. While i < j40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTT1. While arr [i] arr [pivot]j--3. Se i < jscambia arr [i] con arr [j]pivot = 0 29. While i < j1. While arr [i] arr [pivot]3. Se i < jscambia arr [i] con arr [j]40 20 10 30 7 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTTi++j--Scambia arr[pivot] con arr[j]pivot = 0 30. While i < j1. While arr [i] arr [pivot]3. Se i < jscambia arr [i] con arr [j]7 20 10 30 40 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8]i jQQUUIICCKKSSOORRTTi++j--Scambia arr [pivot] con arr [j] 31. QQUUIICCKKSSOORRTTRRIISSUULLTTAATTOO DDEELLLLAAPPAARRTTIIZZIIOONNEE7 20 10 30 40 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8] array[pivot] 32. QQUUIICCKKSSOORRTTRRIICCOORRSSIIOONNEE:: SSOOTTTTOO--VVEETTTTOORRII7 20 10 30 40 50 60 80 100[0] [1] [2] [3] [4] [5] [6] [7] [8] array[pivot] 33. 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