Divide and Conquer

분할 정복

문제를 나눌 수 없을때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

• 하양식 접근법이다
• 일반적으로 재귀함수로 구현을 많이한다
• 문제를 잘게 쪼갤때, 부분문제는 중복되지 않는다
• Memoization기법을 사용하지 않는다

ex) 병합 정렬, 퀵 정렬

퀵정렬

pivot 설정 (첫번째 요소나 가운데 요소 설정)

• 피봇을 기준으로 작은값을 왼쪽, 큰값을 오른쪽으로 정렬
• 재귀로 다시 왼쪽, 오른쪽에 있는 값을에 대해 요소가 하나가 될때까지 진행
• 모두 정렬이 끝난 후 정렬된 배열을 리턴 -> 모든 요소들이 합쳐진다

public static void quickSort(int[] arr, int left, int right) {
	int i, j, pivot, tmp;
	if (left < right) {
		i = left;   j = right;
		pivot = arr[(left+right)/2];
		//분할 과정
		while (i < j) {
			while (arr[j] > pivot)
				j--;
			while (arr[i] < pivot)
				i++;
			if (i < j) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
				j--;
			}
		}
		//정렬 과정
		quickSort(arr, left, i - 1);
		quickSort(arr, i + 1, right);
	}
}

Stream 활용 List 퀵소트

public static List<Integer> quicksort_stream(List<Integer> list){
	if (list.size() <= 1)
		return list;
	int pivot = list.get(list.size()/2);
	List<Integer> Left = new LinkedList<>();
	List<Integer> Right = new LinkedList<>();
	List<Integer> Same = new LinkedList<>();

	for (int val : list){
		if (val < pivot)
			Left.add(val);
		else if (val > pivot)
			Right.add(val);
		else
			Same.add(val);
	}
	return Stream.of(quicksort_stream(Left), Same ,quicksort_stream(Right))
			.flatMap(Collection::stream)
			.collect(Collectors.toList());
}

병합정렬 merge Sort

알고리즘 구현
리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다
결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다
복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다

mergeSplit함수 만들기

만약 리스트 개수가 한개이면 해당 값 리턴 그렇지 않으면, 리스트를 앞뒤, 두개로 나누기
기준은 mid를 기준으로 쪼갠다
left = mergeSplit(앞)
right = mergeSplit(뒤)
merget(left, right)

merge 함수 만들기

리스트 변수 하나 만들기 (정렬된 요소 저장)
left_idx, right_idx = 0
while left_idx < left.length && right_idx < right.length

• 만약 left_idx나 right_idx가 이미 left, right를 다 순회했다면, 반대쪽 데이터를 전부다 넣는다
• 왼쪽이 작으면 왼쪽걸 넣고 left_idx++
• 오른쪽이 작으면 오른쪽걸 넣고 right_idx++

코드

최적화 된 코드

private static void mergesort(int[] arr)
{
	split(arr, 0, arr.length-1);
}

private static void split(int[] arr, int start, int end){
	if (start < end) {
		int mid = (start + end) / 2;
		split(arr, start, mid);
		split(arr, mid + 1, end);
		merge(arr, start, mid, end);
	}
}

private static void merge(int[] arr, int start, int mid, int end){
	int[] temp = new int[arr.length];
	int left = start;
	int right = mid+1;
	int idx = start;

	while (left <= mid && right <= end){
		if (arr[left] < arr[right])
			temp[idx++] = arr[left++];
		else
			temp[idx++] = arr[right++];
	}
	while (left <= mid)
		temp[idx++] = arr[left++];
	while (right <= end)
		temp[idx++] = arr[right++];

	for (int i = start; i < idx; i++)
		arr[i] = temp[i];
}

Arrays.copyOfRange를 이용한 풀이

• 계속해서 새로운 배열을 만들어서 쪼개므로 메모리 사용량이 높다

private static int[] mergeSort(int[] arr)
{
	if (arr.length <= 1)
		return arr;
	int mid = arr.length / 2;
	//mid 전까지 취하는 Arrays.copyOfRange이다 따라서 mid번째는 포함 x
	int[] left_arr = mergeSort(Arrays.copyOfRange(arr, 0, mid));
	int[] right_arr =  mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
	int[] sorted_arr = new int[arr.length];

	int left = 0; int idx = 0; int right = 0;
	while (left < left_arr.length && right < right_arr.length) {
		if (left_arr[left] < right_arr[right])
			sorted_arr[idx++] = left_arr[left++];
		else
			sorted_arr[idx++] = right_arr[right++];
	}
	while (left < left_arr.length)
		sorted_arr[idx++] = left_arr[left++];

	while (right < right_arr.length)
		sorted_arr[idx++] = right_arr[right++];

	return sorted_arr;

}