분할정복

이진검색 재귀

1. 자료의 중앙에 있는 원소를 고른다.
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
3. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 종료한다.
4. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
5. 찾고자 하는 값을 찾을 때까지 1.~4.의 과정을 반복한다.

package day0322_분할정복;

public class 분할정복04_이진검색_재귀 {
	static int[] arr;
	static int key;

	public static void main(String[] args) {
		// 정렬된 상태라고 가정
		arr = new int[] { 2, 4, 6, 8, 9, 17, 28 };
		key = 4;
		
		System.out.println(binarySearch(0, arr.length-1));
	}

	// 이진검색을 하는 이유는요!
	// 이거 이안에 들었나~(boolean) / 들었다면 어디에 들었나~(int)
	// 인자값으로 무엇을 들고가야하나 (경계의 시작점과 끝점을)
	public static boolean binarySearch(int st, int ed) {
		//기저조건(못찾았다)
		if(st > ed) return false;
		
		int mid = (st + ed) / 2; //정수값
		
		//같다면
		if(arr[mid] == key) return true;
		//크다면 (왼쪽구간으로)
		else if(arr[mid] > key) return binarySearch(st, mid-1);
		//작다면 (오른쪽구간으로)
		else return binarySearch(mid+1, ed);
	}
}
//
true
만약 key값이 없는 값이라면 false출력

이진검색 API

package day0322_분할정복;

import java.util.Arrays;

public class 분할정복05_이진검색_API {
	static int[] arr;
	static int key;

	public static void main(String[] args) {
		// 정렬된 상태라고 가정
		arr = new int[] { 2, 4, 6, 8, 9, 17, 28 };
		key = 8;
		//있는 key값을 찾으면 해당 인덱스를 반환해주고
		//없는 key값을 찾으면 음수를 반환하는거 같은데 규칙을 모르겠다.
		//무슨 규칙이 있는거 같긴한데 ... 무엇이지?
		System.out.println(Arrays.binarySearch(arr, key));
		
	}
}
//
3

병합정렬

package day0322_분할정복;

import java.util.Arrays;

public class 병합정렬 {
    public static void main(String[] args) {
        int[] arr = new int[] {69, 10, 30, 2, 16, 8, 31, 22};
        mergeSort(arr); // 병합 정렬 수행
        System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
    }

    // 병합 정렬 메소드
    public static void mergeSort(int[] arr) {
        // 배열이 null이거나 길이가 2보다 작은 경우
        if (arr == null || arr.length < 2) {
            System.out.println("배열이 없거나 짧아요");
            return;
        }
        sort(arr, 0, arr.length - 1); // 배열을 분할하고 정렬하는 메소드 호출
    }

    // 분할 및 정렬하는 메소드
    private static void sort(int[] arr, int left, int right) {
        // 배열의 길이가 1인 경우
        if (left >= right) {
            return;
        }
        int mid = (left +right) / 2; // 배열을 분할하기 위한 중간 지점 계산
        sort(arr, left, mid); // 왼쪽 부분 배열 정렬
        sort(arr, mid + 1, right); // 오른쪽 부분 배열 정렬
        merge(arr, left, mid, right); // 정렬된 부분 배열 병합
    }

    // 병합 메소드
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 병합할 때 사용할 임시 배열 생성
        int i = left, j = mid + 1, k = 0; // i는 왼쪽 부분 배열의 시작 인덱스, j는 오른쪽 부분 배열의 시작 인덱스, k는 임시 배열의 인덱스
        // 왼쪽과 오른쪽 부분 배열을 비교하여 임시 배열에 정렬된 상태로 삽입
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 왼쪽 부분 배열에 남은 요소들을 임시 배열에 삽입
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 오른쪽 부분 배열에 남은 요소들을 임시 배열에 삽입
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 임시 배열에 있는 요소들을 원래 배열에 정렬된 상태로 복사
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }
}

퀵정렬_로무토파티션

주어진 배열을 두 개로 분할하고, 각각을 정렬한다.

병합정렬과 다른 점

1. 병합 정렬은 그냥 두 부분으로 나누는 반면에, 퀵 정렬은 분할할 때, 기준 아이템(pivot item)중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.
2. 각 부분 정렬이 끝난 후, 병합정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요로 하지 않는다.

동작 과정

1. 정렬한 배열 입력
2. 임의의 한 점을 pivot으로 선정(Partition 방법)
   pivot보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동
3. 정렬할 범위가 0이나 1이 될 때까지 분할 정복

package day0322_분할정복;

import java.util.Arrays;

public class 퀵정렬_로무토파티션 {
    public static void main(String[] args) {
        int[] arr = {3,1,6,12,78,34,7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // [1, 3, 6, 7, 12, 34, 78]
    }

    // 퀵정렬을 구현하는 메소드
    private static void quickSort(int[] arr, int left, int right) {
        // 배열이 null이거나 빈 배열일 경우
        if (arr == null || arr.length == 0) { 
            return; // 정렬할 필요가 없으므로 바로 리턴
        }

        // left가 right보다 작은 경우
        if (left < right) {
            // 배열을 분할하는 기준 인덱스를 구함
            int pivotIndex = partition(arr, left, right);
            // pivot을 기준으로 왼쪽 부분배열 퀵정렬 수행
            quickSort(arr, left, pivotIndex - 1);
            // pivot을 기준으로 오른쪽 부분배열 퀵정렬 수행
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    // 배열을 분할하는 기준 인덱스를 구하는 메소드
    public static int partition(int[] arr, int left, int right) {
        // pivot을 가장 오른쪽 값으로 설정
        int pivot = arr[right];
        int i = left - 1; // i를 왼쪽 끝으로 설정
        // left부터 right - 1까지 반복
        for (int j = left; j < right; j++) {
            // 현재 값이 pivot보다 작거나 같은 경우
            if (arr[j] <= pivot) {
                i++; // i를 1 증가시킴
                swap(arr, i, j); // i와 j를 swap함
            }
        }
        swap(arr, i + 1, right); // pivot을 i + 1과 swap함
        return i + 1; // i + 1을 pivot으로 설정하여 리턴
    }

    // 배열에서 두 인덱스의 값을 서로 바꾸는 메소드
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}