LabEx
로그인무료 가입

Java 를 이용한 재귀적 병합 정렬 구현

JavaBeginner
지금 연습하기

소개

병합 정렬 (Merge Sort) 은 배열 정렬을 위해 분할 정복 (Divide and Conquer) 기법을 사용하는 효율적이고 안정적인 정렬 알고리즘입니다. 이 Lab 에서는 재귀적 접근 방식을 사용하여 Java 에서 병합 정렬을 구현하는 방법을 배우게 됩니다.

병합 정렬 메서드 생성

int arrToSort[], startIdx, endIdx 세 개의 정수 매개변수를 갖는 mergeSort()라는 public static 메서드를 생성합니다. 배열 길이가 2 미만인지 확인한 다음 반환해야 합니다. 그렇지 않으면 배열의 중간 인덱스를 계산하고 배열을 왼쪽 및 오른쪽 절반으로 분할합니다. 왼쪽 및 오른쪽 절반도 재귀적으로 분할해야 합니다. 분할 후에는 정렬된 배열을 형성하기 위해 병합해야 합니다.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

Merge 메서드 생성

int arrToSort[], startIdx, midIdx, 및 endIdx의 네 가지 매개변수를 갖는 merge()라는 다른 public static 메서드를 생성합니다. 왼쪽 및 오른쪽 배열을 초기화해야 합니다. 그런 다음 각 배열의 요소를 비교하고 단일 배열로 병합하여 두 배열을 병합해야 합니다.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

병합 정렬 테스트

입력 배열을 정렬하는 코드를 작성하여 mergeSort() 메서드를 테스트해 보겠습니다. main 메서드를 생성합니다. 그런 다음, 정렬되지 않은 몇 개의 값을 가진 정수 배열을 선언합니다. mergeSort() 메서드를 호출하고 정렬되지 않은 배열을 전달합니다. 마지막으로, 정렬된 배열을 콘솔에 출력합니다. 이 단계의 코드 블록은 다음과 같습니다.

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

프로그램을 실행한 후 출력은 다음과 같아야 합니다: [0, 1, 2, 4, 6, 8].

빈 배열로 테스트

빈 배열에 대한 다른 테스트를 생성합니다. 빈 정수 배열을 선언합니다. mergeSort() 메서드를 호출하고 빈 배열을 전달합니다. 마지막으로, 정렬된 배열을 콘솔에 출력합니다. 이 단계의 코드 블록은 다음과 같습니다.

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

출력은 입력과 동일해야 합니다.

단일 요소 배열 테스트

단일 요소 배열로 테스트를 하나 더 생성합니다. 단일 요소 정수 배열을 선언합니다. mergeSort() 메서드를 호출하고 단일 요소 배열을 전달합니다. 마지막으로, 정렬된 배열을 콘솔에 출력합니다. 이 단계의 코드 블록은 다음과 같습니다.

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

출력은 입력과 동일해야 합니다.

음수 값으로 테스트

음수 정수로 구성된 배열에 대한 다른 테스트를 생성합니다. 일부 음수 정수를 포함하는 정수 배열을 선언합니다. mergeSort() 메서드를 호출하고 배열을 인수로 전달합니다. 마지막으로, 정렬된 배열을 콘솔에 출력합니다. 이 단계의 코드 블록은 다음과 같습니다.

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

프로그램을 실행한 후 출력은 다음과 같아야 합니다: [-9, -7, -1, 0, 2, 6, 8].

숫자가 아닌 요소로 테스트

비수치 요소의 배열을 정렬하여 다른 테스트를 생성합니다. 문자열 배열을 선언합니다. mergeSort() 메서드를 호출하고 배열을 인수로 전달합니다. 마지막으로, 정렬된 배열을 콘솔에 출력합니다. 이 단계의 코드 블록은 다음과 같습니다.

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

프로그램을 실행한 후 출력은 다음과 같아야 합니다: ['Bob', 'Christine', 'David', 'Emily', 'John'].

최종 소스 코드

다음은 병합 정렬 (Merge Sort) 의 최종 소스 코드입니다.

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //create an unsorted integer array
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //sort the integer array using Merge Sort
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrToSort));

       //create an empty integer array
       int[] emptyArr = {};
       //sort the empty array
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(emptyArr));

       //create a single-element array
       int[] singleElementArr = {7};
       //sort the single-element array
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(singleElementArr));

       //create a negative integer array
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //sort the negative integer array
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrWithNegatives));

       //create a string array
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //sort the string array
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(strsToSort));
   }
}

프로그램 실행

터미널을 사용하여 프로그램을 컴파일하고 실행합니다:

javac MergeSort.java && java MergeSort

요약

이 랩에서는 병합 정렬 (Merge Sort) 이 무엇인지, 어떻게 작동하는지, 그리고 Java 에서 어떻게 구현하는지 배웠습니다. 입력 배열을 분할하고 병합하기 위해 각각 mergeSort()와 merge()라는 두 개의 public static 메서드를 만들었습니다. 구현 후, 다양한 입력에 대해 테스트하고, 시간 및 공간 복잡도를 논의했으며, 기능성을 검증했습니다. 축하합니다! Java 에서 병합 정렬 랩을 성공적으로 완료했습니다.

관련 Java 코스
초보자를 위한 Java

초보자를 위한 Java

java
Java 프로그래밍 연습 문제

Java 프로그래밍 연습 문제

java
MyBatis 를 사용하여 수강 일정에 대량 데이터 삽입

MyBatis 를 사용하여 수강 일정에 대량 데이터 삽입

java