Merge Sort Program in Java: differenza tra Merge Sort e Quicksort

Introduzione al programma Merge Sort in JAVA

Come suggerisce il nome, il programma di ordinamento merge in JAVA è un algoritmo di ordinamento. È stato classicamente concettualizzato come l'algoritmo divide et impera in JAVA. Il programma merge sort in Java funziona scomponendo ricorsivamente un array di input in due o più dei suoi sottoproblemi costitutivi finché questi non sono abbastanza semplici da essere risolti direttamente.

I sottoproblemi costitutivi possono essere simili o in qualche modo correlati al problema genitore. Le singole soluzioni a ciascun sottoproblema vengono quindi combinate per ottenere la soluzione al problema originario del genitore.

Come funziona il programma Merge Sort in Java?

Come ripetuto in precedenza, il programma di ordinamento unione in JAVA è un algoritmo divide et impera. È un ordinamento stabile, il che significa che gli elementi dell'array mantengono le loro posizioni originali l'uno rispetto all'altro durante il processo di ordinamento.

• Dividere: In questo passaggio, un array di input viene diviso nelle sue due metà costituenti. Questo passaggio viene ripetuto continuamente per tutti i mezzi array risultanti fino a quando non ci sono più mezzi array da dividere ulteriormente.
• Conquista: in questo passaggio, gli array divisi vengono ordinati e uniti dal basso verso l'alto per raggiungere l'array ordinato finale.

Differenza tra Quicksort e Merge Sort Program in Java

Sebbene funzionalmente simili, è necessario porre un'enfasi pertinente sulla differenza fondamentale tra quicksort e mergesort in JAVA.

• Meccanismo : Quicksort è un algoritmo di ordinamento interno e sul posto, mentre il mergesort è un algoritmo di ordinamento esterno e fuori posto. In Quicksort, gli elementi vengono ordinati in base a un elemento chiave noto come pivot. Il pivot è generalmente il valore medio in una matrice di input. Gli elementi con un valore inferiore al pivot vengono spinti sul lato sinistro del pivot, mentre gli elementi con un valore maggiore sul lato destro del pivot. Qui, il lato sinistro è indicato come la partizione sinistra e il lato destro è indicato come la partizione destra. Al contrario, mergesort divide ripetutamente un array in due sottoarray (n/2) finché non rimane un solo elemento. Quindi combina i sottoarray per formare l'array ordinato.
• Applicazione: mentre quicksort è adatto per piccoli array, mergesort funziona con qualsiasi array, indipendentemente dalle sue dimensioni.
• Velocità : nel caso di Quicksort, più piccolo è il set di dati, più veloce sarà l'algoritmo. Mergesort, d'altra parte, funziona a una velocità costante per tutti i set di dati.
• Requisiti di spazio e utilizzo della memoria: come accennato in precedenza, il mergesort è un algoritmo di ordinamento esterno e fuori luogo. La sua complessità spaziale è O (n). Pertanto, richiede una memoria aggiuntiva di (O (n)) per ordinare l'array ausiliario.

Leggi anche: Tipi di letterali in Java con esempi

Analisi della complessità temporale del programma Merge Sort in JAVA

Il programma merge sort in JAVA ha una complessità temporale di O (n*log n). Secondo Binary Search, ogni volta che un numero è diviso a metà in ogni passaggio, può essere rappresentato dalla funzione logaritmica 'log n'. Il numero di passi (al massimo) può essere rappresentato da log n +1. Il centro di ogni sottoarray è O (1).

Pertanto, per unire i sottoarray, sarà richiesto un tempo di esecuzione di O (n). Quindi, il tempo totale per il programma di ordinamento unione in JAVA diventa n (log n +1). Ciò equivale a una complessità temporale di O (n*log n) in tutti e tre i casi (peggiore, medio e migliore) poiché l'ordinamento di unione richiede sempre tempo lineare per unire due metà.

Impara i corsi di software online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Riassumendo

Proprio come i dati ordinati per gli esseri umani sono logicamente validi e più facili da comprendere, gli array ordinati sono più gestibili con cui i computer possono lavorare. È qui che il programma di ordinamento unione in JAVA si rivela vantaggioso. È un algoritmo di ordinamento efficiente, generico e basato sul confronto.

Se sei interessato a saperne di più su Java, lo sviluppo di software full-stack, dai un'occhiata al programma Executive PG di upGrad & IIIT-B in Full-stack Software Development, progettato per i professionisti che lavorano e offre oltre 500 ore di formazione rigorosa, 9+ progetti e incarichi, stato di Alumni IIIT-B, progetti pratici pratici e assistenza sul lavoro con le migliori aziende.