Basi di Coding 02 - Ricerca e Ordinamento PDF

Prof.Luca Ronchetti Basi di Coding RICERCA E ORDINAMENTO RICERCHE E ORDINAMENTI RICERCHE E ORDINAMENTI Un algoritmo di ordinamento è un algoritmo che viene utilizzato per posizionare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in...

Prof.Luca Ronchetti Basi di Coding RICERCA E ORDINAMENTO RICERCHE E ORDINAMENTI RICERCHE E ORDINAMENTI Un algoritmo di ordinamento è un algoritmo che viene utilizzato per posizionare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore o maggiore di quello che lo segue. In assenza di altre specifiche, essa viene sempre considerata totale, cioè tale da rendere sempre possibile il confronto tra due elementi dell'insieme: le relazioni d'ordine parziale danno origine agli algoritmi di ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente. Algoritmi di ordinamento di array quali: selection sort bubble sort insertion sort merge sort quick sort ORDINAMENTI: criteri di partizionamento Per analizzare e studiare gli algoritmi di ordinamento sono stati definiti differenti criteri di partizionamento, analizzati qui di seguito. Ordinamento interno e ordinamento esterno Se il file da ordinare, o la struttura dati, può essere contenuto in memoria, il metodo viene detto interno. L'ordinamento di file residenti su disco o su nastro viene chiamato ordinamento esterno: la differenza principale tra i due tipi di ordinamento sta nel fatto che mentre nel primo è possibile accedere direttamente a un record, nel secondo i record devono essere indirizzati in modo sequenziale o al più per grandi blocchi. Ordinamento per confronti-scambi e digitale A seconda del tipo di operazione che viene effettuata, si hanno due differenti tipi di ordinamento: l'ordinamento che effettua confronti e scambi (a≤b:exch(a,b)) e l'algoritmo digitale che accede all'informazione tramite un gruppo di bit alla volta. Ordinamento adattivo Solitamente un algoritmo di ordinamento sfrutta operazioni di confronto e scambio. Se tali operazioni vengono svolte in modo indipendente dai dati di input l'algoritmo viene definito non adattivo. Mentre se un metodo di ordinamento esegue diverse sequenze di operazioni in funzione del risultato dei confronti si ha un algoritmo adattivo. ORDINAMENTI: criteri di partizionamento Per analizzare e studiare gli algoritmi di ordinamento sono stati definiti differenti criteri di partizionamento, analizzati qui di seguito. Stabilità di un algoritmo Un metodo di ordinamento si dice stabile se preserva l'ordine relativo dei dati con chiavi uguali all'interno del file da ordinare. Ad esempio se si ordina per anno di corso una lista di studenti già ordinata alfabeticamente un metodo stabile produce una lista in cui gli alunni dello stesso anno sono ancora in ordine alfabetico mentre un ordinamento instabile probabilmente produrrà una lista senza più alcuna traccia del precedente ordinamento. La stabilità può essere forzata aggiungendo prima dell'ordinamento un piccolo indice a ciascuna chiave o allungando in qualche altro modo le chiavi sulle quali operare, in modo da renderle univoche preservando l'informazione sulla posizione relativa degli elementi. Algoritmi in place Un algoritmo si dice algoritmo in place quando non crea una copia dell'input per raggiungere l'obiettivo, l'ordinamento in questo caso. Pertanto un algoritmo in place risparmia memoria rispetto ad un algoritmo non in place. Si noti infatti che, malgrado le considerazioni fatte sulla complessità abbiano senso in generale, hanno una rilevanza decisiva sui grandi numeri. Allo stesso modo della proprietà di essere o meno in place. RICERCHE E ORDINAMENTI Algoritmi di ordinamento di array SEMPLICI EFFICIENTI NON CONFRONTATIVI Selection sort Merge sort Radix sort Insertion sort Quick sort Bucket sort Bubble sort Heap sort + facili da implementare + più efficienti rispetto agli algoritmi non si basano sul confronto diretto semplici e spesso sono preferiti per degli elementi, ma utilizzano altre - hanno una complessità relativamente grandi quantità di dati. strategie come l’analisi delle cifre o alta, rendendoli meno efficienti per la suddivisione in secchi per grandi quantità di dati. - possono richiedere più spazio di ordinare gli elementi. memoria per l’elaborazione. + possono essere particolarmente efficienti in determinati scenari specifici. ORDINAMENT SELECTION SORT Selection sort, detto anche algoritmo per selezione o da alcuni sel-sort, è un algoritmo di ordinamento di un array: non particolarmente efficiente; facile da comprendere e implementare. Questo algoritmo, chiamato anche ordinamento per minimi successivi, è importante a fini didattici, tuttavia anche se nella pratica in realtà non si usa per la sua inefficienza, non c’è programmatore che non lo conosca. La problematica di ordinare un array è una problematica che spesso si deve affrontare, pensiamo ad esempio: fare la classifica di giocatori per punteggio fare la classifica di studenti per numero di assenze; fare la classifica di candidati per numero di voti… ORDINAMENTO SELECTION SORT (O NAIVE) Idea del funzionamento alla base del Selection sort [https://it.wikipedia.org/wiki/Selection_sort] L‘idea di base è semplice: si cercano successivamente i minimi dell’array. Questo algoritmo è iterativo, e in ogni iterazione “divide” l’array in due parti: la prima parte, ordinata; la seconda parte non-ordinata; Inizialmente la prima parte non conterrà alcun elemento. L’algoritmo continuerà a cercherà il minimo tra gli elementi della parte non-ordinata e lo scambierà con il primo elemento della parte non ordinata, andando così ad aumentare di uno la dimensione della parte ordinata. L’algoritmo termina quando la parte non-ordinata contiene un solo elemento, che sarà il massimo dell’array, e quindi l’array sarà completamente ordinato. Complessità computazionale Selection Sort Per chi conoscesse già cosa si intende con complessità computazionale, la complessità computazionale di questo algoritmo è O(n²). ORDINAMENTO SELECTION SORT PSEUDO CODICE procedure SelectionSort(a: lista dei numeri da ordinare){ for i = 0 to n - 1 { // cerco la posizione del minimo tra i non ordinati posmin ← i for j = (i + 1) to n { if a[j] < a[posmin] { posmin ← j } // if } // for i // se non è il 1° elemento dei non ordinati allora lo scambio con il 1° dei non ordinati if posmin != i { tmp ← a[i] a[i] ← a[posmin] a[posmin] ← tmp } // if } // for i } // procedure ORDINAMENTO BUBBLE SORT Selection sort, detto anche algoritmo per selezione o da alcuni sel-sort, è un algoritmo di ordinamento di un array: non particolarmente efficiente; facile da comprendere e implementare. L’algoritmo Bubble Sort è un tra i più noti algoritmi di ordinamento (sorting) di un array, che deve il suo nome al fatto che il metodo che utilizza ricorda un po’ le bolle d’aria che salgono nell’acqua. non particolarmente efficiente; facile da comprendere e implementare. ORDINAMENTO BUBBLE SORT Idea del funzionamento alla base del Bubble sort [https://it.wikipedia.org/wiki/Bubble_sort] L’idea di base del bubble sort è confrontare il contenuto di ogni cella dell’array con quello della cella seguente e se questi non rispettano l’ordine invertirli (si dovrà fare così per tutti i contenuti successivi a quello dell’ultima cella che non ha una cella successiva). Così facendo l’elemento maggiore dell’array alla fine della “passata” di confronti e eventuali scambi sarà salito lungo l’array fino a trovarsi in fondo all’array. Ripetendo il procedimento per tante volte quanti sono gli elementi dell’array (meno uno) l’array sarà ordinato. Il nome bubble sort nasce dal suo comportamento che ricorda quello delle bolle che risalgono dall’acqua. Complessità computazionale Bubble Sort Per chi conoscesse già cosa si intende con complessità computazionale, la complessità computazionale del Bubble Sort è O(n²) sia nel caso medio che nel caso peggiore, nel caso migliore con sentinella è O(n) altrimenti è O(n²). ORDINAMENTO BUBBLE SORT PSEUDO CODICE della versione originale dell'algoritmo: PSEUDO CODICE di una versione alternativa: procedure BubbleSort(A:lista elementi da ordinare){ procedure BubbleSort(A:lista elementi da ordinare) scambio ← true for i ← 0 to length(A)-2 { while scambio { for j ← i+1 to length(A)-1 { scambio ← false if A[j] < A[i] then { for i ← 0 to length(A)-1 { tmp = A[j] if A[i] > A[i+1] then { A[i] = A[j] tmp = A[i] A[j] = tmp A[i] = A[i+1] }// if A[i+1] = tmp }// for scambio ← true }// for }// if }// procedura }// for }// while }// procedura Questa versione, invece, sposta, ad ogni ciclo for esterno, l'elemento più piccolo all'estrema sinistra. Lo pseudocodice appena scritto sposta, ad ogni ciclo while, l'elemento più grande all'estrema destra. ORDINAMENTO BUBBLE SORT OTTIMIZZAZIONE 1 Le prestazioni del bubble sort possono essere leggermente migliorate tenendo conto del fatto che dopo la prima iterazione l'elemento più grande si troverà certamente nell'ultima posizione della lista, quella sua definitiva; alla seconda iterazione il secondo più grande si troverà in penultima posizione, quella sua definitiva, e così via. Ad ogni iterazione il ciclo dei confronti può accorciarsi di un passo rispetto al precedente evitando di scorrere ogni volta tutta la lista fino in fondo: all'n-esima iterazione si può quindi fare a meno di trattare gli ultimi n-1 elementi che ormai si trovano nella loro posizione definitiva. Possiamo rappresentare quanto detto con questo secondo pseudocodice: procedure BubbleSort(A:lista di elementi da ordinare){ scambio ← true n ← length(A) - 2 // l'indice parte da 0 e devo fermarmi al penultimo elemento, quindi devo togliere 2 while (scambio) { scambio ← false for i ← 0 to n { if (A[i] > A[i + 1]) then { //sostituire '>' con '' con '1 value ← A[i] insertionSortRicorsivo(A,n-1) j ← i-1 value ← A[n-1] while j >= 0 and A[j] > value { j ← n-2 A[j + 1] ← A[j] while (j>=0 and A[j]>value) { j ← j-1 A[j + 1] ← A[j] }// while j ← j-1 A[j+1] ← value; }// while }// for A[j+1] ← value }// procedura }// for }// procedura Per ordinare un array di dimensione n, A[0..n-1]: si ordina prima il sotto-array A[0..n-2] e poi si inserisce l'n-1-esimo elemento. Il sotto-array di un elemento (n==1) è già ordinato. ORDINAMENTO QUICK SORT Selection sort, detto anche algoritmo per selezione o da alcuni sel-sort, è un algoritmo di ordinamento di un array: non particolarmente efficiente; facile da comprendere e implementare. L’algoritmo Bubble Sort è un tra i più noti algoritmi di ordinamento (sorting) di un array, che deve il suo nome al fatto che il metodo che utilizza ricorda un po’ le bolle d’aria che salgono nell’acqua. non particolarmente efficiente; facile da comprendere e implementare. ORDINAMENTO QUICK SORT Idea del funzionamento alla base del Bubble sort [https://it.wikipedia.org/wiki/Bubble_sort] L’idea di base del bubble sort è confrontare il contenuto di ogni cella dell’array con quello della cella seguente e se questi non rispettano l’ordine invertirli (si dovrà fare così per tutti i contenuti successivi a quello dell’ultima cella che non ha una cella successiva). Così facendo l’elemento maggiore dell’array alla fine della “passata” di confronti e eventuali scambi sarà salito lungo l’array fino a trovarsi in fondo all’array. Ripetendo il procedimento per tante volte quanti sono gli elementi dell’array (meno uno) l’array sarà ordinato. Il nome bubble sort nasce dal suo comportamento che ricorda quello delle bolle che risalgono dall’acqua. Complessità computazionale Bubble Sort Per chi conoscesse già cosa si intende con complessità computazionale, la complessità computazionale del Bubble Sort è O(n²) sia nel caso medio che nel caso peggiore, nel caso migliore con sentinella è O(n) altrimenti è O(n²). ORDINAMENTO QUICK SORT PSEUDO CODICE della versione originale dell'algoritmo: PSEUDO CODICE di una versione alternativa: procedure BubbleSort(A:lista elementi da ordinare){ procedure BubbleSort(A:lista elementi da ordinare) scambio ← true for i ← 0 to length(A)-2 { while scambio { for j ← i+1 to length(A)-1 { scambio ← false if A[j] < A[i] then { for i ← 0 to length(A)-1 { tmp = A[j] if A[i] > A[i+1] then { A[i] = A[j] tmp = A[i] A[j] = tmp A[i] = A[i+1] }// if A[i+1] = tmp }// for scambio ← true }// for }// if }// procedura }// for }// while }// procedura Questa versione, invece, sposta, ad ogni ciclo for esterno, l'elemento più piccolo all'estrema sinistra. Lo pseudocodice appena scritto sposta, ad ogni ciclo while, l'elemento più grande all'estrema destra. ORDINAMENTO MERGE SORT Selection sort, detto anche algoritmo per selezione o da alcuni sel-sort, è un algoritmo di ordinamento di un array: non particolarmente efficiente; facile da comprendere e implementare. L’algoritmo Bubble Sort è un tra i più noti algoritmi di ordinamento (sorting) di un array, che deve il suo nome al fatto che il metodo che utilizza ricorda un po’ le bolle d’aria che salgono nell’acqua. non particolarmente efficiente; facile da comprendere e implementare. ORDINAMENTO MERGE SORT Idea del funzionamento alla base del Bubble sort [https://it.wikipedia.org/wiki/Bubble_sort] L’idea di base del bubble sort è confrontare il contenuto di ogni cella dell’array con quello della cella seguente e se questi non rispettano l’ordine invertirli (si dovrà fare così per tutti i contenuti successivi a quello dell’ultima cella che non ha una cella successiva). Così facendo l’elemento maggiore dell’array alla fine della “passata” di confronti e eventuali scambi sarà salito lungo l’array fino a trovarsi in fondo all’array. Ripetendo il procedimento per tante volte quanti sono gli elementi dell’array (meno uno) l’array sarà ordinato. Il nome bubble sort nasce dal suo comportamento che ricorda quello delle bolle che risalgono dall’acqua. Complessità computazionale Bubble Sort Per chi conoscesse già cosa si intende con complessità computazionale, la complessità computazionale del Bubble Sort è O(n²) sia nel caso medio che nel caso peggiore, nel caso migliore con sentinella è O(n) altrimenti è O(n²). ORDINAMENTO MERGE SORT PSEUDO CODICE della versione originale dell'algoritmo: PSEUDO CODICE di una versione alternativa: procedure BubbleSort(A:lista elementi da ordinare){ procedure BubbleSort(A:lista elementi da ordinare) scambio ← true for i ← 0 to length(A)-2 { while scambio { for j ← i+1 to length(A)-1 { scambio ← false if A[j] < A[i] then { for i ← 0 to length(A)-1 { tmp = A[j] if A[i] > A[i+1] then { A[i] = A[j] tmp = A[i] A[j] = tmp A[i] = A[i+1] }// if A[i+1] = tmp }// for scambio ← true }// for }// if }// procedura }// for }// while }// procedura Questa versione, invece, sposta, ad ogni ciclo for esterno, l'elemento più piccolo all'estrema sinistra. Lo pseudocodice appena scritto sposta, ad ogni ciclo while, l'elemento più grande all'estrema destra. ALBERI, GRAFI E VISITE ALBERI, GRAFI E VISITE AUTOMI A STATI FINITI AUTOMI A STATI FINITI PROGETTI E PUNTI DI VISTA PROGETTI E PUNTI DI VISTA SVILUPPO DAL PUNTO DI VISTA DELLA SOLUZIONE DEL PROBLEMA SVILUPPO DAL PUNTO DI VISTA DEI PROCESSI SVILUPPO DAL PUNTO DI VISTA DEGLI AMBIENTI INTEGRAZIONE DEI DIVERSI PUNTI DI VISTA