Introduzione a Merge Sort in Java
Il programma per Merge Sort in Java è uno degli algoritmi più utilizzati ed efficienti. Unisci ordinamento si basa sulla tecnica di divisione e conquista che prevede la divisione di un determinato problema in più sottoproblemi e la risoluzione indipendente di ogni sottoproblema. Quando i sottoproblemi vengono risolti, uniamo i loro risultati per ottenere la soluzione finale al problema. L'algoritmo di tipo merge può essere implementato usando la ricorsione in quanto implica lavorare con i sottoproblemi piuttosto che con il problema principale.
Come funziona il Merge Sort?
Consideriamo un array non ordinato che deve essere ordinato utilizzando l'algoritmo di ordinamento di tipo merge. Ecco i passaggi necessari per ordinare un array con valori: 18, 8, 4, 13, 10, 12, 7 e 11:
- Il primo passo prevede la ricerca di un elemento pivot in base al quale il nostro array di input verrà suddiviso in sottoarray.
- Consideriamo che l'elemento 13 è scelto come perno, quindi l'array originale sarà diviso in due sottoarray. Il primo subarray conterrà 18, 8, 4, 13 e il secondo subarray conterrà gli elementi rimanenti 10, 12, 7, 11.
- I subarray ottenuti nel passaggio 2 vengono ulteriormente suddivisi come nel passaggio 1 e questo continua.
- Una volta che l'array principale è diviso in sottoarray con elementi singoli, iniziamo nuovamente a unire questi sottoarray in modo tale che gli elementi uniti siano in ordine.
- Ecco come funziona l'attuale divisione e conquista:
Programma per Merge Sort in Java
Ecco un esempio di codice che mostra l'implementazione dell'ordinamento di tipo merge in Java:
Codice:
package com.edubca.sorting;
public class MergeSort (
private int() array;
private int() tempMergedArr;
private int length;
public static void main(String a())(
int() inputArr = (18, 8, 4, 13, 10, 12, 7, 11);
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr)(
System.out.print(i + " ");
)
)
public void sort(int inputArr()) (
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int(length);
performMergeSort(0, length - 1);
)
private void performMergeSort(int lowerIndex, int higherIndex) (
if (lowerIndex < higherIndex) (
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
)
)
private void mergeData (int lowerIndex, int middle, int higherIndex) (
for (int i = lowerIndex; i <= higherIndex; i++) (
tempMergedArr(i) = array(i);
)
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) (
if (tempMergedArr(i) <= tempMergedArr(j)) (
array(k) = tempMergedArr(i);
i++;
) else (
array(k) = tempMergedArr(j);
j++;
)
k++;
)
while (i <= middle) (
array(k) = tempMergedArr(i);
k++;
i++;
)
)
)
Il codice sopra produce un array ordinato come output.
Produzione:
Quando dovremmo usare il Merge Sort?
Unisci ordinamento può essere utilizzato nei seguenti scenari:
- Quando la struttura dei dati da ordinare non supporta l'accesso casuale, l'ordinamento di unione può essere utile ed efficiente.
- Quando è richiesto un elevato livello di parallelismo, è possibile utilizzare l'ordinamento unione in quanto diversi sottoproblemi possono essere risolti in modo indipendente utilizzando più processi in esecuzione in parallelo.
- Unire l'ordinamento è più veloce quando si lavora con elenchi collegati poiché i puntatori possono essere facilmente modificati durante l'unione degli elenchi.
- Unisci ordinamento può essere considerato un ordinamento stabile, il che significa che lo stesso elemento in un array mantiene le posizioni originali l'uno rispetto all'altro. Nei casi in cui è richiesta un'elevata stabilità, si può andare per unire l'ordinamento.
Analisi di complessità di Merge Sort
Di seguito la complessità dell'analisi dei punti di tipo merge:
- L'unione dell'ordinamento è un algoritmo ricorsivo e la sua complessità temporale è O (n * log n) in tutti e tre i casi (peggiore, migliore e media) poiché l'ordinamento di unione divide l'array in due metà uguali e impiega un tempo lineare per unirle.
- La complessità spaziale di tipo merge è O (n) mentre opera sull'approccio ricorsivo. Pertanto, l'ordinamento per unione può essere considerato un algoritmo veloce, efficiente in termini di spazio e tempo.
Confronto di Merge Sort con altri algoritmi
I seguenti punti confrontano l'unione dell'ordinamento con altri algoritmi:
- L'ordinamento dell'heap ha la stessa complessità temporale dell'ordinamento di tipo merge, ma richiede solo lo spazio ausiliario O (1) invece di unire O (n) dell'ordinamento. Quindi l'ordinamento heap è più efficiente in termini di spazio rispetto all'unione ordinamento.
- Le implementazioni di Ordinamento rapido in genere superano l'ordinamento di tipo merge per l'ordinamento di array basati su RAM.
- Unisci ordinamento supera gli algoritmi di ordinamento rapido e di heap quando si lavora con l'elenco collegato poiché i puntatori possono essere facilmente modificati.
Programma di conclusione per Merge Sort in Java
Dall'articolo, si è concluso che il tipo di unione è un concetto importante da capire quando si tratta di algoritmi.
Articoli consigliati
Questa è una guida al programma per unire l'ordinamento in Java. Qui discutiamo di come dovrebbe funzionare, il suo utilizzo, il programma di Merge Sort, ecc. Puoi anche consultare i nostri altri articoli correlati per saperne di più-
- Unisci ordinamento in Java
- Unisci gli algoritmi di ordinamento in Java
- Heap Ordina in C
- Ordinamento dell'heap in Java
- Strumenti di distribuzione Java
- Ordinamento dell'heap in Python
- Algoritmi di ordinamento rapido in Java
- I 6 migliori algoritmi di ordinamento in JavaScript
- Primi 6 algoritmi di ordinamento in Python