Java의 병합 정렬

모든 프로그래머는 처음에 향후 작업의 계획/계획/아키텍처를 충분히 생각해야 합니다. 그렇지 않으면 모든 것이 엉망이 되어 완전한 무정부 상태가 됩니다. 모든 게시물과 마찬가지로 처음에는 계획이 필요합니다. 시작해 보겠습니다.

• 1) 초보자를 위한 병합 정렬 주제를 살펴보겠습니다.
• 2) 추가 작업을 위한 아키텍처와 계획을 수립하겠습니다.
• 3) 우리는 계획의 모든 부분을 검토하고 설명할 것입니다.
• 4) 성능과 품질을 확인해보자.

• 2.1) 병합 정렬이란 무엇입니까?
• 2.2) 가능한 서명에 대한 설명.
• 2.3) 예를 들어보세요.
• 2.4) 예제를 사용하여 Java 구현을 설명합니다.
• 2.5) 추가 사항.

병합 - Java의 병합 정렬

'분할 정복'의 원칙을 내포하고 있습니다. 아이디어와 그 의미는 무엇입니까?

1. 정렬.

   배열이 1개의 요소와 같아질 때까지 여러 부분으로 나눕니다. 1개의 요소마다 정렬됩니다.

2. 합병.

   정렬된 요소를 병합합니다.
   두 개의 카드 덱의 원리를 기반으로 합니다. 우리는 값이 높은 카드 2덱을 테이블 위에 놓고, 가장 낮은 카드가 세 번째 카드 더미에 놓입니다. 궁극적으로 특정 덱의 카드가 부족하면 해당 카드를 결과 덱으로 하나씩 옮깁니다. 결과는 두 개의 정렬된 배열, 즉 하나의 새로운 정렬된 배열이 병합된 것입니다.

소요된 시간은 O(n log2 n)입니다. 정렬은 매우 빠른 것으로 간주됩니다. 필요한 경우 알고리즘의 복잡성에 대해 간략하게 설명합니다. 다음과 같은 기능을 자주 볼 수 있습니다.

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

이것은 인덱스에만 연결되는 것과 거의 같습니다. 그 안에 있는 변수는 다음과 같습니다.

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

이러한 변수가 설명되지 않으면 그러한 기능을 직접 만들어달라고 요청하는 사람은 자신이 원하는 것이 무엇인지 알 수 없습니다. 그리고 그것이 무엇인지 알아내기 위해 구글을 뒤져야 할 것입니다. 아마도 찾을 수 있을 것입니다. 정렬의 예를 들어 보겠습니다. 배열이 있는데 {6, 1, 3, 5, 2, 4, 7, 8}길이가 1보다 크면 이를 2개 부분으로 나누고 왼쪽 부분 {6, 1, 3, 5}과 오른쪽 부분을 얻습니다 {2, 4, 7, 8}. 길이가 1보다 커질 때까지 두 부분으로 나누는 작업을 계속합니다. 결과적으로 길이가 1 요소인 배열 묶음을 얻습니다 {6} {1} {3} {5} {2} {4} {7} {8}. Java에서의 구현은 다음과 같습니다.

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

다음으로 이 배열을 1로 병합해야 합니다. 이 작업은 어떻게 수행됩니까? 각 배열을 여러 번 거치는 것을 피하기 위해 각 배열에 대한 위치 인덱스를 입력해 보겠습니다. 그런 다음 이 두 배열의 합 길이와 동일한 루프를 한 번 통과합니다. 첫 번째 배열과 두 번째 배열을 가져와 첫 번째 요소를 가져와 첫 번째 배열의 요소 번호 1 과 두 번째 배열의 요소 번호 1을 비교합니까 ? 더 작은 것이 결과 배열에 배치됩니다. 여기서 중요한 점은 첫 번째 배열에서 요소를 가져온 다음 루프가 통과할 때 첫 번째 배열의 두 번째 요소와 두 번째 배열의 첫 번째 요소를 참조해야 한다는 것입니다. 이렇게 하려면 두 번째 배열의 인덱스를 +1만큼 늘려야 하며, 확인할 때 첫 번째 배열과 마찬가지로 사이클 번호에서 이를 빼야 합니다. 왜 이렇게 해야 하는지 분명합니까? 아니면 전혀 명확한 것이 없습니까? :-) 예를 들어, 2개의 배열이 있습니다: {1}{4}{8}그리고 {3}{6}{7} 사이클이 있습니다:

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

루프의 첫 번째 패스에서 다음과 같은 결과가 나타납니다 arrayC[1] = {1}. 첫 번째 배열에서 이 요소를 가져왔습니다. {4}그런 다음 두 번째 루프를 통과할 때 이미 요소 와 를 비교해야 {3}하지만 이를 위해서는 두 배열의 위치 인덱스와 오프셋을 고려해야 합니다. 이를 위해 입력합니다.

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

하지만 그게 전부는 아닙니다. 일부 배열은 더 일찍 종료될 수 있다는 점을 고려해야 합니다. 예를 들어, 3개의 배열이 있습니다. {1}{3}{5}첫 {6}{7}{9} 번째 배열은 두 번째 배열이 도착하기 전에 종료됩니다. 이를 위해서는 검사를 입력해야 하며 원칙적으로 병합 기능이 준비됩니다.

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;

이 정렬에서 가장 어려운 점은 재귀 전환의 원리입니다. 저것들. 왼쪽을 2로 나눌 수 있을 때까지 재귀에 던졌다가 다시 되돌립니다. 말로 하면 매우 복잡하고 혼란스럽습니다. 하지만 상상하려고 하면 아직 명확하지 않으면 완전히 엉망이 됩니다. 배열을 살펴보겠습니다: {2}{1}{4}{3}. 첫 번째 정렬 재귀는 이를 두 부분으로 나누고 요소 2-1 로 함수를 다시 실행한 다음 다시 요소 2 와 1 로 차례로 반환하므로 병합 함수에 먼저 들어가고 1-2가 올 것입니다. out 이면 재귀가 다시 돌아와서 4-3 을 merge 에 던진 다음 4 와 3 을 던지고 그 후에 병합이 3-4 를 반환 한 다음에만 재귀가 다시 돌아가고 1-2 와 3-4 가 됩니다. 병합에 포함되고 정렬된 배열은 1-2-3-4 로 반환됩니다 . 그게 다입니다. 정렬은 두 가지 기능으로 구성됩니다.

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

어떤 종류의 주요 내용을 적어 보면 다음과 같은 결과가 나타납니다.

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

나에게이 정렬은 완전히 실패했고 질문이 백만 개 있었지만 답변이 없었고 인터넷 전체를 파헤치고 다시 읽고 많은 비디오를 보았지만 언제나 그렇듯이 스스로 답을 찾았습니다. 그리고 모든 곳에서 깜박이는 솔루션과 완전히 다른 솔루션을 작성하기 시작했을 때만) 그러나 결국에는 다른 모든 솔루션과 비슷한 것으로 나타났습니다.))) 정렬은 실제로 가장 간단하고 가장 중요한 것은 실제로 대화식으로 표시하는 것입니다. 익숙해지면 모든 것이 제자리에 놓이게 됩니다. 동영상을 만들겠습니다)))) 지금까지는 그게 제가 할 수 있는 전부입니다: 병합 정렬 병합 정렬 가장 중요한 것은 항상 다음에서 계획을 세우는 것입니다. 시작. 어떤 일을 시작하기 전에 조금 기다렸다가 생각하는 것이 좋습니다. 시간은 더 걸릴 수 있지만 몇 번이고 다시 작성하고 목발을 짚는 것보다 이해와 해결책이 나올 것이다. 시간을 내주신 모든 분들께 감사드립니다. 행운과 좋은 기분을 가져보세요. ) 추신: 좋은 점과 나쁜 점에 대한 비판과 질문은 매우 환영합니다. )))