[알고리즘] 병합, 퀵 정렬

병합 정렬 - Merge Sort

• 병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.
• 시간 복잡도는 O(nlogn)이다.

정렬 과정

1. 분할

• 입력 배열을 반으로 나눈다.
• 배열의 길이가 1이 될 때까지 나눈다.
• 길이가 1인 배열은 이미 정렬된 상태로 간주한다.

2. 정복

• 나뉘어진 배열들을 쌍으로 병합하며 정렬한다.
• 병합 시, 두 배열의 첫 번째 요소부터 비교하여 작은 값을 결과 배열에 추가한다.
• 두 배열의 값이 모두 결과 배열로 이동할 때까지 이 과정을 반복한다.

3. 병합

• 정렬된 배열들을 병합하여 하나의 완전한 배열을 만든다.

  
  

2개의 그룹을 병합하는 과정

투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.
왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 결과 값을 배열에 추가하고 포인터를 오른쪽으로 한 칸 이동시킨다.

구현 예제

// 내가 짠 병합정렬
public static int[] MergeSort(int[] arr) {
	if (arr.length <= 1) {
    	return arr;
	}

    int[] newArr = new int[arr.length];
    int middle = arr.length / 2;

    int[] leftArr = MergeSort(Arrays.copyOfRange(arr, 0, middle));
    int[] rightArr = MergeSort(Arrays.copyOfRange(arr, middle, arr.length));

    int leftIdx = 0;
    int rightIdx = 0;
    int count = 0;

    while (leftIdx < leftArr.length && rightIdx < rightArr.length) {
    	if (leftArr[leftIdx] < rightArr[rightIdx]) {
        	newArr[count++] = leftArr[leftIdx++];
		} else {
        	newArr[count++] = rightArr[rightIdx++];
		}
	}

    while (leftIdx < leftArr.length) {
    	newArr[count++] = leftArr[leftIdx++];
	}

	while (rightIdx < rightArr.length) {
    	newArr[count++] = rightArr[rightIdx++];
	}

    return newArr;
}

// 지피티가 알려준 원본 배열 정렬
public static void mergeSort(int arr[], int start, int end) {
    if (start >= end) {
    	return;
	}

    int middle = start + (end - start) / 2;

    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);

    int[] temp = new int[end - start + 1];

	int leftIdx = start;
    int rightIdx = middle + 1;
    int tempIdx = 0;

	while (leftIdx <= middle && rightIdx <= end) {
		if (arr[leftIdx] <= arr[rightIdx]) {
        	temp[tempIdx++] = arr[leftIdx++];
		} else {
        	temp[tempIdx++] = arr[rightIdx++];
    	}
    }

	while (leftIdx <= middle) {
    	temp[tempIdx++] = arr[leftIdx++];
    }

	while (rightIdx <= end) {
    	temp[tempIdx++] = arr[rightIdx++];
    }

	System.arraycopy(temp, 0, arr, start, temp.length);
}

빠른 정렬 - Quick Sort

• 퀵 정렬은 기준값을 선정해 해당 값보다 큰 데이터와 작은 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.
• 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 복잡도는 O(nlogn)이다.

정렬 방식

1. 기준 선택

   퀵 정렬은 배열의 요소 중 하나를 기준으로 선택한다. 일반적으로 아래의 방법들이 사용된다.

• 첫 번째 요소
• 마지막 요소
• 중간값
• 랜덤 요소

2. 분할

   배열을 기준의 중심으로 두 개의 부분 배열로 나눈다.

• 왼쪽 부분 배열 : 기준보다 작은 값
• 오른쪽 부분 배열 : 기준보다 큰 값

3. 재귀적 정렬

• 나뉜 두 부분에 대해 같은 작업( 기준 선택 -> 분할 )을 재귀적으로 반복한다.
• 이 부분은 배열의 크기가 1 이하가 될 때까지 계속된다.

4. 결합

• 퀵 정렬은 분할 과정에서 이미 배열이 정렬되기 때문에 별도의 결합 단계가 필요하지 않다.

구현 예제

// 내가 구현한 방식
private static void quickSort(int[] arr, int left, int right) {
	if (left < right) {
        int pivotIndex = partition(arr, left, right);

        quickSort(arr, left, pivotIndex - 1);  // 피벗 왼쪽 정렬
    	quickSort(arr, pivotIndex + 1, right); // 피벗 오른쪽 정렬
	}
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int originRight = right;
    right--;

	while (left <= right) {
		while (left <= right && arr[left] < pivot) {
        	left++;
        }

		while (left <= right && arr[right] > pivot) {
        	right--;
        }

		if (left <= right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        	left++;
        	right--;
    	}
    }

	if (left < arr.length) {
        int temp = arr[left];
        arr[left] = arr[originRight];
    	arr[originRight] = temp;
    }

	return left;
}

// 지피티가 추천해준 방법
private static void quickSort(int[] arr, int left, int right) {
	if (left < right) {
        int pivotIndex = partition(arr, left, right);

        quickSort(arr, left, pivotIndex);  
    	quickSort(arr, pivotIndex + 1, right); 
	}
}

// Hoare Partition Scheme
private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left - 1;
    int j = right + 1;

	while (true) {
		do {
        	i++;
        } while (arr[i] < pivot);

		do {
        	j--;
        } while (arr[j] > pivot);

		if (i >= j) {
        	return j;
        }

        int temp = arr[i];
        arr[i] = arr[j];
    	arr[j] = temp;
	}
}

마무리

흠.. 재귀를 쓰면서 정렬 과정을 따라서 구현하려다 보니 가끔 오류가 발생했다.
로그 찍어보면서 값 이상하게 들어가는 부분 찾으면서 계산하니 머리가 아프다....

아직 재귀에 덜 익숙해진것 같다.. 문제를 많이 풀고 재귀 활용을 조금씩 하다보면 괜찮아지겠지..