Mesclar classificação em Java

Todo programador deve inicialmente pensar no esquema/plano/arquitetura do trabalho futuro, caso contrário tudo acabará em uma bagunça, com completa anarquia. Como acontece com qualquer postagem, inicialmente você precisa de um plano, vamos começar.

• 1) Vamos abordar o tópico Merge sort para iniciantes.
• 2) Criaremos uma arquitetura e um plano para trabalhos futuros.
• 3) Trabalharemos e descreveremos todas as partes do plano.
• 4) Vamos verificar o desempenho e a qualidade.

• 2.1) O que é classificação por mesclagem.
• 2.2) Descrição de possíveis assinaturas.
• 2.3) Dê um exemplo.
• 2.4) Descreva a implementação em Java usando um exemplo.
• 2.5) Qualquer coisa extra.

Mesclar - classificação de mesclagem em Java

Implica o princípio de “dividir para conquistar”. Qual é a ideia e seu significado?

1. Ordenação.

   Dividimos o array em partes até que seja igual a 1 elemento. Cada 1 elemento é classificado.

2. Fusão.

   Mesclando elementos classificados.
   Baseado no princípio de dois baralhos de cartas. Colocamos 2 baralhos de cartas na mesa com seus valores para cima, e a carta de menor valor é colocada na terceira pilha de cartas resultante. Em última análise, se ficarmos sem cartas num determinado baralho, movemo-las uma a uma para o baralho resultante. O resultado será uma fusão de duas matrizes classificadas, uma nova matriz classificada.

O tempo gasto é O(n log2 n). A classificação é considerada bastante rápida. Resumidamente sobre a complexidade algorítmica, se alguém precisar. Muitas vezes você pode ver funções como:

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

É quase a mesma coisa, apenas vinculado a índices. As variáveis ​​neles são:

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

Se essas variáveis ​​​​não forem descritas, então quem pede para fazer ele mesmo tal função não sabe o que quer. E você terá que vasculhar o Google para descobrir o que é, provavelmente você encontrará, talvez. Vamos dar um exemplo de nossa classificação. Existe um array {6, 1, 3, 5, 2, 4, 7, 8}, se seu comprimento for maior que 1, então o dividimos em 2 partes e obtemos a parte esquerda {6, 1, 3, 5}e a parte direita {2, 4, 7, 8}. Continuamos a ação de dividir em 2 partes até que seu comprimento seja maior que 1. Como resultado, obtemos um monte de arrays com comprimento de 1 elemento, a saber: {6} {1} {3} {5} {2} {4} {7} {8}. A implementação em Java é mais ou menos assim:

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

Em seguida você precisa mesclar esses arrays em 1. Como isso é feito? Para evitar passar por cada array várias vezes, vamos inserir índices de posição para cada array. Então passaremos por um loop uma vez, igual ao comprimento da soma dessas duas matrizes. Pegue a primeira matriz e a segunda matriz e pegue o primeiro elemento, compare o elemento número 1 na primeira matriz e o elemento número 1 na segunda matriz ? O menor é colocado na matriz resultante. É importante aqui que se pegarmos um elemento do primeiro array, então quando o loop passar, ele deverá se referir ao segundo elemento do primeiro array e ao primeiro elemento do segundo array. Para fazer isso, você precisa aumentar o índice do segundo array em +1 e, ao verificar, subtraí-lo do número do ciclo, da mesma forma para o primeiro array. Está claro por que fazer isso? Ou não está nada claro? :-) Por exemplo, existem 2 arrays: {1}{4}{8}e {3}{6}{7} E há um loop:

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

Na primeira passagem do loop, acontece que arrayC[1] = {1}: pegamos esse elemento do primeiro array. Então, ao passar pelo segundo loop, já devemos comparar o elemento {4}e {3}, mas para isso precisamos levar em consideração os índices de posição e o deslocamento de ambos os arrays, para isso os inserimos.

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

Mas não é só isso, é preciso levar em consideração que algum array pode terminar mais cedo. Por exemplo, existem 3 arrays: {1}{3}{5}e {6}{7}{9} O primeiro array terminará antes que o segundo chegue, para isso é necessário inserir uma verificação e, em princípio, a função de mesclagem está 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;

A coisa mais difícil nessa classificação é o princípio da transição de recursão. Aqueles. jogamos o lado esquerdo em recursão até que seja divisível por 2, e depois desenrolamos de volta, em palavras é muito complicado e confuso, mas quando você tenta imaginar, se ainda não está claro, então é uma bagunça completa. Vamos pegar a matriz: {2}{1}{4}{3}. A primeira recursão de classificação irá dividi-lo em 2 partes e executar a função novamente com os elementos 2-1 , depois novamente com os elementos 2 e 1 , retorná-los por sua vez, para que eles entrem na função de mesclagem primeiro e 1-2 venha out , então a recursão retornará e lançará 4-3 na mesclagem , depois 4 e 3 , após o que a mesclagem retornará 3-4 , e só então a recursão girará novamente e 1-2 e 3-4 irão será incluído na mesclagem e a matriz classificada será retornada 1-2-3-4 . Bem, isso é tudo, a classificação consiste em duas funções.

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

Se você escrever algum tipo de main, obterá algo como:

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

Para mim essa triagem foi um fracasso total, foram um milhão de perguntas, mas sem respostas, vasculhei toda a internet, reli, assisti um monte de vídeos, mas como sempre, só encontrei as respostas sozinho. E só quando comecei a escrever uma solução completamente diferente daquela que pisca em todos os lugares) Mas no final ficou semelhante a todas as outras))) A classificação é na verdade a mais simples, o principal é apresentá-la interativamente em ação, e tudo se encaixa se você pegar o jeito, farei um vídeo)))) Até agora, é tudo o que tenho o suficiente: Merge sort Merge-sort O mais importante é sempre fazer um plano a partir de o início. É melhor esperar um pouco e pensar antes de começar a fazer qualquer coisa. Pode levar mais tempo, mas uma compreensão e uma solução aparecerão, em vez de ter que reescrever algumas vezes e inventar muletas. Obrigado a todos pelo seu tempo, boa sorte e bom humor. ) PS: Críticas, boas e ruins, bem como dúvidas são muito bem vindas. )))