얼거스 개발 일지

📖 책 정보

---

1. 분할 정복

문제 해결 방법 중에서

가장 유명한 재귀적 기술인

분할 정복 dividid and conquer 전략!

분할 정복 전략은 문제에 바로 적용할 수 있는 단순한 알고리즘이 아니다.

문제를 풀기 위한 방법론에 가깝다.

문제를 분할 정복 전략으로 풀기 위해서는 다음의 두 가지 단계를 거쳐야 한다.

1. 기본 단계를 해결한다. 이 부분은 가능한 한 간단한 문제이어야만 한다.

2. 문제가 기본 단계가 될 때 까지 나누거나 작게 만든다.

2. 퀵 정렬

선택 정렬보다 훨씬 빠르고,

실제로 자주 사용되는 정렬 알고리즘이다.

예를 들면,

C언어에는 qsort라는 함수가 있는데, 바로 퀵 정렬을 구현한 함수이다.

퀵 정렬도 마찬가지로 분할 정복 전략으로 만들어진 알고리즘이다.

배열을 정렬 해본다고 가정해보면,

우선

정렬하는데 가장 간단한 배열은

" 비어있는 배열 " , " 원소가 하나인 배열 " 이다.

이러한 비어있는 배열이나, 원소가 하나인 배열이 기본 단계가 된다.

이때는 배열을 있는 그대로 반환하면 된다.

배열이 긴 경우,

배열을 기본 단계가 될 때까지 나누면 된다.

퀵 정렬의 동작은 다음과 같다.

1 . 배열에서 원소를 아무거나 하나 고른다.      이 원소가 기준 원소 pivot 가 됨.

2 . 모든 원소를 기준 원소보다 작은 원소와 큰 원소로 분류한다.      이것을 분할 partitioning 이라고 한다.

이제 배열은 기준 원소보다 작은 숫자로 이루어진 하위 배열, 기준 원소 , 기준 원소보다 큰 숫자들로 이루어진 하위 배열로 구성되었다.

하위 배열들은 정렬되어있지 않기 때문에,

각각의 하위 배열에 대해서도 퀵 정렬을 호출한 후 결과를 합친다.

java 코드 구현

배열을 새로 만들지 않고, 포인터를 사용해서 배열의 크기를 지정.

배열 범위 내에서 기준 값인 pivot보다 큰 값이 나오면 지나가고, pivot보다 작은 값이 나오면 i를 1증가시킨 후 i와 교체하며 pivot보다 작은 값들을 배열의 왼쪽 구간에 두게 된다.

i는 탐색이 끝난 후 pivot의 위치가 될 값으로, 탐색중엔 pivot보다 작은값과 큰 값을 구분하는 용도로 사용된다.

탐색 중 i의 위치는 pivot보다 작은 값들 중 마지막으로 정리 된 값의 위치이다.

private int[] quickSort(int[] arr) {
    quickSortRecursive(arr, 0, arr.length - 1);

    return arr;
}
private void quickSortRecursive(int[] arr, int left, int right) {
    if (left >= right)
        return;

    int pivotPos = partition(arr, left, right);
	
    quickSortRecursive(arr, left, pivotPos - 1);
    quickSortRecursive(arr, pivotPos + 1, right);
}

// 정렬 구현 
// 기준점 : 가장 오른쪽 요소
// 왼쪽 끝에서부터 pivot과 비교하며 정렬
private int partition(int[] arr, int left, int right) {
    int pivot = arr[right]; // 가장 오른쪽 요소를 기준값으로 사용

    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }

	// pivot 제자리로.
    int pivotPos = i + 1;
    swap(arr, pivotPos, right);

    return pivotPos;
}

실행 확인!

 [ arr ]___________🚩  [1, 2, 3, 4, 5, 6, 7, 7, 8, 9]

처음 왼쪽 구간 정렬 구현 묘사