시간복잡도 O(N^2)는 느리지만 구현이 매우 단순한 bubble, selection, insertion 3가지 알고리즘에 대해 알아보겠다. 그전에, 알고리즘 분류에 대해 먼저 알아보겠다.
In-place sort
위키백과 ‘정렬 알고리즘’ 설명에서 제자리 정렬(in-place 정렬)에 대해 나온다.
제자리 정렬은 원소들의 개에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘들을 의미.
여기서 충분히 무시할 만한 이라는 말이 너무 애매한 단어다. 좀 더 구체적으로 하면, N에 비례하지 않는 정도로 해석할 수 있고 좀 더 넓게 해석하자면, N에 선형적으로 비례하지 않는 정도로 해석할 수 있을 것 같다.
stable sort
sort 과정에서 동일한 key 값을 가진 원소들의 순서가 바뀌지 않는 정렬을 stable한 정렬이라고 한다.
online sort
모든 원소들이 처음부터 주어지는 것이 아니라, 차례대로 들어오는 경우도 처리할 수 있는 알고리즘을 의미.
대표적으로 merge sort를 온라인 정렬로 만들 수 있다.
인접한 두 원소를 비교하여 교환하는 방식으로 정렬하는 알고리즘이다.
3가지 알고리즘 중 가장 느리지만, in-place, stable 정렬이다.
시간복잡도 최선, 평균, 최악 모두 O(N^2)이다.
** 향상된 bubble sort
교환이 발생하지 않는 round는 이미 모든 원소가 정렬되어 있는 것이므로 정렬을 마칠 수 있다.
최선의 경우 시간복잡도가 O(N)으로 향상된다.
주어진 원소들 중 최소값을 찾아 맨 앞에 위치한 값과 교환한다.
맨 앞을 제외한 원소들끼리 이를 반복하여 정렬하는 알고리즘.
버블정렬보다 빠르며 in-place이지만 일반적으로 unstable 정렬이다. (예시 2213)
시간복잡도 최선, 평균, 최악 모두 O(N^2)이다.
** stable한 selection sort
선택정렬도 stable하게 만들 수 있다.
교환(swap) 대신 삽입(insertion)하면 된다.
위에서 예로 든, 2213을 살펴보자. 앞의 2와 뒤의 2가 헤깔리니까 뒤의 2는 2’ 라고 하겠다.
2 2' 1 3 에서 최솟값인 1을 맨 앞의 2와 교환하면1 2' 2 3 이 되어 unstable이다.2 2' 1 3에서 최솟값인 1을 다른 임시변수에 저장해두고 한칸씩 당기면_ 2 2' 3 이 되고 맨 앞에 1을 삽입하면 1 2 2' 3 이 되어 stable한 선택 정렬이 된다.2번째 원소부터 시작해 이미 정렬된 앞의 원소들을 차례로 비교해 자신의 위치를 찾아가며 정렬하는 알고리즘.
위의 두 정렬보다 더 빠르며 in-place이고 stable 정렬이다.
시간복잡도 최선 O(N)이고, 평균, 최악 O(N^2)이다.