# data[].attributes.attachment_link.description
Cliccare sulla bandiera per avviare il programma,poi decidere quanti numeri vorreste ordinare, successivamente cliccate sul pulsante caricamento per caricare i numeri puramente casuali ,infine cliccate sul pulsante ordinamento per ordinare i numeri.

# data[].attributes.attachment_link.readable_text
La web app che trovate in questa pagina vi permette di ascoltare il suono e osservare la danza degli algoritmi quotidiani. Sono gli stessi algoritmi che di solito lavorano in silenzio per rispondere ad un nostro click, o che noi stessi applichiamo più o meno consapevolmente nella vita di tutti i giorni. Ora li potete osservare e ascoltare per comprenderli meglio.

Come funziona

Quando lanciate l'applicazione vengono generati 100 numeri casuali, rappresentati da sinistra a destra come tante palline appese a sottili fili, tanto più lunghi quanto più grandi sono i numeri che rappresentano.

Se volete aumentare o diminuire la quantità di palline, potete usare le grandi frecce azzurre e premere il tasto centrale. Se invece volete rimescolarli potete cliccare sulle due frecce rosse incrociate.

Per cercare una pallina appesa ad una certa altezza cliccate due volte sullo schermo (in una posizione in cui non ci siano pulsanti attivi) per indicare l'intervallo di altezze entro cui effettuare la ricerca. Un algoritmo di ricerca individuerà per voi la pallina che cercate, evidenziando in rosso i tentativi di ricerca e in verde la soluzione trovata (se esiste). Se le palline non sono in ordine verrà effettuata una ricerca sequenziale, altrimenti una ricerca dicotomica.

Per mettere le palline in ordine di altezza potete cliccare su uno qualsiasi dei triangoli colorati. Corrispondono ad algoritmi di ordinamento diversi: il tasto blu è il Selection sort, il tasto verde è l' Insertion sort, il tasto giallo è il Bubble sort, il tasto rosso è il Merge sort. Sono tutti equivalenti (producono lo stesso risultato), ma hanno efficienza diversa. Metteteli alla prova.

Se volete mettere le palline in ordine crescente o decrescente di altezza potete cliccare sull'icona nera in basso a destra e rilanciare un qualsiasi algoritmo di ordinamento.

I contatori che appaiono in basso a sinistra mostrano il numero di confronti e il numero di scambi effettuati dall'algoritmo che avete scelto di utilizzare. Osservandoli potete mettere a confronto l'efficienza dei diversi algoritmi.

La danza

Durante l'esecuzione di ogni algoritmo di ricerca o di ordinamento, l'applicazione ne mostra il funzionamento evidenziando in rosso le palline prese in considerazione e aggiornando la rappresentazione ad ogni scambio.

Potete disabilitare (e riabilitare) la visualizzazione dei passaggi intermedi cliccando sull'icona dell'occhio.

Il suono

Per far suonare gli algoritmi ho preso il campionamento del suono emesso da 64 tasti di un pianoforte e li ho associati alle lunghezze dei fili, distribuendoli uniformemente dal più lungo (suono più grave) al più corto (suono più acuto).

L'app emette tutti i suoni associati alle palline prese in considerazione dall'algoritmo.

Potete disabilitare (e riabilitare) la riproduzione dei suoni cliccando sull'icona delle note musicali.

Cosa ci insegna

L'App ci aiuta a comprendere il principio di funzionamento dei 6 algoritmi che implementa e ad apprezzarne i punti di forza e di debolezza:

Vedendoli in funzione possiamo comprendere in che ordine prendono in considerazioni gli elementi e cercare di riconoscere il comportamento ciclico della ricerca sequenziale, il comportamento ricorsivo della ricerca dicotomica e del merge sort, i due cicli nidificati del Selection sort, dell'Insertion sort e del Bubble sort

Ascoltando l'altezza dei suoni emessi e la frequenza con cui vengono riproposte le stesse note possiamo comprendere l'alternanza dei cicli.

Apprezzandone la durata possiamo confrontarne l'efficienza.

Osservando i contatori possiamo misurare accuratamente il numero di passi necessari ad ottenere la soluzione.

Rigenerando l'insieme di palline possiamo verificare la dipendenza del tempo di esecuzione dai dati del problema.

Come è fatta

L'App è stata sviluppata in diretta durante le lezioni 06.03 e 06.04 di Algoritmi quotidiani, programmando in JavaScript nell'ambiente. L'applicazione può essere utilizzata liberamente sia da computer che da smartphone e tablet. Chi vuole può guardare il codice JavaScript e provare a modifcarlo. Spostando il cursore dalla lepre alla tartaruga si può anche rallentare l'esecuzione del codice per seguirla passo-passo.

Qui trovate le video-lezioni e le slide che illustrano le fasi di sviluppo e le modalità di utilizzo:

Per saperne di più

Vi invito a seguire liberamente le lezioni online di Algoritmi quotidiani e gli aggiornamenti nel gruppo Facebook.

# data[].attributes.attachment_link.description
La web app che trovate in questa pagina vi permette di ascoltare il suono e osservare la danza degli algoritmi quotidiani. Sono gli stessi algoritmi che di solito lavorano in silenzio per rispondere ad un nostro click, o che noi stessi applichiamo più o meno consapevolmente nella vita di tutti i giorni.

# data[].attributes.headline
VIDEO SUL FUNZIONAMENTO DELL' ORDINAMENTO

# data[].attributes.subject
VIDEO SUL FUNZIONAMENTO DELL' ORDINAMENTO

# data[].attributes.headline
IMMAGINI DELL' ESECUZIONE DELL' ORDINAMENTO

# data[].attributes.subject
IMMAGINI DELL' ESECUZIONE DELL' ORDINAMENTO

# data[].attributes.attachment_link.readable_text
, Coordinator of Europe Code Week

Published on

http://codemooc.org/algomooc/

1. 1. Mettiamo(li) in ordine alessandro bogliolo http://codemooc.org/algoritmi/ Algo 06.02

2. 2. Algo 06.02 alessandro.bogliolo@uniurb.it Tuttiinfila 0 1 2 3 4 5 6 altezza[3] indice altezza 175 165 110 180 150 100 170

3. 3. Algo 06.02 alessandro.bogliolo@uniurb.it Ordinamentodiuna sequenza 0 1 2 3 4 5 6 altezza[3] indice altezza 175 165 110 180 150 100 170 Input * Data una sequenza di elementi tra i quali esista una relazione d'ordine * Dato il criterio di ordinamento da applicare Output * Restituire la sequenza ordinata secondo il criterio dato

4. 4. Algo 06.02 alessandro.bogliolo@uniurb.it Input 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170

5. 5. Algo 06.02 alessandro.bogliolo@uniurb.it Output 0 1 2 3 4 5 6 100 110 150 165 170 175 180

6. 6. Algo 06.02 alessandro.bogliolo@uniurb.it 1. SELECTION SORT Cerchiamo nella sequenza data l'elemento più piccolo e lo mettiamo all'inizio della fila Procediamo selezionando sempre il più piccolo tra quelli che restano e lo aggiungiamo alla fila ordinata che stiamo componendo

7. 7. Algo 06.02 alessandro.bogliolo@uniurb.it 7 SELECTIONSORT

8. 8. Algo 06.02 alessandro.bogliolo@uniurb.it 6 SELECTIONSORT

9. 9. Algo 06.02 alessandro.bogliolo@uniurb.it 5 SELECTIONSORT

10. 10. Algo 06.02 alessandro.bogliolo@uniurb.it 4 SELECTIONSORT

11. 11. Algo 06.02 alessandro.bogliolo@uniurb.it 3 SELECTIONSORT

12. 12. Algo 06.02 alessandro.bogliolo@uniurb.it 2 SELECTIONSORT

13. 13. Algo 06.02 alessandro.bogliolo@uniurb.it 1 SELECTIONSORT

14. 14. Algo 06.02 alessandro.bogliolo@uniurb.it 7+6+5+4+3+2+1 7*8/2 SELECTIONSORT

15. 15. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 175min 7N da ordinareordinato 0i 0j 0pos i indica il numero di elementi già ordinati e la posizione dove inserire il prossimo elemento in ordine j scorre tutti gli indici degli elementi ancora da ordinare pos memorizza la posizione del più piccolo (min) degli elementi ancora da ordinare

16. 16. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 165min 7N da ordinareordinato 0i 1j 1pos Sposto l'indice j, confronto altezza[j] con min, siccome l'elemento in posizione j è minore di min, aggiorno min e pos.

17. 17. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 110min 7N da ordinareordinato 0i 2j 2pos Sposto l'indice j, confronto altezza[j] con min, siccome l'elemento in posizione j è minore di min, aggiorno min e pos.

18. 18. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 110min 7N da ordinareordinato 0i 3j 2pos Sposto l'indice j, confronto altezza[j] con min, ma siccome l'elemento in posizione j NON è minore di min, NON aggiorno min e pos.

19. 19. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 110min 7N da ordinareordinato 0i 4j 2pos Sposto l'indice j, confronto altezza[j] con min, ma siccome l'elemento in posizione j NON è minore di min, NON aggiorno min e pos.

20. 20. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 100min 7N da ordinareordinato 0i 5j 5pos Sposto l'indice j, confronto altezza[j] con min, siccome l'elemento in posizione j è minore di min, aggiorno min e pos.

21. 21. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 100min 7N da ordinareordinato 0i 6j 5pos Sposto l'indice j, confronto altezza[j] con min, ma siccome l'elemento in posizione j NON è minore di min, NON aggiorno min e pos.

22. 22. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 175 165 110 180 150 100 170 SELECTIONSORT 100min 7N da ordinareordinato 0i 6j 5pos Scambio gli elementi in posizione i e pos Incremento i Cerco nuovamente il minimo tra quelli da ordinare

23. 23. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 100 165 110 180 150 175 170 SELECTIONSORT 110min 7N da ordinareordinato 1i 6j 2pos

24. 24. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 100 110 165 180 150 175 170 SELECTIONSORT min 7N da ordinareordinato 2i 6j 4pos 150

25. 25. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 100 110 150 180 165 175 170 SELECTIONSORT min 7N da ordinareordinato 3i 6j 4pos 165

26. 26. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 100 110 150 165 180 175 170 SELECTIONSORT min 7N da ordinareordinato 4i 6j 6pos 170

27. 27. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 100 110 150 165 170 175 180 SELECTIONSORT min 7N da ordinareordinato 5i 6j 5pos 175

28. 28. Algo 06.02 alessandro.bogliolo@uniurb.it 0 1 2 3 4 5 6indice altezza 100 110 150 165 170 175 180 SELECTIONSORT 180min 7N da ordinareordinato 6i 6j 6pos

29. 29. Algo 06.02 alessandro.bogliolo@uniurb.it * Invariante di ciclo: ad ogni ciclo k * ik è il numero di elementi già ordinati * altezzak[m]<=altezzak[m+1] per ogni m<k * altezzak[m]<=altezzak[posk]<=altezzak[n] per ogni m<k, n>=k * altezzak[] contiene tutti gli elementi dati * Quando k=N-1 * I primi N-1 elementi sono ordinati e tutti <= all'unico non ancora ordinato, che quindi rispetta a sua volta il criterio di ordinamento crescente Selectionsort Correttezza

30. 30. Algo 06.02 alessandro.bogliolo@uniurb.it Selectionsort Complessità N N N-1 N-2 2 1 𝑓 𝑛 = ℎ=1 𝑛 ℎ = 1 + 2 + ⋯ + 𝑛 = 𝑛 𝑛 + 1 2 = 𝑛2 2 + 𝑛 2 ∈ 𝑂(𝑛2)

31. 31. Algo 06.02 alessandro.bogliolo@uniurb.it 2. INSERTION SORT Prendo gli elementi ad uno ad uno nell'ordine in cui mi sono dati e cerco la posizione giusta in cui inserirli nel nuovo array che sto mettendo in ordine

32. 32. Algo 06.02 alessandro.bogliolo@uniurb.it INSERTIONSORT

33. 33. Algo 06.02 alessandro.bogliolo@uniurb.it 1 INSERTIONSORT

34. 34. Algo 06.02 alessandro.bogliolo@uniurb.it 2 (1) INSERTIONSORT

35. 35. Algo 06.02 alessandro.bogliolo@uniurb.it 3 (1) INSERTIONSORT

36. 36. Algo 06.02 alessandro.bogliolo@uniurb.it 4 (3) INSERTIONSORT

37. 37. Algo 06.02 alessandro.bogliolo@uniurb.it 5 (4) INSERTIONSORT

38. 38. Algo 06.02 alessandro.bogliolo@uniurb.it 6 (1) INSERTIONSORT

39. 39. Algo 06.02 alessandro.bogliolo@uniurb.it 7 (4) 1+1+3+4+1+4 <7*8/2 INSERTIONSORT

40. 40. Algo 06.02 alessandro.bogliolo@uniurb.it 3. BUBBLE SORT Partendo dall'ultimo elemento confronto coppie di elementi vicini e li scambio, se necessario, in modo da portare a galla il più piccolo. Quando arrivo in cima riparto dal fondo e procedo così finché ci sono scambi da fare

41. 41. Algo 06.02 alessandro.bogliolo@uniurb.it 1BUBBLESORT

42. 42. Algo 06.02 alessandro.bogliolo@uniurb.it 2BUBBLESORT

43. 43. Algo 06.02 alessandro.bogliolo@uniurb.it 2BUBBLESORT

44. 44. Algo 06.02 alessandro.bogliolo@uniurb.it 3BUBBLESORT

45. 45. Algo 06.02 alessandro.bogliolo@uniurb.it 3BUBBLESORT

46. 46. Algo 06.02 alessandro.bogliolo@uniurb.it 4BUBBLESORT

47. 47. Algo 06.02 alessandro.bogliolo@uniurb.it 4BUBBLESORT

48. 48. Algo 06.02 alessandro.bogliolo@uniurb.it 5BUBBLESORT

49. 49. Algo 06.02 alessandro.bogliolo@uniurb.it 5BUBBLESORT

50. 50. Algo 06.02 alessandro.bogliolo@uniurb.it 6BUBBLESORT

51. 51. Algo 06.02 alessandro.bogliolo@uniurb.it 6BUBBLESORT

52. 52. Algo 06.02 alessandro.bogliolo@uniurb.it 7BUBBLESORT

53. 53. Algo 06.02 alessandro.bogliolo@uniurb.it 8BUBBLESORT

54. 54. Algo 06.02 alessandro.bogliolo@uniurb.it 8BUBBLESORT

55. 55. Algo 06.02 alessandro.bogliolo@uniurb.it 9BUBBLESORT

56. 56. Algo 06.02 alessandro.bogliolo@uniurb.it 10BUBBLESORT

57. 57. Algo 06.02 alessandro.bogliolo@uniurb.it 10BUBBLESORT

58. 58. Algo 06.02 alessandro.bogliolo@uniurb.it 11BUBBLESORT

59. 59. Algo 06.02 alessandro.bogliolo@uniurb.it 11BUBBLESORT

60. 60. Algo 06.02 alessandro.bogliolo@uniurb.it 11BUBBLESORT

61. 61. Algo 06.02 alessandro.bogliolo@uniurb.it 12BUBBLESORT

62. 62. Algo 06.02 alessandro.bogliolo@uniurb.it 12BUBBLESORT

63. 63. Algo 06.02 alessandro.bogliolo@uniurb.it 13BUBBLESORT

64. 64. Algo 06.02 alessandro.bogliolo@uniurb.it 14BUBBLESORT

65. 65. Algo 06.02 alessandro.bogliolo@uniurb.it 14BUBBLESORT

66. 66. Algo 06.02 alessandro.bogliolo@uniurb.it 15BUBBLESORT

67. 67. Algo 06.02 alessandro.bogliolo@uniurb.it 15BUBBLESORT

68. 68. Algo 06.02 alessandro.bogliolo@uniurb.it 15BUBBLESORT

69. 69. Algo 06.02 alessandro.bogliolo@uniurb.it 16BUBBLESORT

70. 70. Algo 06.02 alessandro.bogliolo@uniurb.it 17BUBBLESORT

71. 71. Algo 06.02 alessandro.bogliolo@uniurb.it 18BUBBLESORT

72. 72. Algo 06.02 alessandro.bogliolo@uniurb.it 19BUBBLESORT

73. 73. Algo 06.02 alessandro.bogliolo@uniurb.it 19BUBBLESORT

74. 74. Algo 06.02 alessandro.bogliolo@uniurb.it 20BUBBLESORT

75. 75. Algo 06.02 alessandro.bogliolo@uniurb.it 21BUBBLESORT

76. 76. Algo 06.02 alessandro.bogliolo@uniurb.it 21BUBBLESORT

77. 77. Algo 06.02 alessandro.bogliolo@uniurb.it 22BUBBLESORT

78. 78. Algo 06.02 alessandro.bogliolo@uniurb.it 22BUBBLESORT

79. 79. Algo 06.02 alessandro.bogliolo@uniurb.it 22BUBBLESORT

80. 80. Algo 06.02 alessandro.bogliolo@uniurb.it 4. MERGE SORT Risolvo il problema in modo ricorsivo, riducendolo a due problemi di dimensione inferiore (l'ordinamento delle due metà dell'array dato) e unendo i risultati (merge)

81. 81. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà Immaginiamo di avere qualcuno che metta in ordine per noi le due metà dell'array. Sapremmo ricomporle per ottenere l'array ordinato?

82. 82. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà Confrontiamo i primi elementi delle due metà ordinate, prendiamo il più piccolo e aggiungiamolo all'array ordinato. Procediamo così fino ad esaurire gli elementi delle due metà. 1

83. 83. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà 2

84. 84. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà 3

85. 85. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà 4

86. 86. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà 5

87. 87. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà 6

88. 88. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Seconda metàPrima metà <7

89. 89. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Ora che abbiamo visto che il merge funziona, proviamo ad applicarlo ricorsivamente... Livello 1

90. 90. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Ora che abbiamo visto che il merge funziona, proviamo ad applicarlo ricorsivamente... Livello 2

91. 91. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Ora che abbiamo visto che il merge funziona, proviamo ad applicarlo ricorsivamente... Livello 3 merge

92. 92. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Ora che abbiamo visto che il merge funziona, proviamo ad applicarlo ricorsivamente... Livello 2 merge

93. 93. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT Ora che abbiamo visto che il merge funziona, proviamo ad applicarlo ricorsivamente... Livello 1 merge

94. 94. Algo 06.02 alessandro.bogliolo@uniurb.it MERGESORT 𝑓 𝑛 = 𝑂(𝑛 ∙ log 𝑛 ) ≤ 7 ∙ 3

# data[].attributes.attachment_link.description
Coordinator of Europe Code Week Published on http://codemooc.org/algomooc/ 1. Mettiamo(li) in ordine alessandro bogliolo http://codemooc.org/algoritmi/ Algo 06.02 2. Algo 06.02 alessandro.bogliolo@uniurb.it Tuttiinfila 0 1 2 3 4 5 6 altezza[3] indice altezza 175 165 110 180 150 100 170 3.