1. 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있어야한다.
2. C로 문자열 형식을 가진 변수를 선언하고 출력하는 프로그램을 만들 수 있다.

boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 듣고 정리한 필기입니다. 😀

1. 선택정렬

보통 배열이 정렬되어있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있다. 우리에게는 어제와 같이 정렬되지 않은 배열이 있다.

6 3 8 5 2 7 4 1

버블 정렬의 좋은 점은 직관적인 방법이라는 것이다. 왼쪽과 오른쪽이라는 2개의 숫자를 비교해서 작은 문제를 풀어나간다. 하지만 버블 정렬은 O(n²)의 시간이 소요된다. 오늘은 버블정렬이 아닌 선택 정렬을 배웠다. 선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 선택 정렬은 교환 횟수를 최소화하지만 각 자료를 비교하는 횟수는 증가한다.

먼저 정렬되지 않는 배열을 하나하나 탐색하면서 가장 작은 값을 찾는다. 주어진 배열 “6 3 8 5 2 7 4 1”을 예로 들어보자. 왼쪽부터 확인한다고 지면, 컴퓨터는 가장 먼저 0번째 인덱스를 확인할 것이니 6이 제일 작은 숫자라고 기억할 것이다. 그리고서 1번째 인덱스를 확인하면 6보다 3이 작기 때문에 3을 가장 작은 수로 기억할 것이다. 이후 8, 5와 비교를 하다가 2를 만나면 이제는 3이 아니라 2가 가장 작은 숫자가 된다. 그리고 맨 마지막에 와서야 해당 배열에서 가장 작은 값인 1을 찾게 된다.

6 3 8 5 2 7 4 1

가장 작은 값은 가장 왼쪽에 있어야 하으로, 현재 배열의 1번째 인덱스값인 6과 자리를 바꾼다. 꼭 두 개의 자리를 바꿔야 하는 것은 아니다. “1 6 3 8 5 2 7 4”의 순서도 가능하겠지만, 인덱스의 값을 하나하나 뒤로 이동시키는 건 1과 6의 자리를 교환하는 것보다 시간이 좀 더 걸린다.

1 3 8 5 2 7 4 6

자 우리는 해당 배열 중 가장 작은 값을 찾았으니, 우리는 앞으로 n개가 아니라 n-1개의 수를 살피면 된다. 즉, 1번째 인덱스에 있는 3부터 시작해 가작 작은 수를 찾으면 된다는 말이다. 1번째 인덱스에 있는 3은 2를 만나기 전까지 가장 작은 수가 될 것이다.

1 3 8 5 2 7 4 6

2를 만나면 멈추고 2와 3일 옮기면 될까? 우리는 사람이기에 3의 오른쪽에 있는 숫자 중에, 3보다 작은 수는 2 밖에 없다는 것을 알겠지만, 컴퓨터는 한 번에 하나씩만 기억할 수 있기 때문에 그렇지 않다. 이제 그다음부터는 2보다 작은 것이 있는지를 확인하면 된다.

1 2 8 5 3 7 4 6

2보다 작은 값이 없다는 것을 확인하고 나면, 정렬되지 않는 숫자 중에서 가장 앞에 있어야 하므로 3과 교환한다. 이 과정을 더는 교환이 일어나지 않을 때까지 반복하면, 아래와 같이 오름차순 정렬이 된다.

1 2 3 4 5 6 7 8

어제 배웠던 버블정렬과는 완전히 다른 알고리즘이다. 쌍을 이뤄 앞뒤 순서를 교환하지 않는다. 매번 목표를 세워 가장 작은 값을 찾고 다음 작은 값을 찾는 정렬 방법을 ‘선택 정렬’ 이라고 한다. 반복할 때마다 다음으로 가장 작은 수를 고른다. 의사 코드로 아래와 같이 표현할 수 있습니다.

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

수도코드만 보면 매우 단순해 보인다. 이제 어떤 정렬이 더 나은가에 대해서 생각해봐야 한다. 정렬을 비교하기 위해서는 Big-O와 Omege가 있다. 여기서도 두 번의 루프를 돌아야 한다. (바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 한다.)

주어진 배열 중에서 가장 작은 값을 찾을 때는(즉, 0번째 인덱스에서 시작할 때) n번을 돌아야 한다. 그다음에는 n-1 번, 그다음에는 n-2 번… 이것을 식으로 나타내면 아래와 같다.

n + (n-1) + (n-2) + ... + 1

이것은 총 몇 번이 될까? 이것을 다 더하거나 공식을 찾아보면 n(n+1)/2가 된다. 곱셈을 풀어보면 (n²+n)/2이고, 이것을 더 풀면 (n²)/2 + n/2가 된다. 하지만 내가 지금 하는 것은 수학이 아니기 때문에 이런 식으로 수학적 증명을 할 필요가 없다. 기억해야 할 것은 Big-O 표기법에서는 n²라는 것이다. 상수나 계수처럼 숫자 형태인 것은 죄다 제외하고 가장 큰 n을 찾으면 그게 Big-O 표기법이 된다. 따라서 소요 시간의 상한은 O(n²)이 된다. 버블정렬과는 근본적으로 다른 알고리즘이지만, 수학적으로는(실제로도) 같은 성능을 갖는다.

선택정렬의 Omega는 어떨까? 가장 최악의 경우에는 정렬이 된 배열을 다시 정렬하는 것이다. 이미 ‘ 1 2 3 4 5 6 7 8’, 오름차순으로 잘 정렬되어있음에도 컴퓨터는 그 사실을 모른다. 위에서 말했듯이 프로그램은 배열 속 다른 값을 전부 보기 전까지는 알 수가 없다. 심지어 지나온 숫자가 무엇이었는지도 기억하지 못한다. 즉, 선택정렬을 사용해도, 당장 앞에 놓은 수만 알 수 있기 때문에 같은 코드를 계속 반복할 것이다. 즉, Big-O 표기법이 버블정렬과 같았던 것과 마찬가지로 Omega도 동일하게 Ω(n²) 이다.

2. 정렬 알고리즘의 실행시간

여태까지 배운 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행 시간이 각각 어떻게 되는지 정리하면 아래와 같다.

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n)
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n)
• Ω(n)
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

n²는 결코 좋은 알고리즘이라고 할 수 없다. 우리가 배운 정렬을 더 좋게 만들 수는 없을까? 다시 버블정렬도 돌아가 보자. 아래는 버블정렬의 의사코드이다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

버블정렬은 i와 i+1를 비교하고 i+1가 i보다 작다면 위치를 바꾼다. 정렬이 될 때까지 계속 반복하면서 말이다. 언제쯤이면 배열 앞뒤를 훑으면서 비교하는 것을 그만할까? 바로 i와 i+1의 위치를 바꾸지 않을 때이다. 알고리즘은 n-1번 반복하라고 했지만, 여기에 ‘교환이 일어나지 않을 때’까지만 수행하도록 하는 조건문이 있으면 시간을 단축할 수 있을 것이다.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

이것이 잘 와닿지 않는다면 이미 잘 정렬되어있는 배열을 가지고 생각하면 이해가 쉽다. 우리에는 아래와 같이 잘 정렬된 배열이 있다.

1 2 3 4 5 6 7 8

먼저 0번째 인덱스와 1번째 인덱스를 비교한다. 1번째 인덱스에 있는 2가 0번째 인덱스에 있는 1보다 크기 때문에 자리를 바꾸지 않는다.

1 2 3 4 5 6 7 8

그다음은 1번째 인덱스와 2번째 인덱스를 비교한다. 2번째 인덱스에 있는 3이 1번째 인덱스에 있는 2보다 크기 때문에 역시 자리를 바꾸지 않는다.

1 2 3 4 5 6 7 8

이것을 계속 반복하다 보면 총 n-1번 진행된다. (숫자는 총 8개가 있는데, 비교는 총 7번 일어나기 때문에) n-1번동안 교환이 일어나지 않았다는 답을 받으면 알고리즘을 일찍 종료해도 된다. 그렇다면 최선의 경우에는 n-1 번의 과정을 반복한다. 따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 된다. 더는 Ω(n²)가 아니어도 되는 것이다.

상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것이다.

실행시간의 하한

• Ω(n^2): 선택 정렬
• Ω(n log n)
• Ω(n): 버블 정렬
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색