[알고리즘] 정렬 알고리즘 - 선택,버블,삽입
안녕하세요. 오늘은 정렬 알고리즘에 대해 공부를 해보았는데요. 기초적인 알고리즘에 속하지만 최근들어 알고리즘을 제대로 다시 시작하기 위해 시간복잡도를 바탕으로 다시 공부해보는 시간을 가졌습니다.
오늘은 기본적으로 시간 복잡도가 O(N^2)인 알고리즘부터 알아보도록 하겠습니다.
(모든 다이어그램은 제가 키노트를 활용하여 제작하였습니다! 조금은 부족하더라도 너그러히 이해부탁드리며 틀린 부분이 있다면 피드백 부탁드리겠습니다.)
1. 선택 정렬
선택 정렬을 간단히 설명해드리자면 오름차순으로 정렬한다고 가정을 하였을 때 정렬되지 않은 배열 중 가장 작은 배열을 선택하여 앞에서부터 채워나가는 방식입니다.
파란색 화살표는 현재 채워야 할 위치의 인덱스를 가리킵니다. 빨간색 화살표는 현재 라운드에서 가장 작은 값에 해당하는 인덱스를 가리킵니다. 현재 인덱스를 포함하여 그 뒤의 배열 값 중 가장 작은 값을 선택하여 현재 인덱스의 값과 자리를 바꿔주면 됩니다. 첫 번째 라운드에서는 1이 선택되어 현재 인덱스의 값인 5와 자리가 바뀌어 다음 라운드부터 1은 본인의 알맞은 인덱스에 위치하게 됩니다.
이렇게 매 라운드마다 값들이 하나씩 자신의 자리에 채워지게 되므로 이미 자리를 찾은 값은 고려해주지 않아도 됩니다. 그렇다면 배열의 크기가 N이라면 총 라운드는 배열의 길이만큼 N 라운드가 진행되며 각 라운드마다 비교횟수는 하나씩 줄어들게 됩니다.
첫 라운드에서 비교해야할 인덱스의 갯수는 N개! 첫 라운드 이후 하나의 값은 제자리를 찾아갔으므로 다음 라운드에서 비교해야할 인덱스의 갯수는 N-1개 이런식으로 줄어들게 됩니다. 이렇게 총 비교 횟수를 계산해보면 (N - 1) + (N - 2) + (N - 3) + ... + 1
그렇다면 총 비교 연산 횟수는 N *(N - 1 ) / 2 가 됩니다. 그러므로 이에따른 빅오는 O(N^2)이 됩니다. 단점이라하면 이미 정렬되어있는 상태에서도 매 라운드마다 남은 배열들에서 가장 작은 값을 찾는 불필요한 비교를 진행하기 때문에 정렬되어 있는 배열에 대해서도 빅오는 O(N^2)가 됩니다.
2. 버블 정렬
버블 정렬은 마치 정렬이 이루어지는 과정이 거품이 일어나는 것과 비슷하다하여 붙여진 이름입니다. 버블 정렬의 과정을 간단히 설명하자면 바로 다음 인덱스의 값과 비교를 하여 현재의 인덱스 값이 다음 인덱스의 값보다 크다면 둘의 위치를 바꿔주고 같은 방식으로 바로 그 다음 인덱스부터 비교를 다시 시작하는 것입니다. 즉 바로 다음 인덱스와의 비교만을 진행하는 것입니다.
선택 정렬과 다르게 위의 그림이 한 라운드입니다. 첫 인덱스 5를 2와 비교 후 앞의 인덱스인 5가 더 크기 때문에 둘의 위치를 바꿔줍니다. 그리고 비교하고자 하는 인덱스를 하나 증가시켜 두 번째 인덱스의 값인 5와 바로 그 다음 인덱스의 값인 8을 비교합니다. 하지만 5는 8보다 작으므로 위치를 바꿔주는 행위는 실행되지 않습니다. 하지만 비교 인덱스의 증가는 지속됩니다. 즉 8가 1을 비교하여 교체 8과 10을 비교, 10이 더 크므로 다시 10과 4를 비교하여 교체!
이런식으로 하나의 라운드를 진행하다보면 매 라운드마다 가장 큰 수가 맨 뒤에 위치하게 됩니다. 비교 횟수 역시 처음에는 N -1 번이고 다음 라운드에서는 맨 마지막 값은 정해졌기 때문에 그 앞까지 비교를 진행하므로 N - 2번이 됩니다. 총 비교 횟수는 역시 마찬가지로 N * ( N - 1) / 2가 됩니다. 고로 빅오는 O(N^2)가 됩니다.
선택 정렬과 마찬가지로 이미 정렬되어 있어도 비교를 진행하기 때문에 최선의 상황에서도 빅오는 O(N^2)가 됩니다.
3. 삽입 정렬
삽입 정렬은 얼핏보면 선택 정렬과 비슷하다는 느낌을 받을 수 있습니다. 삽입 정렬은 현재 인덱스 이전의 배열들은 정렬이 되어있다는 전제하에 현재 인덱스의 값을 적절한 위치에 삽입해주는 정렬 알고리즘입니다. 역시 그림으로 먼저 살펴보도록 하겠습니다.
앞의 배열은 이미 정렬이 되어 있다는 전제하에 진행하기 때문에 첫 번째 인덱스는 정렬되어 있다치고 두 번째 인덱스부터 정렬 알고리즘을 수행합니다. 위의 그림대로라면 두 번째 인덱스의 값을 정렬되어있는 앞의 인덱스들 사이에서의 적절한 위치에 삽입시켜주면 됩니다. 즉 적절한 위치는 5의 앞이됩니다.
세 번째 인덱스의 값인 8을 생각해보도록 하겠습니다. 이미 현재 인덱스 이전의 배열은 그들끼리 정렬이 되어있습니다. 즉 현재 인덱스의 바로 전 인덱스는 정렬되어있는 배열들 중 가장 큰 값이 될 것입니다. 여기선 5가 되겠죠. 만일 현재 위치를 결정해주어야 할 인덱스의 값이 바로 이전의 값보다 크다면 정렬된 배열들 중에 가장 큰 값이라는 뜻이므로 삽입할 필요 없이 현재의 위치를 고수해주면 됩니다.
이런식으로 이미 정렬되어 있는 이전 배열에 현재 인덱스의 값의 위치를 찾아내는 것이 삽입 정렬입니다. 삽입 정렬은 조금 특별한데요. 역정렬되어 있는 최악의 경우에는 첫 라운드에는 1번, 그 다음 라운드에는 2번, 3번 .... N - 1의 비교 횟수를 갖고 이로인한 총 비교 횟수는 N * ( N - 1) / 2가 됩니다. 고로 빅오는 O(N^2)이 됩니다.
하지만 이미 정렬이 되어있는 최선의 조건에서는 다른 빅오를 갖습니다.
이미 앞의 배열이 정렬되어있기 때문에 정렬되어 있는 배열 중 가장 마지막 요소와 비교만하기 때문에 총 N번의 비교만 하게 됩니다. 고로 최선의 경우에서 선택 정렬의 빅오는 O(N)이 됩니다.
마무리
오늘은 이렇게 빅오가 O(N^2)인 정렬 알고리즘에 대해서 조금 더 상세하게 공부해보는 시간을 가졌습니다. 정확한 동작 원리와 시간 복잡도를 생각해보니 이전에 코드를 단순히 외우는 것으로 공부했던 것보다 확실히 머리에 더 많이 남는 것 같습니다. 다음 시간에는 나머지 정렬 알고리즘들에 대해 알아보는 시간을 가져보도록 하겠습니다. 감사합니다.
