정렬

정렬은 무작위인 값들을 일관된 순서를 가지게 정렬하는 것을 말한다. 예를 들어 5,2,4,3,1을 오름차순으로 정렬한다면 1,2,3,4,5 로 정렬되게 된다. 이렇게 정렬하는 알고리즘은 굉장히 다양하다.

백준 문제에서는 평균 시간복잡도가 O(n²)인 정렬은 시간초과가 자주 발생하므로 웬만하면 O(n log n) 선에서 해결해야 한다. 1,2,3번은 구현하는 방법만 알아보도록 하자.

난이도 ★~★★, 평균 시간복잡도 : O(n²)

난이도 ★★★~★★★★, 평균 시간복잡도 : O(n log n)

병합 정렬
퀵 정렬
힙 정렬

이외에도 다양한 정렬이 있다.

1. 버블 정렬 (Bubble Sort) ★

인접한 두 값을 반복적으로 비교하고 교환하여 큰 값을 점점 뒤로 보내는 정렬 방식이다.

정렬 대상: 5, 2, 4, 3, 1

첫 번째 반복:

5 > 2 → 교환 → 2, 5, 4, 3, 1
5 > 4 → 교환 → 2, 4, 5, 3, 1
5 > 3 → 교환 → 2, 4, 3, 5, 1
5 > 1 → 교환 → 2, 4, 3, 1, 5 ← 5는 확정

두 번째 반복:

2 < 4 → 유지
4 > 3 → 교환 → 2, 3, 4, 1, 5
4 > 1 → 교환 → 2, 3, 1, 4, 5 ← 4는 확정

…

이런 식으로 반복 시행 1회마다 맨 뒤의 숫자가 무조건 결정되게 되어 총 정렬 대상의 인덱스 크기만큼 반복하면 모두 정렬되게 된다.

아래는 버블 정렬을 C++로 구현한 코드이다.

c++

// 배열은 arr[]이라 가정
int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
		// n - 1 번 시행하면 마지막 1개의 숫자는 자동으로 정렬된다.
        for (int j = 0; j < n - i - 1; ++j) {
        // n - i - 1인 이유는 n - i 번째 까지는 이미 
	      // 정렬이 완료되었기 때문이다.
            if (arr[j] > arr[j + 1]) {
                // swap 구현 (함수 -> 선택 정렬에 설명)
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

2. 선택 정렬 (Selection Sort) ★

선택 정렬은 매 반복 마다 가장 작은 값을 맨 앞으로 보내는 정렬 방식이다. 정렬 순서가 버블 정렬의 역순이라고 생각하면 좋다.

정렬 대상: 5, 2, 4, 3, 1

1단계:

전체 중 최솟값 1 → 맨 앞 5와 교환
→ 1, 2, 4, 3, 5

2단계:

나머지 중 최솟값 2 → 그대로 있음
→ 1, 2, 4, 3, 5

3단계:

나머지 중 최솟값 3 → 4와 교환
→ 1, 2, 3, 4, 5

…

매 n번째 반복 시행 마다 n번째 인덱스부터 가장 작은 값을 찾고 그 값과 n번째 인덱스에 들어있는 값을 바꾸며 정렬이 완료될 때 까지 반복한다.

아래는 선택 정렬을 C++로 구현한 코드이다.

c++

//배열은 arr[]이라 가정
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
    int minIdx = i;
    // 최솟값의 인덱스를 찾음
    for (int j = i + 1; j < n; ++j) {
        if (arr[j] < arr[minIdx]) {
            minIdx = j;
        }
    }
    // i번째 값과 최솟값을 교환
    swap(arr[i], arr[minIdx]); // (swap 함수 사용)
}

3. 삽입 정렬(Insertion Sort) ★★

삽입 정렬은 자신의 위치를 찾아 삽입하는 정렬 방식이다. 앞에서 부터 차례대로 요소를 확인하며, 이미 정렬된 부분과 비교하여 알맞은 위치에 삽입한다.

정렬 대상: 5, 2, 4, 3, 1

1단계:

2는 정렬된 부분 5보다 작음 → 앞으로 이동
→ 2, 5, 4, 3, 1

2단계:

4는 5보다 작고 2보다 큼 → 중간에 삽입
→ 2, 4, 5, 3, 1

3단계:

3은 5, 4보다 작고 2보다 큼 → 사이에 삽입
→ 2, 3, 4, 5, 1

4단계:

1은 모두보다 작음 → 맨 앞에 삽입
→ 1, 2, 3, 4, 5

정렬된 부분은 앞에서 부터 n 회차 반복일 경우 n 이 된다.

n+1 번째 숫자부터 앞쪽으로 비교하며 자신보다 작은 숫자가 나올 때 까지 앞으로 오게 된다.

아래는 삽입 정렬을 C++로 구현한 코드이다.

c++

// 배열은 arr[]이라 가정
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];     // 삽입할 값
        int j = i - 1;
        // key보다 큰 값들은 한 칸씩 뒤로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 올바른 위치에 삽입
        arr[j + 1] = key;
    }