[자료구조] 6-1. O(n²) 정렬- 삽입 정렬, 버블 정렬, 선택 정렬

지금까지 우리가 배워온 연산들의 공통점은 정렬된 리스트를 요구했다는 것이다. 그렇다면 정렬되지 않은 리스트는 어떻게 정렬해야 할까?

데이터를 정해진 key에 따라서 크기 순으로 배열하는 것을 정렬 알고리즘이라고 한다. 오름차순과 내림차순 두 가지의 기준이 있다. 이 두 가지는 서로 호환되기 때문에 우리는 오름차순 정렬만 언급할 것이다.

정렬 알고리즘의 성능은 데이터의 개수(크기)를 가지고 측정한다. 크게 보면 두 가지의 성능이 있다.

1.  O(n²) 정렬 알고리즘

버블, 삽입, 선택

2. O(n log n) 정렬 알고리즘

합병, 쾌속

O(n²) 정렬 알고리즘은 n개의 데이터를 정렬하려고 할 때 걸리는 시간이 n²에 가깝다고 하는 것이다. 삽입 정렬은 이동에 기반한 정렬이고 버블, 선택 정렬은 교환에 기반하고 있다.

앞에서 insert 연산을 배울 때 추가할 원소보다 더 큰 수는 뒤로 미뤄서 정렬되도록 수행했었다. 삽입 정렬은 정렬되지 않은 리스트의 원소를 차례차례 추가하면 되는 것이다.

예를 들어보자.

5, 2, 1, 3을 정렬하면

5

2 5

1 2 5

1 2 3 5

이 순서대로 정렬이 된다. 이때 추가되는 단계마다 기존의 원소가 뒤로 밀리기 때문에 이동에 기반한 정렬 알고리즘이라고 부른다.

쉽게 생각하면 부분 배열을 정렬되도록 만들고 그것을 계속 증가시키면 된다. 그렇게 다 정렬을 시켜서 원래의 배열과 일치하면 정렬이 완료 됐다고 얘기한다.

위처럼 44를 추가해야 한다면 적당한 위치인 52 앞을 찾아서 추가해주는 것이다. 그럼 그 뒤의 값들은 하나씩 뒤로 밀려난다. 이것을 코드로 만들면 n개의 크기를 가진 배열 b에 x를 삽입하라고 할 수 있다.

첫 번째 for문은 x보다 큰 첫 번째 b[i]를 찾는 역할이다. 두 번째 for문은 한 칸씩 이동해서 자리를 만들고 원소를 삽입하는 과정이다. 마지막에는 배열의 크기를 1 증가시켜주는 연산을 하는데 이 경우에는 필요가 없으므로 생략하도록 하겠다.

따라서 삽입 정렬 알고리즘은

1. 배열의 원소를 부분 배열에 하나씩 삽입 하면서 정렬을 만든다.

2. 정렬이 끝난 배열의 앞부분을 부분 배열로 활용한다.

3. 이미 정렬된 이 부분 배열에 내가 추가하고자 하는 원소를 삽입한다.

4. 부분 배열이 하나 더 추가되어 정렬된다.

하나씩 하나씩 늘려가면서 맨 마지막에 마지막 원소를 삽입하면 정렬이 끝났다고 볼 수 있다.

인덱스가 1, 즉 두 번째 원소부터 마지막 원소까지 하나씩 삽입을 하라고 하면 끝난다. 삽입하는 곳은 크기가 i-1개인 배열이다. 0부터 i-1까지의 부분 배열에 삽입하라는 의미다.

전체적인 알고리즘의 구조는 이러하다.

- insertion_sort

두 번째 원소부터 마지막 원소까지 하나씩 삽입한다.

- insert

삽입하는 실제 과정을 처리한다.

왜 a[1]부터 시작해야 할까? 여기서 a[0]은 82다. a[0]만 있는 배열(원소가 하나 있는 배열)은 이 자체로 정렬된 것이라고 간주한다. 그래서 for 루프를 시작하기 전에 우리는 이미 원소 하나 짜리의 정렬된 부분 배열을 가지고 있는 것이다.

i가 1일때는 61이다 a[1]이다. 이것을 부분 배열의 적당한 곳에 삽입하고 더 큰 숫자는 뒤로 물러난다.

i=3일 때 5를 정렬한다.

마찬가지로 수행한다.

계속 반복하다 마지막 원소를 적합한 위치에 삽입하면 정렬이 끝난다. 이렇게 정렬되지 않은 배열이 정렬되었다.

삽입 정렬에서 삽입을 하는 insert 함수는 n개의 원소에 대해서 삽입을 연산하므로 O(n)이 걸린다. 또한, insertion_sort 함수에서 insert를 호출하는 것도 n번 호출하므로 O(n)이다. 둘을 곱하면 토탈 O(n²) 의 시간만큼 연산이 수행된다.

버블 정렬은 교환을 통해 정렬한다.

예를 들어, 5와 30을 비교하면 5가 작은 게 맞으므로 교환이 일어나지 않는다. 하지만 61과 5는 61이 더 크므로 교환이 일어나게 된다.

이 배열에서 가장 작은 수가 첫 번째 자리로 가려면 몇 번이나 교환을 해야할까?

1. best case

가장 작은 수가 맨 앞에 있기 때문에 0번 교환한다.

2. worse case

가장 작은 수가 맨 뒤에 있으므로 4번의 교환이 필요하다. 즉, O(n)번이다.

이렇게 버블 정렬은 최악의 경우를 만날 수 있는 정렬이다.

버블 정렬의 기본 개념은 일단 맨 앞에 가장 작은 수를 두자는 것이다. 그 다음으로는 두 번째 자리에 두 번째 작은 값을 옮기는 것이다. 계속 하다보면 결국 n-1번 반복하게 된다.

가장 작은 숫자가 마치 거품이 밑에서 보글보글 올라오듯 올라오는 알고리즘이라고 해서 버블 정렬이라고 부른다. 같은 원리로 가장 큰 숫자가 맨 뒤로 가는 알고리즘은 sinking sort라고 한다.

알고리즘은 다음의 단계로 수행한다.

1. 정렬되지 않고 남은 원소 중에서 가장 작은 수를 맨 앞에 갖다 놓는 연산을 수행한다.

2. 이러한 연산을 첫 번째부터 마지막 자리까지 차근차근 수행한다.

0번째 자리에 가장 작은 수가 오게 만든다. 그 다음에는 그 다음으로 작은 수가 온다. 이를 위해 n-2번째 자리까지 작은 수부터 정렬한다. n-1번째 자리는 맨 마지막에 숫자 하나만 남아 정렬할 필요가 없기 때문이다.

그 다음, for 루프 안에 i번째로 작은 숫자가 i번째 자리에 오도록 한다. 즉, 맨 뒤에 있는 값부터 i번째 값까지 하나씩 접근하면서 알맞게 교환한다.

자리를 바꾸는 것을 swap이라고 하는데, call by reference를 이용해 구현되는 함수다. 두 숫자의 주소를 입력받고 swap 연산을 수행한다.

버블 정렬이 실제로 어떻게 일어나는지 알아보자. i=0부터 n-2까지 반복할 것이다. i=0일때는 j=4부터 시작한다. j=n-1이기 때문이다. 그리고 j>i인 동안 수행하니까 j=1일때까지 수행할 것이다.  j=4일 때 j번째 원소와 j-1번째 원소를 비교한다.

j=3일때도 교환은 일어나지 않는다.

드디어 교환이 일어난다.

첫번째 자리(i=1)가 제대로 정렬되었다.

다음은 두 번째 자리를 정렬해보자. 아까처럼 똑같이 맨 뒤에서 시작한다.

j=3일때 30이 더 작으므로 교환한다.

두 번째 자리까지 완료되었다.

이제 세 번째 자리에 알맞은 수를 정렬해보자. 역시 맨 뒤에서 시작한다.

완료 되었다.

네 번째 자리까지 완료 되었다. i=n-2일때는 딱 한 번만 비교하면 정렬이 완료된다.

즉, i=3 자리를 완료하고 나면 더이상 하지 않아도 자동 정렬 된다.

첫 번째 i=0일 때는 맨 뒤에서 i번째 자리까지 n-1번 연산을 수행한다. i=1일때는 n-2이고 쭉 반복하다가 i=n-2일때 딱 한 번만 비교하고 연산이 마무리된다. 이걸 다 더한 것이 최종적인 시간 복잡도이다. O(n²)이 된다.

버블 정렬은 최악의 경우 O(n²)번이나 교환을 수행해야 한다. 이러한 단점을 해소하기 위해 선택 정렬이 등장했다.

5가 맨 앞에 가기 위해서는 굳이 바로 앞의 값과 계속 비교할 필요 없이 첫 번째 값만 비교하면 된다는 것이 기본 개념이다. 어떤 수가 맨 앞에 가기 위해 딱 한 번 비교하고, 그 다음 두 번째 수도 그 자리로 가기 위해 딱 1번 비교하는 것이다.

한 마디로 얘기하자면, i번째로 작은 숫자를 찾아서 i번째 원소와 교환하는 것이다.

첫 번째 자리에 제일 작은 값을, 두 번째 자리에 두 번째 작은 값을 옮기는 과정을 반복한다. 그 값을 찾으려면 select_min()이라는 함수를 생각해야 한다.

select_min은 b라는 배열에서 s부터 e까지의 원소 중 가장 작은 값을 찾아서 인덱스를 리턴하는 함수이다.

먼저, 가장 작은 인덱스를 첫 번째 인덱스로 잡는다. 첫 번째 원소가 가장 작다고 가정하는 것이다. 그 다음에 두 번째 원소부터 마지막 원소까지 비교한다. 비교 중인 원소가 가장 작은 원소보다 작다면 해당 원소를 맨 앞으로 보낸다. 연산이 끝나면 min_idx를 리턴한다.

인덱스가 0부터 5인 b라는 배열을 select_min에 넣어 호출하면 9가 제일 작다고 리턴하는 식이다. 따라서, k=4가 된다.

역시나 정렬되지 않은 원소 중에서 제일 작은 값을 찾아 적절한 위치에 바꿔주면 된다.

코드로 나타내면, 0부터 마지막 원소 하나 전(n-1) 사이에 가장 작은 원소를 찾고, 그 인덱스를 가져온다. 그리고 i번째를 해당 인덱스와 교환한다.

전체적으로 보면, selection_sort 함수는 select_min 함수를 여러번 부르고, select_min 함수는 가장 작은 인덱스를 리턴하는 구조다.

selection_sort는 i=0부터 시작한다. 인덱스 0부터 4 사이에 가장 작은 값을 찾고 그 값을 맨 앞으로 교환한다. 

i=1일때는 두번째 원소부터 마지막 사이에 가장 작은 값을 찾고 교환한다.

i를 늘려가며 계속 반복한다.

반복

그럼 마지막 남은 수는 자동적으로 가장 큰 수가 된다.

선택 정렬의 장점은 최악의 경우에도 교환을 O(n)번만 한다는 것이다. select_min() 자체가 n개에서 가장 작은 수를 찾는 알고리즘이므로 O(n)이다. 이 연산을 O(n)번 하므로 최종적으로 O(n²)의 시간이 걸리는 알고리즘이다.

다음 강의에서는 이보다 더 성능이 좋은 정렬에 대해 공부한다.