[백준] 1427번 : 소트인사이드 | C++

1. 문제 상세

 

https://www.acmicpc.net/problem/1427

 

 

 

2. 문제 접근

 

정수를 입력받고 각 자리수를 구하여 배열에 저장한다.

이 자리수들을 내림차순으로 정렬하여 출력하자.

 

입력받는 수는 최대 1,000,000,000 이다.

따라서 정렬 해야 할 수의 최대 갯수는 10개이다.

 

정렬 할 수의 개수가 적어서 여러 정렬 알고리즘을 사용할 수 있다.

좀 더 효율 알고리즘인 퀵 정렬 알고리즘을 사용해보자.

 

■ 퀵 정렬

퀵 정렬 알고리즘은 합병 정렬(merge sort)과 비슷하게 분할 정복 정렬 알고리즘이다.

하지만 합병 정렬과는 다르게 배열을 비균등하게 분할한다는 차이점이 있다.

 

분할 과정에서는 배열을 임의의 피벗 값을 기준으로 피벗보다 작은 쪽(왼쪽)

과 큰 쪽(오른쪽), 총 2개의 부분배열로 나눈다.

정복 과정에서는 부분 배열의 크기가 충분히 작지 않다면

순환 호출로 분할 과정을 다시 거쳐 부분 배열을 더 작게 나눈다.

결합 과정에서는 부분 배열을 하나의 배열로 합쳐간다.

 

배열의 원소중 임의의 값을 피벗(pivot)으로 선택한다.

(코드로 구현 시 대부분 가운데 위치한 값이나 맨 왼쪽 값을 선택한다.)

피벗을 기준으로 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 위치하도록 한다.

이 과정을 거치면 피벗 왼쪽에 작은 부분 배열이 만들어지고,

피벗부터 피벗 오른쪽이 큰 부분 배열로 만들어진다.

이 각 부분 배열들에도 위 과정을 거쳐 부분 배열의 크기가 0이나 1이 될 때 까지 반복한다.

 

아래의 사진으로 확인해보자.

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

그 후에는 결합 과정을 거쳐 배열을 정렬해간다.

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

 

 

 

아래는 배열 { 5, 3, 8, 4, 9, 1, 6, 2, 7 } 을

퀵 정렬을 사용하여 정렬하는 예시이다.

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

정렬 과정에 대해 좀 더 자세히 알아보자.

 

피벗을 배열의 첫 번째 값으로 선택하고, 피벗을 제외한 배열의 맨 앞을 low,

맨 뒤를 high 로 선택한다.

low 는 하나씩 뒤로 이동하며 그 값이 피벗보다 큰지,

high 는 하나씩 앞으로 이동하며 그 값이 피벗보다 작은지 확인한다.

해당하는 값을 발견한 경우 잠시 멈추고 low, high 둘 다 찾으면 값을 교환한다.

이 과정을 반복하다가 low 가 high 와 엇갈리는 경우(low 가 high 보다 커지면)

멈추고, high 자리의 값과 피벗(배열의 첫 번째 값)값을 교환한다.

이렇게 하면 배열의 맨 앞부터 high 전까지가 피벗보다 작은 값의 부분 배열,

high 뒤 부터 배열의 맨 끝까지가 피벗보다 큰 값의 부분배열이 된다.

 

이제 양쪽의 부분 배열도 순환 호출을 통해 위 과정을 실행하자.

 

 

퀵 정렬의 시간복잡도를 확인해보자.

먼저 평균적인 경우 순환 호출의 깊이는 합병 정렬과 같이 log₂n 이 된다.

 

각 순환 호출 단계에서 비교 횟수는 최대 n 번 이므로, 둘을 곱하여 nlog₂n 이 된다.

 

결과적으로 퀵 정렬의 평균적인 시간복잡도는 O(nlog₂n)이다.

 

하지만 퀵 정렬은 최악의 경우 시간복잡도가 다르다.

분할 과정을 거쳤을 때 배열이 계속 불균형하게 분할되는 경우(이미 정렬된 경우)

순환 호출의 깊이가 n 번이 되고, 비교 횟수는 동일하게 n 번이므로 n * n 번,

n² 이 되므로 시간복잡도가 O(n²)이 된다.

 

아래를 통해 다른 정렬 알고리즘과 시간복잡도를 비교해보자.

최악의 경우 O(n²)으로 선택, 삽입, 버블 정렬 알고리즘과 수행 시간이 비슷하지만

대부분의 경우는 O(nlog₂n)으로 매우 효율적이고,

힙, 합병 정렬보다도 수행 속도가 더 빠른 것을 볼 수 있다.

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

문제풀이를 통해 퀵 정렬을 구현해보자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int partition(int list[], int left, int right) {
    int low = left;
    int high = right + 1;
    int temp;

    do {
        do {
            low++;
        } while (low <= right && list[low] < list[left]);
        do {
            high--;
        } while (high >= left && list[high] > list[left]);
        if (low < high) {
            temp = list[low];
            list[low] = list[high];
            list[high] = temp;
        }
    } while (low < high);
    temp = list[high];
    list[high] = list[left];
    list[left] = temp;

    return high;
}

void quick_sort(int list[], int left, int right) {
    if (left < right) {
        int pivot = partition(list, left, right);

        quick_sort(list, left, pivot - 1);
        quick_sort(list, pivot + 1, right);
    }
}

int main() {
    int n, num = 0, list[10];

    cin >> n;

    for (int i = 0; n != 0; i++) {
        list[i] = n % 10;
        n /= 10;
        num++;
    }

    quick_sort(list, 0, num - 1);

    for (int i = num - 1; i >= 0; i--) cout << list[i];
}

 

함수 partition 을 선언, 매개변수로 배열(list)과 정수(left, right)를 받는다.

// 정복 과정의 함수 선언, 매개변수로 배열, 배열의 앞, 마지막 인덱스를 전달받는다.

 

정수 low, high, temp 를 선언, low 는 left 로, high 는 right + 1 값으로 초기화.

// low 는 반복 시작 시 1을 더해주고 right 는 1을 빼주기 때문에 위와 같이 초기화.

 

 

do while문 실행, low 가 high 보다 작을 때 반복한다. 

// low 와 high 가 엇갈리면 반복 중지.

 

다시 do while문 실행, low 가 right 보다 작거나 같고,

list 의 low 위치의 값이 left 위치의 값보다 작을 때 반복.

반복에서는 low 에 1을 더해준다.

// low 를 피벗 뒤부터 하나씩 뒤로 이동하며 low 위치 값이 피벗보다 클 때 반복 중지.

 

위의 반복이 끝나면 다시 do while문 실행, high 가 left 보다 크거나 같고,

list 의 high 위치의 값이 left 위치의 값보다 클 때 반복.

반복에서는 high 에 1을 빼준다.

// high 를 배열 끝부터 하나씩 앞으로 이동하며 high 위치 값이 피벗보다 작을 때 반복 중지.

 

위의 반복이 끝나면 if문으로 low 가 high 보다 작은 경우,

list 의 low 위치의 값과 high 위치의 값을 교환한다.

// 피벗 기준 왼쪽에 위치한 큰 값과 오른쪽에 위치한 작은 값을 교환.

 

 

위의 반복이 끝나면 // low 와 high 가 엇갈린 경우

list 의 left 위치의 값과 high 위치의 값을 교환한다. // 피벗을 중간으로 이동.

 

high 의 값을 반환한다. // 피벗 위치 반환.

 

 

 

함수 quick_sort 를 선언, 매개변수로 배열(list)과 정수(left, right)를 받는다.

// 분할, 정복 과정의 함수를 선언, 매개변수로 배열, 배열의 앞, 마지막 인덱스를 받는다.

 

if문으로 left 가 right 보다 작은 경우, // 배열 크기가 0 또는 1보다 큰지 확인.

정수형 변수 pivot 을 선언하고 partition 함수에 list, left, right 를 전달하여 호출,

반환된 값을 저장한다. // 현재 전달받은 배열의 pivot 값을 구해 저장.

 

quick_sort 함수에 list, left, pivot - 1 값을 전달하여 호출

// 피벗을 구하고 피벗의 앞쪽(왼쪽) 부분 배열을 순환 호출.

quick_sort 함수에 list, pivot + 1, right 값을 전달하여 호출

// 피벗을 구하고 피벗의 뒤쪽(오른쪽) 부분 배열을 순환 호출.

 

 

 

main 함수에서는 정수 n, num, 크기 10의 배열 list 를 선언

/* 입력받을 수를 저장할 n, 입력받은 수의 자리수 개수를 저장할 num,

각 자리수를 저장 할 배열 list 를 선언. */

 

cin 으로 정수를 입력받아 n 에 저장.

 

for문으로 i 가 0 부터 n 이 0이 아닐 때 1씩 더하며 반복.

list 의 i 번 위치에 n 을 10으로 나눈 나머지 값을 저장.

n 을 10으로 나누고 num 에 1을 더해준다.

/* 입력받은 숫자를 각 자리수로 나누어서 배열에 저장하고,

num 에 자리수 개수를 저장한다. */

 

quick_sort 함수에 list, 0, num - 1 을 전달하여 호출.

// list 배열과 배열의 맨 앞 인덱스 0, 맨 뒤 인덱스인 num - 1을 전달한다.

 

for문으로 i 가 num - 1 부터 0 보다 크거나 같을 때 1씩 빼며 반복,

cout 으로 list 의 i 번 인덱스의 값과 개행문자를 출력한다.

// 함수 호출이 끝나고 정렬이 완료되면 정렬된 배열을 역순으로 출력한다.

 

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

이미지 및 참고글 출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

퀵 정렬 구현에서 많이 헷갈렸던 것 같다..

 

피벗을 구하기 위한 함수 partition 에서

low, high 의 위치를 변경하는 반복문에 while문을 사용했더니 문제가 발생했다.

low 보다 high 가 크고, 각 위치에 같은 값이 나오는 경우, 값을 바꾸고

low, high 를 증가시키지 않은 채로 반복하게 되어서 무한 루프를 돌아버린다..

이를 해결하기 위해 결국 do while 문으로 바꿔서 값을 한번 바꾸면 무조건

low, high 를 다음으로 넘기도록 하였다..