Merge-sort in Java

Ogni programmatore deve inizialmente pensare allo schema/piano/architettura del lavoro futuro, altrimenti tutto finisce nel caos, nella completa anarchia. Come per ogni post, inizialmente hai bisogno di un piano, cominciamo.

• 1) Prendiamo l'argomento Merge sort per principianti.
• 2) Creeremo un'architettura e un piano per ulteriori lavori.
• 3) Lavoreremo e descriveremo tutte le parti del piano.
• 4) Controlliamo le prestazioni e la qualità.

• 2.1) Cos'è l'ordinamento Unisci.
• 2.2) Descrizione delle possibili firme.
• 2.3) Fai un esempio.
• 2.4) Descrivere l'implementazione in Java utilizzando un esempio.
• 2.5) Tutto in più.

Unisci: unisci l'ordinamento in Java

Implica il principio del “divide et impera”. Qual è l'idea e il suo significato?

1. Ordinamento.

   Dividiamo l'array in parti finché non è uguale a 1 elemento. Ogni 1 elemento viene ordinato.

2. Fusione.

   Unione di elementi ordinati.
   Basato sul principio di due mazzi di carte. Mettiamo 2 mazzi di carte sul tavolo con il loro valore in alto e la carta con il valore più basso viene posizionata nella terza pila di carte risultante. Alla fine, se finiamo le carte in un determinato mazzo, le spostiamo una per una nel mazzo risultante. Il risultato sarà una fusione di due array ordinati, un nuovo array ordinato.

Il tempo impiegato è O(n log2 n). L'ordinamento è considerato abbastanza veloce. Brevemente sulla complessità algoritmica, se qualcuno ne ha bisogno. Spesso puoi vedere funzioni come:

Sort(A, p, q);
Merge(A, p, q, r);

Si tratta più o meno della stessa cosa, solo collegata agli indici. Le variabili in essi contenute sono:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

Se queste variabili non vengono descritte, chi chiede di realizzare lui stesso una funzione del genere non sa cosa vuole. E dovrai setacciare Google per scoprire di cosa si tratta, probabilmente lo troverai, forse. Diamo un esempio del nostro ordinamento. C'è un array {6, 1, 3, 5, 2, 4, 7, 8}, se la sua lunghezza è maggiore di 1, lo dividiamo in 2 parti e otteniamo la parte sinistra {6, 1, 3, 5}e la parte destra {2, 4, 7, 8}. Continuiamo l'azione di divisione in 2 parti finché la sua lunghezza non è maggiore di 1. Di conseguenza, otteniamo un gruppo di array con una lunghezza di 1 elemento, vale a dire: {6} {1} {3} {5} {2} {4} {7} {8}. L'implementazione in Java è qualcosa del genere:

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

Successivamente è necessario unire questi array in 1. Come si fa? Per evitare di scorrere ogni array più volte, inseriamo gli indici di posizione per ogni array. Quindi eseguiremo un ciclo una volta, pari alla lunghezza della somma di questi due array. Prendi il primo e il secondo array, prendi il primo elemento, confronta l'elemento numero 1 nel primo array e l'elemento numero 1 nel secondo array ? Quello più piccolo viene inserito nell'array risultante. È importante qui che se prendiamo un elemento dal primo array, quando il ciclo passa, dovrebbe riferirsi al 2o elemento del primo array e al 1o elemento del secondo array. Per fare ciò, è necessario aumentare l'indice del secondo array di +1 e, durante il controllo, sottrarlo dal numero di ciclo, allo stesso modo per il primo array. È chiaro il motivo per cui farlo? Oppure non c'è niente di chiaro? :-) Ad esempio, ci sono 2 array: {1}{4}{8}e {3}{6}{7} E c'è un ciclo:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

Al primo passaggio del ciclo risulta che arrayC[1] = {1}: abbiamo preso questo elemento dal primo array. Quindi, durante il secondo ciclo, dobbiamo già confrontare l'elemento {4}e {3}, ma per fare ciò dobbiamo tenere conto degli indici di posizione e dell'offset di entrambi gli array, per questo li inseriamo.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

Ma non è tutto, devi tenere conto del fatto che alcuni array potrebbero terminare prima. Ad esempio, ci sono 3 array: {1}{3}{5}e {6}{7}{9} Il primo array terminerà prima che arrivi il secondo, per questo è necessario inserire un controllo e, in linea di principio, la funzione di unione è pronta.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

La cosa più difficile di questo ordinamento è il principio della transizione ricorsiva. Quelli. gettiamo il lato sinistro in ricorsione finché non diventa divisibile per 2, quindi lo svolgiamo all'indietro, a parole è molto complicato e confuso, ma quando provi a immaginare, se non è ancora chiaro, allora è un completo disastro. Prendiamo l'array: {2}{1}{4}{3}. La prima ricorsione di ordinamento lo dividerà in 2 parti ed eseguirà nuovamente la funzione con gli elementi 2-1 , poi di nuovo con gli elementi 2 e 1 , li restituirà a turno, quindi entreranno prima nella funzione di unione e arriverà 1-2 out , quindi la ricorsione tornerà indietro e getterà 4-3 nella fusione , poi 4 e 3 , dopodiché la fusione restituirà 3-4 , e solo allora la ricorsione si svolgerà nuovamente e 1-2 e 3-4 saranno inclusi nell'unione e l'array ordinato verrà restituito 1-2-3-4 . Bene, questo è tutto, l'ordinamento consiste di due funzioni.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

Se scrivi qualche tipo di main, otterrai qualcosa come:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

Per me questo ordinamento è stato un completo fallimento, c'erano un milione di domande, ma nessuna risposta, ho scavato in tutta Internet, riletto, guardato un sacco di video, ma come sempre ho trovato le risposte solo da solo. E solo quando ho iniziato a scrivere una soluzione completamente diversa da quella che lampeggia ovunque) Ma alla fine si è rivelata simile a tutte le altre))) L'ordinamento è in realtà il più semplice, l'importante è presentarlo in modo interattivo in azione, e tutto andrà a posto se ci prendi la mano, farò un video)))) Finora, questo è tutto ciò che mi bastava: Merge sort Merge-sort La cosa più importante è sempre fare un piano da l'inizio. È meglio aspettare un po' e pensare prima di iniziare a fare qualsiasi cosa. Potrebbe volerci più tempo, ma emergeranno una comprensione e una soluzione piuttosto che doverla riscrivere un paio di volte e trovare delle stampelle. Grazie a tutti per il vostro tempo, buona fortuna e buon umore. ) PS: Le critiche, buone e cattive, così come le domande sono benvenute. )))