CodingTest - 퀵 정렬

- 방법 1

import java.util.Scanner;

public class Main {

    public int[] quickSort(int[] data, int start, int end) {
        if (start >= end) {
            return data;
        }

        int key = start;
        int i = start + 1, j = end, temp;

        while (i <= j) {
            while (i <= end && data[i] <= data[key]) {
                i++;
            }
            while (j > start && data[j] >= data[key]) {
                j--;
            }
            if (i > j) {
                // Swap data[key] and data[j] using temp variable
                temp = data[key];
                data[key] = data[j];
                data[j] = temp;
            } else {
                // Swap data[i] and data[j] using temp variable
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        quickSort(data, start, j - 1);
        quickSort(data, j + 1, end);

        return data;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner scanner = new Scanner(System.in);
        int iNum = scanner.nextInt();
        int[] ints = new int[iNum];
        for (int i = 0; i < iNum; i++) {
            ints[i] = scanner.nextInt();
        }
        int[] sortedArray = main.quickSort(ints, 0, iNum - 1);
        for (int x : sortedArray) {
            System.out.print(x + " ");
        }
    }
}

1. 퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 

2. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

3. 일반적으로 퀵 정렬에서는 기준 값이 있고, 이를 피벗(Pivot)이라고도 한다. 보통 첫 번째 원소를 피벗 값으로 설정하고 사용한다.

 

- EX)

1. 3 6 2 8 4 9 7 1 5 10 / 의 숫자 배열이 있을 때 처음 피벗은 3이 된다.

2. (3) 6 2 8 4 9 7 1 5 10 / 3을 기준으로 좌측과 우측의 숫자 배열들을 비교한다.

3. 현재 3을 기준으로 왼쪽은 없기 때문에 우측 숫자 배열을 기준으로 왼쪽에서부터는 3보다 큰 값을 우측에서 부터는 3보자 작은 값을 검색한다.

4. 왼쪽부터 찾은 값은 6, 오른쪽부터 찾은 값은 1이 된다.(3보다 큰수, 작은수를 찾은 것이다.

5. 여기서 추가로 확인해야 할 부분은 1) 왼쪽에서 찾은 값의 인덱스가 오른쪽에서 찾은 인덱스 값보다 커졌다면, 오른쪽에서부터 찾은 값(기준 값인 3보다 작은 값)과 위치를 바꾸고, 2) 왼쪽에서 찾은 값의 인덱스가 오른쪽에서 찾은 인덱스 값보다 작다면 양쪽에서 찾은 값(기준 값인 3보다 큰값, 작은값)을 서로 바꾼다.

6. 현재 ex에 있는 배열의 경우 5.2)에 해당하기 때문에 찾은 값을 서로 바꾼다.

- (3) 1 2 8 4 9 7 6 5 10 와 같이 변하게 된다.

7. 최초의 피벗값의 인덱스(위치)가 변하지 않으면 위 과정을 또 다시 반복한다.

8. (3) 1 2 8 4 9 7 6 5 10를 한 번 더 수행하면 5.1)의 경우가 발생하여 오른쪽에서부터 찾은 값(기준보다 작은 값)과 위치를 바꾸게 되고, 2 1 (3) 8 4 9 7 6 5 10 와 같이 숫자 배열이 변하게 된다.

9. 최초 피벗 값이 변했기 때문에 최초 피벗 값을 기준으로 왼쪽과 오른쪽을 나눠(왼쪽 2 1 / 오른쪽 8 4 9 7 6 5 10) 각 그룹의 첫번째(2 / 8)을 피벗으로 지정하여 1. 과정부터 다시 반복한다. 

 

- 선택, 버블 정렬의 평균 속도가 N^2이지만 퀵 정렬은 N*logN의 속도를 가지기 때문에 N이 커지면 커질수록 속도의 차이가 엄청나게 차이나게 된다.