[정렬 기초] O(n^2) 정렬
정렬(Sort)는 데이터를 정의된 기준으로 순서대로 나열하는 것입니다. 일반적으로 보통 숫자를 순서대로 나열하는 것을 생각하시면 됩니다.
그리고 어떤 자료구조를 사용하나에 따라 위에서 행해지는 알고리즘의 효율이 달라지 듯이 정렬이 어떻게 되었는가에 따라 탐색 등의 실제 시간도 달라지며 ‘이진 탐색’과 같은 탐색 알고리즘은 아예 순차정렬이 이뤄져 있을 때만 사용할 수 있습니다.
그리고 물론 중간 과정인 정렬 또한 어떤 알고리즘을 사용하냐에 따라 그 효율이 천차만별이 됩니다.
오늘 포스팅에서는 시간복잡도가 O(n^2)이 되어 속도가 느리지만, 비교적 구현은 간단한 기초적인 정렬 알고리즘 몇가지의 기본 개념을 이야기 해보겠습니다.
아래 정렬은 중복이 없는 수의 집합을 오름차순 정렬하는 것으로 기준삼습니다.
(중복이 있어도 알고리즘은 적용됩니다.)
1. 선택 정렬 (Selection Sort)
선택 정렬의 원리는 간단합니다. 오름차순으로 선택정렬을 하는 경우 후보 데이터 군에서 최솟값을 찾아 (‘선택’하여) 앞자리의 수와 자리를 교체하는 작업을 반복하는 알고리즘입니다.
알고리즘에서 시간은 실제 시간이 아닌 총 스탭(step)수를 따지는 것이었고, 데이터 개수가 총 n개라면 1라운드에서 최솟값을 찾는 선형탐색에는 최대 n-1회의 스탭이 발생합니다.
교체는 각 라운드 당 최대 한 번이 발생하며, 자리를 ‘교체’하는 것이기에 배열에서는 전체 이동없이 각
위치를 임의접근하여 교체됩니다. 실질적으로 탐색과 교체가 거의 한 템포로 이뤄진다고 생각해도 됩니다.
(참고로 교체는 1라운드 첫째자리, 2라운드 둘째자리… n-1라운드 n-1번째 자리로 교체합니다.)
그리고 각 라운드마다 최솟값이 찾아지므로 라운드가 지날 수록 후보가 감소하기 때문에 라운드를 거치며 스탭수가 1씩 감소하며 전부 탐색하여 교체하는데 최대 n-1라운드(해당 스탭1회)가 필요합니다.
따라서 n개의 수를 선택정렬하는데 총 n-1 라운드 동안 다음과 같이
(n-1) + (n-2) + ... + 2 + 1 : 약 n^2 / 2회의 스탭 수
가 필요로 하며 따라서 선택 정렬은 O(n^2)의 시간복잡도를 갖습니다.
선택 정렬 시간복잡도 : O(n^2)
2. 버블 정렬 (Bubble Sort)
버블 정렬은 오른쪽부터 왼쪽까지 인접 데이터를 2개씩 비교하여 교체해나가는 알고리즘입니다. 이렇게 교체해가는 모습이 거품이 올라오는 모양같다고 해서 명명되었다는데 저는 개인적으로 느낌이 잘….
n개의 수 집합에서 버블 정렬은 1라운드에 뒤 n번째와 n-1번째, n-1번째와 n-2번째… 2번째와 1번째, 총 n-1회의 비교탐색 스탭이 이뤄집니다. 선택 정렬과 마찬가지로 1라운드가 끝나면 가장 왼쪽의 정렬이 확정되어 후보가 하나씩 줄어가므로 최대 총 n-1 라운드가 발생합니다.
버블 정렬은 이미 정렬이 되어 있으면 라운드 당 한 번도 정렬이 발생하지 않을 수 있고, 최악의 경우 비교할 때마다 교체가 이뤄지게 됩니다. 그래도 앞서 선택과 교체가 한 템포라 했듯 여기도 비교와 교체가 한 템포에 이뤄진다고 생각하시면 됩니다.
그럼 총 n-1라운드 동안 다음과 같이 비교탐색 스탭이 발생되므로
(n-1) + (n-2) + ... + 2 + 1 : 약 n^2 / 2회의 스탭 수
버블 정렬도 선택 정렬처럼 O(n^2)의 시간복잡도를 갖습니다.
버블 정렬 시간복잡도 : O(n^2)
그럼 선택 정렬과 버블 정렬은 언제 사용하면 좋을까요? 저의 개인적인 백준 문제 경험 바탕으로 간단히 생각해보면 둘 다 최대 O(n^2) 시간복잡도를 갖지만,
선택 정렬은 다음 최솟값 후보가 무엇인지 알고 있을 때 (n라운드에서 최솟값은 n이라던가) 데이터 상태에 따라 실질적으로 더 빠른 실제 소요시간을 가질 수 있고,
버블 정렬은 인접 데이터끼리 계속 비교해 나가므로 결과적으로 무슨 숫자들이 배치되어 있는지 모르는 경우 쉽고 용이하게 짤 수 있다고 생각합니다.
선택 정렬 : 다음 탐색 값이 무엇인지 알 때 vs 버블 정렬 : 전체적인 데이터 구성을 모를 때
3. 삽입 정렬 (Insertion Sort)
삽입 정렬은 다음 탐색 영역의 데이터를 탐색이 끝난 영역의 데이터 집합 사이 적절한 위치에 ‘삽입’하는 방식의 정렬 알고리즘입니다.
삽입 정렬에서 탐색이 끝난 영역을 확장해나가는 방법은 다음과 같습니다.
1. 맨 왼쪽 데이터는 이미 탐색이 완료된 것으로 여깁니다.
2. 다음 데이터를 탐색이 완료된 데이터들의 '가장 뒤부터' 비교해가며 자리를 교체합니다.
3. 2의 과정이 끝나면 그 영역까지 탐색이 완료된 것으로 하고 다음 데이터로 넘어갑니다.
이와 같은 과정의 반복으로 가장 오른쪽까지 진행해 나갑니다.
이런 삽입 정렬은 항상 후보군 사이 전체 비교가 일어나는 버블정렬과 달리 탐색 비교하는 데이터가 비교되는 ‘탐색 완료 영역의 가장 뒤의 데이터’보다 클 경우(오름차순 기준) 바로 라운드를 종료하게 됩니다.
물론 탐색 완료 영역의 모든 데이터와 교체하는 최악의 경우를 상정하면 n라운드에는 최대 n-1회의 스탭수가 발생합니다. 따라서 선택 정렬, 버블 정렬과 마찬가지로 삽입 정렬 시간 복잡도도 O(n^2)입니다.
버블 정렬 시간복잡도 : O(n^2)
삽입정렬은 다음 후보값이 무엇인지 몰라도 되고 데이터 배열 상태에 따라 실제 시간이 좀 더 빠르게 나올 수 있는 위 두 정렬의 장점이 적절히 갖춰져 있다고 생각합니다.
하지만 여전히 최악의 경우를 상정하면 O(n^2)의 시간복잡도를 갖고 있기에 시간상 좋은 효율의 알고리즘이라 보기는 어렵습니다. 다음에는 구현 난이도는 비교적 높지만 O(n log n)의 시간복잡도를 갖는 기초적인 정렬 알고리즘을 몇 가지 살펴보겠습니다.
언제나 읽어주셔서 감사합니다.^^
개인 공부용 블로그입니다.
잘못된 부분에 언제든지 댓글이나 메일로 지적해주시면 감사하겠습니다.
Leave a comment