Imparare gli algoritmi

Capitolo 5. Smistamento senza cappello

Questo lavoro è stato tradotto utilizzando l'AI. Siamo lieti di ricevere il tuo feedback e i tuoi commenti: [e-mail]

In questo capitolo imparerai:

• Gli algoritmi di ordinamento basati sul confronto richiedono due operazioni fondamentali:

  • less(i,j) determina se A[i] < A[j].

  • swap(i,j) scambia i contenuti di A[i] eA[j].

• Come fornire una funzione di confronto durante l'ordinamento; ad esempio, puoi ordinare i valori interi o le stringhe in ordine decrescente. La funzione comparatore può anche ordinare strutture di dati complesse senza un ordine predefinito; ad esempio, non è chiaro come ordinare un insieme di punti bidimensionali (x, y).

• Come identificare gli algoritmi di ordinamento O(^N2) inefficienti, come Insertion Sort e Selection Sort, dalla struttura del loro codice.

• Laricorsione, in cui una funzione può richiamare se stessa. Questo concetto fondamentale dell'informatica è alla base della strategia divide et impera per risolvere i problemi.

• Come Merge Sort e Quicksort possono ordinare un array di N valori in O(N logN) utilizzando il metodo divide et impera. Anche l'Heap Sort garantisce O(N log N).

• Come Tim Sort combina l'Insertion Sort e le funzionalità di Merge Sort per implementare l'algoritmo di ordinamento predefinito di Python con una garanzia di O(N log N).

In questo capitolo presento degli algoritmi che riordinano gli N valori di un array in modo che siano in ordine crescente. Organizzare ...