합병 정렬

JAVA로 작성되었습니다.

합병 정렬

• 분할정복을 이용한 정렬방법
• 배열을 한개의 조각이 될 때까지 쪼개고 두개 (1, 1)를 서로 비교,
  4개(2, 2)를 서로 비교, 8개(4, 4)를 서로 비교 하는 방법
• 비교한 결과를 저장하기 위해 임시의 배열이 추가로 필요하다.

 

1. 인자로 들어온 left가 right보다 작은지 검증한다 (같다면 숫자가 하나이기에)
2. 중간값을 결정한다. ((오른쪽 값 - 왼쪽 값) / 2 + left)
3. 중간값과 왼쪽 배열, 중간값 오른쪽 배열을 다시 분할하는 재귀함수를 호출한다.
4. left + 1 = right 가 될때까지 분할을 수행한다.
   (분할해야 하는 배열의 요소가 2개)
   (3개인 경우 2개와 1개로 쪼개지고 왼쪽의 2개만 쪼개져 서로 비교를 진행하고
   다시 돌아와 2개와 1개의 비교를 진행한다.)
5. 1개 두개를 비교했으면 요소가 2개인 정렬된 배열 2개를 다시 비교하고
   비교된 4개의 요소는 다시 다른 4개의 요소와 비교되어 원본 배열의 크기와
   같아질 때 까지 비교를 진행한다.
6. 비교를 진행하는 방법은 왼쪽 배열의 첫번째 값과 오른쪽 배열의 첫번째 값을
   비교하는 것으로 시작한다.
   1. 첫번째 값이 오른쪽이 더 작다면 오른쪽의 첫번째 값을 임시배열의 처음 값에
      집어 넣는다. 그리고 왼쪽의 인덱스는 그대로 두고 오른쪽 배열의
      인덱스를 + 1 하여 오른쪽의 두번째 값과 왼쪽의 첫번째 값을 비교한다.
   2. 이번에도 오른쪽 배열의 숫자가 더 작다면 위와 같은 방법으로 임시 배열에
      오른쪽의 값을 집어 넣고 오른쪽 배열의 인덱스만을 증가시켜
      다음 숫자를 비교한다.
7. 비교가 끝나면 왼쪽 배열과 오른쪽 배열중 하나는 배열의 끝에 도달하였을텐데
   그때 인덱스가 끝에 위치하지 않은 배열의 나머지를 모두 임시의 배열에 추가한다.
   1. 비교를 진행하기 전 왼쪽과 오른쪽 배열은 각자 정렬이 완료되어있는 상태이다.
      그러므로 한쪽의 모든 값보다 작다면 반대쪽의 기존에 정렬된 숫자를 그대로
      뒤에 넣는 것이 맞는것.
8. 서로의 비교, 정렬이 끝나고 인자로 들어온 left값부터 right값 까지의 원본배열에
   임시 배열의 값들을 집어넣어준다.
   • 6부터 10까지의 값을 비교하여 임시배열에 저장하였다면 임시배열의 크기는
     5이고 그 5개의 값을 원본 배열의 인덱스 6 - 10에 넣어주는 것.
9. 재귀함수가 끝나고 원본을 반 나눈 배열 두개를 비교하고 나 정렬이 종료된다.

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MergeSort {
    public List<Integer> list_merge(List<Integer> list, int left, int right) {
        // 리스트 를 반으로 쪼갠다.
        // 재귀 함수 발동! (반절의 왼쪽, 반절의 오른쪽)
        // 재귀 함수가 반환하는 두 리스트를 하나씩 비교하여 정렬한다.
//        System.out.println("new!");
        int mid = 0;
        if (left < right) {
            mid = ((right - left) / 2) + left;
//            System.out.println("left: " + left + "\nright: " + right + "\nmid: " + mid);
            list = list_merge(list, left, mid);
            list = list_merge(list, mid + 1, right);

            List<Integer> temp = new ArrayList<Integer>();
            int temp1 = left, temp2 = mid + 1;
            while (temp1 <= mid && temp2 <= right) {
//                System.out.println("index: " + temp1 + " value: " + list.get(temp1));
//                System.out.println("index: " + temp2 + " value: " + list.get(temp2));
                if (list.get(temp1) <= list.get(temp2)) {
                    temp.add(list.get(temp1));
                    temp1++;
                } else if (list.get(temp1) > list.get(temp2)) {
                    temp.add(list.get(temp2));
                    temp2++;
                }
            }
            if (temp1 == mid + 1) {
                for (int i = temp2; i <= right; i++) {
                    temp.add(list.get(i));
                }
            } else if (temp2 == right + 1) {
                for (int i = temp1; i <= mid; i++) {
                    temp.add(list.get(i));
                }
            }
            for (int i = left, temp_cnt = 0;
                 i <= right && temp_cnt < temp.size();
                 i++, temp_cnt++) {
                list.set(i, temp.get(temp_cnt));
            }
        }
//        System.out.println(list + "\n");
        return list;
    }
    public void accuracy_test(List<Integer> origin, List<Integer> sorted) {
        int cnt = 0, temp1 = 0;
        List<Integer> temp = new ArrayList<Integer>(sorted);

        for (int i = temp1; i < origin.size(); i++) {
            for (int j = 0; j < temp.size(); j++) {
                if (temp.get(j).equals(origin.get(i))) {
                    if (i < origin.size() - 1) {
                        temp1++;
                    }
                    temp.remove(j);
                    j = temp.size();
                    cnt++;
                }
            }
        }
        System.out.println("Matching rate: " + (cnt / origin.size()) * 100 + "%");
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        MergeSort mergeSort = new MergeSort();
        Random random = new Random();


        for (int i = 0; i < 10; i++) {
            list.add(random.nextInt(10));
        }
        List<Integer> origin_copy = new ArrayList<Integer>(list);
        System.out.println("before: " + origin_copy);

        list = mergeSort.list_merge(list, 0, list.size() - 1);
        System.out.println("after: " + list);

        mergeSort.accuracy_test(origin_copy, list);
    }
}