Il metodo di ordinamento Quicksort

tramite: O2O
Difficoltà: difficile
18

Introduzione

Chiunque di noi (programmatori) si è trovato davanti alla necessità di dover ordinare dei dati, e sappiamo che, siano essi pochi o molti, il coefficiente di difficoltà per risolvere il problema rimane lo stesso. Proprio per agevolare la vita a chiunque si trova in questa situazione in questa guida mostreremo un metodo abbastanza rapido per ordinare dei dati: il metodo di ordinamento quicksort. Questo metodo si basa su un'algoritmo abbastanza complesso che però velocizzerà di molto le nostre operazioni. Quindi non vi resta altro che leggere questa guida per apprendere il metodo quicksort, partendo però dal considerare come questo metodo sia per programmatori esperti e pertanto alcuni passaggi sono stati dati per scontati all'interno di questa guida.

28

Occorrente

  • Un vettore di oltre 100 elementi
38

Scomporre il problema

Il metodo quicksort si basa sulla scomposizione del problema, in pieno stile cartesiano: il problema principale viene scisso in problemi più piccoli che devono essere risolti uno alla volta per portare al risultato finale desiderato, ovvero l'ordinamento di una grossa mole di dati. Il metodo quicksort è quindi un metodo di tipo ricorsivo.

48

Iniziare il partizionamento

Vediamo come implementare in linguaggio Java, il metodo di partizionamento. Di seguito, ne illustro una sua possibile implementazione:

public int partiziona (int[] vettore, int fine, int inizio){

int pivot = vettore[fine];
while (fine < inizio) {
while (vettore[fine] < pivot)
fine++;
while (vettore[inizio] > pivot)
inizio--;
scambia (vettore, fine, inizio);
}
return fine;
}.

Continua la lettura
58

Iniziare a scomporre i dati

Analizzando il metodo partiziona, scegliamo temporaneamente come elemento pivot l'ultimo elemento del vettore. Successivamente, l'idea di base, è di posizionare tutti gli elementi più grandi di questo Pivot alla sua destra e tutti gli elementi più piccoli alla sua sinistra. Questo metodo restituirà, all'ambiente chiamante, un valore intero che sarà il nuovo elemento Pivot su cui effettuare una nuova partizione.

68

Iniziare la ricorsione

Il passo conclusivo è di implementare la parte ricorsiva dell'algoritmo. Ne propongo di seguito una sua implementazione:

public void quickSort (int[] vettore, int fine, int inizio){

if (fine >= inizio) return;

int indicePivot = partiziona (vettore, fine, inizio);
quickSort (vettore, fine, indicePivot);
quickSort (vettore, indicePivot+1, inizio);
}.

78

Attenzione al pivot

In sostanza, nel metodo ricorsivo QuickSort, una volta ottenuto il valore di indice del nuovo elemento scelto come Pivot, si procede a considerare quella parte (o partizione) del vettore, delimitata appunto dall'elemento Pivot. Si procederà fino a quando non sarà più possibile ottenere ulteriori partizioni. Ottenute le partizioni desiderate non vi resterà che unirle con l'apposito comando (che non mi fermo a spiegare) e avrete ordinato i vostri dati.

88

Consigli

Non dimenticare mai:
  • Capito il principio di funzionamento, ideate una vostra implementazione

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Programmazione

Come implementare il BubbleSort

L'attività di realizzazione di piccoli o complessi progetti software è molto problematica e difficile. Così, potrete finire la vostra attività di ordinare i dati da trattare. Sono tante le tecniche per farlo. Ce ne sono di più efficienti e di meno;...
Programmazione

Come ordinare una LinkedList di stringhe

Una delle operazioni più richieste, nell'utilizzo di una vasta collezione di dati, è di fornire una loro rappresentazione chiara ed ordinata, specie quando si ha da manipolare delle stringhe. L'utente, generalmente, preferisce utilizzare dati che seguano...
Programmazione

Come ordinare una lista in Java

Java in campo informatico rappresenta senza dubbio uno dei sistemi di programmazione più diffusi e conosciuti. Ordinare una lista in Java potrebbe sembrare un'operazione piuttosto complicata, in modo particolare per i meno esperti del settore. In realtà...
Programmazione

Come inserire musica di sottofondo in Java

Che sia lavoro, che sia relax o qualsiasi altro momento una bella canzone di sottofondo non guasta mai e ascoltando le nostre preferite ci fa felici, ecco che oggi andiamo a vedere come inserire musica di sottofondo in Java. Per prima cosa andiamo a creare...
Programmazione

Come svuotare slot machine

Spesso le slot machine possono rivelarsi vere e proprie trappole o persino creare dipendenza. Quelle luci accattivanti e quelle musiche ipnotiche possono indurre un giocatore alle prime armi ad avvicinarsi e a non staccarsi più se non a portafoglio vuoto....
Programmazione

Come spostare un file in Java

Spostare i file in Java potrebbe sembrare inizialmente un'operazione complessa, ma con un po' di attenzione potremo farlo semplicemente da soli, senza dunque rivolgerci ad un tecnico informatico specializzato. Così facendo, non solo potremo imparare...
Programmazione

Come implementare gli alberi in C

In informatica per rappresentare dei dati si usano le strutture dati. Le strutture dati sono dei metodi per organizzare dati. A seconda delle operazioni che vogliamo fare su un insieme di dati, possiamo scegliere una struttura dati invece che un'altra....
Programmazione

HTML: impostare il colore di sfondo

L' html è un potente linguaggio testuale che serve per la creazione di pagine Web. Nato moltissimi anni fa, viene ancora oggi utilizzato come principale linguaggio e metodo per la creazione di siti web, durante gli anni è stato inoltre migliorato innumerevoli...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.