Tri par fusion en Java

Chaque programmeur doit d'abord réfléchir au schéma/plan/architecture des travaux futurs, sinon tout se termine dans le désordre, dans l'anarchie complète. Comme pour tout article, vous avez d’abord besoin d’un plan, commençons.

• 1) Prenons le sujet du tri par fusion pour les débutants.
• 2) Nous créerons une architecture et un plan pour les travaux ultérieurs.
• 3) Nous étudierons et décrirons toutes les parties du plan.
• 4) Vérifions les performances et la qualité.

• 2.1) Qu'est-ce que le tri par fusion.
• 2.2) Description des signatures possibles.
• 2.3) Donnez un exemple.
• 2.4) Décrivez l'implémentation en Java à l'aide d'un exemple.
• 2.5) Tout ce qui est en plus.

Fusionner - trier par fusion en Java

Implique le principe de « diviser pour mieux régner ». Quelle est l’idée et sa signification ?

1. Tri.

   Nous divisons le tableau en parties jusqu'à ce qu'il soit égal à 1 élément. Chaque élément est trié.

2. Fusionnement.

   Fusionner des éléments triés.
   Basé sur le principe de deux jeux de cartes. Nous plaçons 2 jeux de cartes sur la table avec leurs valeurs augmentées, et la carte la plus basse est placée dans la troisième pile de cartes résultante. En fin de compte, si nous manquons de cartes dans un certain deck, nous les déplaçons une par une vers le deck résultant. Le résultat sera une fusion de deux tableaux triés, un nouveau tableau trié.

Le temps passé est O(n log2 n). Le tri est considéré comme assez rapide. En bref sur la complexité algorithmique, si quelqu'un en a besoin. Vous pouvez souvent voir des fonctions telles que :

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

C'est à peu près la même chose, uniquement liée aux index. Les variables qu'ils contiennent sont :

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

Si ces variables ne sont pas décrites, alors celui qui demande à réaliser lui-même une telle fonction ne sait pas ce qu'il veut. Et il faudra parcourir Google pour savoir de quoi il s’agit, vous le trouverez probablement, peut-être. Donnons un exemple de notre tri. Il existe un tableau {6, 1, 3, 5, 2, 4, 7, 8}, si sa longueur est supérieure à 1, alors nous le divisons en 2 parties et obtenons la partie gauche {6, 1, 3, 5}et la partie droite {2, 4, 7, 8}. On continue l'action de diviser en 2 parties jusqu'à ce que sa longueur soit supérieure à 1. En conséquence, on obtient un tas de tableaux d'une longueur de 1 élément, à savoir : {6} {1} {3} {5} {2} {4} {7} {8}. L'implémentation en Java ressemble à ceci :

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);
    }

Ensuite, vous devez fusionner ces tableaux en 1. Comment cela se fait-il ? Pour éviter de parcourir chaque tableau plusieurs fois, entrons les indices de position pour chaque tableau. Ensuite, nous parcourrons une fois une boucle, égale à la longueur de la somme de ces deux tableaux. Prendre le premier tableau et le deuxième tableau, et prendre le premier élément, comparer l'élément numéro 1 dans le premier tableau et l'élément numéro 1 dans le deuxième tableau ? Le plus petit est placé dans le tableau résultant. Il est important ici que si nous prenons un élément du premier tableau, alors lorsque la boucle passe, elle doit faire référence au 2ème élément du premier tableau et au 1er élément du deuxième tableau. Pour ce faire, vous devez augmenter l'indice du deuxième tableau de +1 et, lors de la vérification, le soustraire du numéro de cycle, de même pour le premier tableau. Est-il clair pourquoi faire cela ? Ou rien n'est clair du tout ? :-) Par exemple, il y a 2 tableaux : {1}{4}{8}et {3}{6}{7} Et il y a une boucle :

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

Au premier passage de la boucle, il s'avère que arrayC[1] = {1}: nous avons pris cet élément du premier tableau. Ensuite, en parcourant la deuxième boucle, nous devons déjà comparer l'élément {4}et {3}, mais pour ce faire, nous devons prendre en compte les indices de position et le décalage des deux tableaux, pour cela nous les saisissons.

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++;
	}
}

Mais ce n’est pas tout, vous devez garder à l’esprit que certains tableaux peuvent se terminer plus tôt. Par exemple, il y a 3 tableaux : {1}{3}{5}et {6}{7}{9} Le premier tableau se terminera avant l'arrivée du second, pour cela vous devez saisir un chèque et, en principe, la fonction de fusion est prête.

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 chose la plus difficile dans ce tri est le principe de transition récursive. Ceux. nous jetons le côté gauche en récursion jusqu'à ce qu'il soit divisible par 2, puis le déroulons, en mots, c'est très compliqué et déroutant, mais quand vous essayez d'imaginer, si ce n'est pas encore clair, alors c'est un gâchis complet. Prenons le tableau : {2}{1}{4}{3}. La première récursion de tri le divisera en 2 parties et exécutera à nouveau la fonction avec les éléments 2-1 , puis à nouveau avec les éléments 2 et 1 , les renverra tour à tour, ils entreront donc d'abord dans la fonction de fusion, et 1-2 viendra out , alors la récursion reviendra et lancera 4-3 dans la fusion , puis 4 et 3 , après quoi la fusion reviendra 3-4 , et alors seulement la récursion reviendra en arrière et 1-2 et 3-4 seront sera inclus dans la fusion et le tableau trié sera renvoyé 1-2-3-4 . Eh bien, c'est tout, le tri se compose de deux fonctions.

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

Si vous écrivez une sorte de principal, vous obtiendrez quelque chose comme :

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] + " ");
        }
    }

Pour moi, ce tri a été un échec complet, il y avait un million de questions, mais pas de réponses, j'ai fouillé tout Internet, relu, regardé un tas de vidéos, mais comme toujours, je n'ai trouvé les réponses que moi-même. Et seulement quand j'ai commencé à écrire une solution complètement différente de celle qui clignote partout) Mais au final elle s'est avérée similaire à toutes les autres))) Le tri est en fait le plus simple, l'essentiel est de le présenter de manière interactive en action, et tout se met en place si vous comprenez, je ferai une vidéo)))) Jusqu'à présent, c'est tout ce dont j'ai assez : Tri par fusion Fusion-tri Le plus important est de toujours faire un plan à partir de le début. Il vaut mieux attendre un peu et réfléchir avant de commencer quoi que ce soit. Cela prendra peut-être plus de temps, mais une compréhension et une solution émergeront plutôt que d’avoir à le réécrire plusieurs fois et à trouver des béquilles. Merci à tous pour votre temps, bonne chance et bonne humeur. ) PS : Les critiques, bonnes et mauvaises, ainsi que les questions sont les bienvenues. )))