[Java/알고리즘] Quick Sort(퀵 정렬)

 

 

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴합니다.

조건

• 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;
}

 

 

 

깃허브 코드 보러가기

 

 

 

감사합니다. 좋은하루 되세요. 😄