문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

이전 챌린지에서 실행시간이 O(n^2)인 간단하고 직관적인 정렬 알고리즘인 Insertion Sort를 다루었다. 이번 챌린지에서 분할 정복 알고리즘이라 불리는 Quicksort(또는 Partion Sort)를 다룬다. 이 챌린지는 단지 분할에 관련된 알고리즘의 수정 버전이다.

Step 1: Divide

어떤 중심 요소 p를 선택하고 정렬되지 않은 배열 arr을 세 개의 배열로 나눠라. 각각 left, right, equal이고 left의 요소는 p보다 작고, right의 요소는 p보다 크고 equal의 요소는 p와 같다.

Example

arr = [5, 7, 4, 3, 8]

이 챌린지에서 중심은 항상 arr의 인덱스 0의 값이며 5이다.
arr은 left = {4, 3}, equal = {5}, right = {7, 8}로 나누어 진다.
전부 한 곳에 모아서 {4, 3, 5, 7, 8}로 만든다. left와 right에 어떤 순서든지 있을 수 있는 유연한 체커가 있다. 예를 들면, {3, 4, 5, 8, 7}도 유효하다.
arr와 p = arr[0]이 주어지고, 위의 나누기 규칙을 사용해서 arr을 left, right, equal로 나눠라. 처음에 left의 요소, 다음은 equal의 요소, 다음은 right의 요소를 포함한 1차원 배열을 반환해라.

Function Description

quickSort 함수를 완성해라.
quickSort 함수는 아래와 같은 매개변수를 가지고 있다.

• int arr[n]: arr[0]이 중심 요소이다.

Returns

• int[n]: 위 규칙을 따른 정수형 배열

Constraints

• 1 <= n <= 1000
• -1000 <= arr[i] <= 1000
• 0 <= i < n
• 모든 요소는 유일하다.

Solved

문제의 예시를 따라서 푼다면 쉽게 해결할 수 있다.
먼저 left와 equal, right를 선언하고, equal은 arr[0]을 할당한다.

List<Integer> left = new ArrayList<>();
int equal = arr.get(0);
List<Integer> right = new ArrayList<>();

그리고 equal을 기준으로 arr의 요소를 left와 right에 담아준다.

for(int i = 1; i < arr.size(); i++){
	if(arr.get(i) > equal){
		right.add(arr.get(i));
	}else{
		left.add(arr.get(i));
	}
}

arr의 요소를 나눴다면 result 리스트를 생성하고 left, equal, right 순으로 result에 담는다. 그리고 result를 반환한다.

List<Integer> result = new ArrayList<>();

for(int i = 0; i < left.size(); i++){
	result.add(left.get(i));
}

result.add(equal);

for(int i = 0; i < right.size(); i++){
	result.add(right.get(i));
}

return result;

All Code

public static List<Integer> quickSort(List<Integer> arr) {
	List<Integer> left = new ArrayList<>();
	int equal = arr.get(0);
	List<Integer> right = new ArrayList<>();

	for(int i = 1; i < arr.size(); i++){
		if(arr.get(i) > equal){
			right.add(arr.get(i));
		}else{
			left.add(arr.get(i));
		}
	}

	List<Integer> result = new ArrayList<>();

	for(int i = 0; i < left.size(); i++){
		result.add(left.get(i));
	}

	result.add(equal);

	for(int i = 0; i < right.size(); i++){
		result.add(right.get(i));
	}

	return result;
}