알고리즘 공부/강의 - 3. sort 정렬문제

 

 

 

이제 기본적인 산수, 반복 문제를 쉽게 풀 수 있다면 sort 문제를 쉽게 풀 수 있을 것이다. sort는 정렬이라는 의미로 알고리즘을 처음 배우는 사람들이 가장 먼저 접하는? 그리고 공부하는 사람들이 가장 먼저 배우면서 짜증 나는 파트이기도 하다. 왜냐하면 정렬의 종류가 많은데 뭔 의미인지 모르겠기 때문이다. 일단 가장 기본적인 세 가지 정렬이 있다. 이 기본적인 정렬은 작성하기는 쉽지만 시간복잡도가 큰, 즉 효율이 적은 정렬을 말한다.

 

하지만 이 세 가지 정렬은 마지막에 보고 그 전에 빠르게 알고리즘을 사용할 수 있는 방법이 있다. 바로 sort 함수를 이용하는 것이다. 사용법은 <algorithm> 라이브러리를 추가한다. 그리고 sort 함수를 사용하면 된다. sort 함수를 사용하는 방법은 두 가지인데 compare 함수를 쓰느냐 마느냐가 있다. 빠르게 오름차순으로 정렬하려면 compare함수가 필요 없이 배열의 크기만 알고 있으면 된다.

#include <algorithm>

int arr [100];

sort(arr, arr+100);

이렇게만 하면 정렬이 된다. 여기에 오름차순 내림차순을 바꿔주려면 compare함수를 추가한다.

bool compare(int x, int y)

{
    return x <y;

}

저기에 x <y면 앞에가 더 작고 뒤에나 더 커지는 오름차순, x> y를 하면 내림차순으로 정렬이 된다. 그리고 sort 함수에 추가한다.

sort(arr, arr+100, compare);

 

이렇게 하면 기본적인 정렬 문제를 풀 수 있다. 예시로 구글 문제를 가져왔다.

이 문제의 경우 배열을 정렬시켜서 값을 처음부터 비교해보면 쉽게 알 수 있다. 

 

이 아래는 3가지 정렬인데 이름과 비슷하므로 이러한 정렬이 있구나를 생각만 해놓으면 된다. 나중에 응용해서 다른 문제를 풀 수도 있다.

 

1. 버블 정렬

버블 정렬은 기준 배열과 바로 오른쪽 옆 배열과 비교하여 바꾸는 형식으로 가장 쉽게 생각할 수 있는 방식 중 하나이다. 비교대상이 바로 옆이라 직관적으로 알기 쉽다. 바꾼 뒤에는 기준 배열을 오른쪽으로 한 칸 옮기고 다시 비교하고... 이런 식이다. 딱 봐도 여러 번 실행해야 하는 것을 알 수 있다. 기본적인 코드는 아래와 같다.

 

void bubbleSort(int arr [], int size) {

    int i, j;

    for (i = size - 1; i>0; i--)

        for (j = 0; j <i; j++)

            if (arr [j]<arr [j + 1])

                swap(&arr [j], &arr[j + 1]);

}

 

2. 선택 정렬

선택 정렬은 가장 작은 수나 가장 큰 수를 찾아 첫 번째에 넣고, 그다음 큰 숫자를 그 다음 배열에 넣고 하는 식으로 진행이 된다. 넣을 때에는 새로운 배열을 써도 되지만 swap을 통해 하나의 배열로 바꿀 수도 있다. 정렬은 기본적으로 한 개의 배열로 하나보다. 기본적인 코드는 아래와 같다. 

 

void selectionSort(int arr [], int size) {

    int minIndex;

    int i, j;

    for (i = 0; i < size - 1; i++) {

        minIndex = i;

        for (j = i + 1; j < size; j++)

            if (arr [j] < arr [minIndex])

                minIndex = j;

         

        swap(&arr [i], &arr [minIndex]);

    }

}

 

3. 삽입 정렬

삽입 정렬에서는 key값이 등장하는데 보통 배열의 1번부터 시작해서 맨 앞의 원소랑 비교한 뒤 그 뒤에 원소들과 비교를 한다. 그래서 그 원소보다 작으면 그 위치에 넣고 뒤의 배열을 밀어버린다.  

 

void insertionSort(int arr [], int size) {

    int i, j, key;

 

    for (i = 1; i < size; i++) {

        key = arr [i];

        j = i - 1;

        while (j >= 0&&arr [j]>key) {

            arr[j + 1] = arr [j];

            j--;

        }

        arr [j + 1] = key;

    }

}