문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴합니다.
조건
- sort 메서드 사용 금지
- 퀵 정렬을 구현
- 오름차순으로 정렬
해결과정
퀵 정렬을 정확하게 모르기 때문에 구현할 수가 없어 퀵 정렬 방법만 검색하여 참고한 후 코드는 직접 구현하였습니다.
퀵 정렬은 pivot을 기준으로 작은 수들, 큰 수들을 각각 새로운 배열에 넣는 과정을 반복하여 정렬하는 방식입니다.
시간복잡도는 O(nlog n) 에서 최악의 경우 O(n^2) 입니다.
검색한 퀵 정렬의 개념을 토대로 재귀를 이용하여 간단하게 로직을 구현했습니다.
pivot은 주로 맨 끝 요소를 기준으로 하는 것으로 보여서 입력받은 맨끝요소를 pivot으로 하고
배열의 나머지 요소를 순회하면서 작은 수와 큰 수를 각각 나눠 리스트에 집어넣습니다.
(배열이 아닌 리스트를 사용한 이유는?
배열은 사이즈를 알고 있어야 생성할 수 있는데 pivot을 기준으로 큰 수가 몇 개이고 작은 수가 몇 개인지 순회하기 전까진 알 수 없어
번거롭더라도 사이즈가 가변하는 리스트에 넣은 후 순회를 마치면 toArray로 배열로 변환해주었습니다.)
그 후에 작은 수 배열을 재귀로 집어넣고 큰 수 배열도 마찬가지로 재귀에 집어넣습니다.
재귀 브레이크 포인트로 입력받은 배열의 길이가 1이하일 경우는 그대로 리턴하고 2일 경우는 정렬 후 리턴하도록 했습니다.
마지막으로 배열을 작은 수 배열 + pivot + 큰 수 배열 순으로 붙여서 결과 배열을 만든 후 리턴하였습니다.
코드
public int[] quickSort(int[] arr) {
if (arr.length <= 1) {
return arr;
}
if (arr.length == 2) {
if (arr[0] > arr[1]) {
int a = arr[0];
arr[0] = arr[1];
arr[1] = a;
}
return arr;
}
int[] answer = new int[arr.length];
List<Integer> smallNums = new ArrayList<>();
List<Integer> bigNums = new ArrayList<>();
int pivot = arr[arr.length - 1];
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
smallNums.add(arr[i]);
} else bigNums.add(arr[i]);
}
int[] smallArr = quickSort(smallNums.stream().mapToInt(Integer::intValue).toArray());
int[] bigArr = quickSort(bigNums.stream().mapToInt(Integer::intValue).toArray());
System.arraycopy(smallArr, 0, answer, 0, smallArr.length);
answer[smallArr.length] = pivot;
System.arraycopy(bigArr, 0, answer, smallArr.length + 1, bigArr.length);
return answer;
}
감사합니다. 좋은하루 되세요. 😄
'JAVA > 해결한 문제' 카테고리의 다른 글
| [Java/알고리즘] Merge Sort (병합 정렬) (0) | 2022.10.26 |
|---|---|
| [Java/알고리즘] 성격 유형 검사하기(프로그래머스 Lv.1) (0) | 2022.10.25 |
| 소수(prime number)인지 구하는 함수 구현하기 (3) | 2022.06.13 |
| CC(Coin Change, 동전교환) 알고리즘 구현하기 (0) | 2022.06.06 |
| 탐욕 알고리즘(Greed Algorithm) - 짐을 박스에 담는 최선의 방법 (0) | 2022.06.02 |