데이터 정렬을 위한 알고리즘에는 여러 가지가 있다. 알고리즘마다 시간 복잡도도 다르다. 정렬 알고리즘 중 지수 시간**(O(nˆ2))** 복잡도 알고리즘들은 단순하고 이해하기 쉽다. 이들은 주로 항목이 천개 이하로 많지 않은 경우에 사용된다. 대표적으로 선택정렬, 삽입정렬이 있다.
삽입정렬 알고리즘은 지수시간 알고리즘이긴 하지만, 데이터가 어느정도 정렬되어 있을 때는 데이터의 양이 방대하다 하더라도 효율적으로 동작한다. 정렬되지 않은 데이터가 적을 경우 삽입 정렬의 복잡도가 O(n)이 된다. 이 경우에 한해 삽입 정렬이 어떤 정렬 알고리즘보다 연산을 적게 요구한다.
하지만 데이터가 뒤죽박죽이라면 병합 정렬(merge sort), 퀵 정렬(quick sort) 같은 O(n log n)의 시간 복잡도를 가진 알고리즘이 유리하다,
병합정렬
병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘이다. 병합 정렬은 다음과 같은 알고리즘을 사용한다.
1. N의 길이를 가진 배열 리스트를 1의 길이를 가진 "부분 리스트"가 N개 모인 것으로 취급합니다.
2. 인접한 부분 리스트들을 정렬하여 2의 길이를 가진 부분 리스트로 병합합니다.
3. 2의 길이를 가진 인접한 부분 리스트들을 4의 길이를 가진 부분 리스트로 합칩니다.
4. 하나의 정렬된 리스트가 될 때까지 위 과정을 반복합니다.
5. N이 홀수라면, 첫 번째 병합 때 1의 길이를 가진 부분 리스트를 남깁니다.병합 정렬은 두 가지 방식으로 구현 가능합니다. 반복적 접근(하->상) 과 재귀적 접근(상->하)
반복적 접근
주어진 배열이 "정렬된" 부분 리스트로 나뉘어집니다.
[4,7,4,3,9,1,2] -> [[4],[7],[4],[3],[9],[1],[2]]
인접한 부분 리스트 2개가 정렬된 부분 리스트로 병합됩니다.
[[4],[7],[4],[3],[9],[1],[2]] -> [[4,7],[3,4],[1,9],[2]]
병합 과정 (반복) :
[[4,7],[3,4],[1,9],[2]] -> [[3,4,4,7], [1,2,9]]
병합 과정 (반복) :
[[3,4,4,7], [1,2,9]] -> [[1,2,3,4,4,7,9]]
마무리 : 정렬된 배열이 리턴됩니다.
[1,2,3,4,4,7,9]
재귀적 접근
주어진 배열을 절반으로 나눕니다.
4, 7, 4, 3, 9, 1, 2 -> 4, 7, 4, 3, 9, 1, 2
두 배열이 재귀적으로 정렬됩니다.
4, 7, 4 -> 4, 4, 7 -> 1, 2, 3, 9
두 배열이 병합됩니다.
4, 7, 4, 3, 9, 1, 2 -> 1, 2, 3, 4, 4, 7, 9
2단계에서 나뉘어진 각각의 배열 4, 7, 4에 대해서도 1-3번의 과정이 재귀적으로 똑같이 진행됩니다.
주어진 배열을 절반으로 나눕니다.
4, 7, 4 -> 4, 7, 4
두 배열이 재귀적으로 정렬됩니다.
4 -> 4 -> 4, 7
두 배열이 병합됩니다.
4, 4, 7 -> 4, 4, 7
이 과정의 2단계에서 나뉘어진 4, 7에 대해서도 재귀가 호출됩니다.
4는 원소가 하나이기 때문에 정렬하지 않아도 되겠죠?
주어진 배열을 절반으로 나눕니다.
7, 4 -> 7, 4
두 배열이 재귀적으로 정렬됩니다.
7 -> 7 -> 4
두 배열이 병합됩니다.
7, 4 -> 4, 7
모든 재귀 호출이 완료되면 3단계에서 병합이 되기 때문에 최종적으로 정렬된 하나의 배열이 리턴됩니다.
퀵정렬
퀵 정렬은 병합 정렬과 보통 많이 비교되곤 한다. 둘 다 평균적으로 O(nlogn)의 성능을 갖기 때문이다.
퀵 정렬, 병합 정렬 공통점
Divide and Conquer(분할-정복) 알고리즘에 속한다.
둘 다 점점 탐색할 배열의 크기를 쪼개서 재귀함수에 넘겨준다.
퀵 정렬, 병합 정렬 차이점
병합정렬은 배열을 분할하는 방식이 반으로 쪼개는 것
퀵 정렬은 크게 두 가지 분할 방법이 있다(in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법)
퀵 정렬은 병합정렬과 달리 다른 메모리 공간을 사용하지 않는다. (오직 재귀 콜 스택을 위한 메모리만 사용됨, 그에 반면 병합정렬은 매 번 새로운 배열을 만들어 내므로 메모리 사용량이 더 큼)
드물지만, 파티션의 방법에 따라 최악의 경우에 O(n²) 까지 성능이 낮아질 수 있음.
병합정렬은 stable 하지만, 퀵 정렬은 unstable 하다. (원소들 중에 같은 값이 있는 경우에 정렬 이후 순서가 초기 순서와 달라 질 수 있기 때문에)
Basic Quick Sort - Not In Place
퀵 정렬은 Divide and Conquer 전략을 사용한 알고리즘이다.
즉, 정렬하는데 가장 간단한 배열은 바로 요소가 없거나 하나만 있는 배열이므로 모든 배열이 기본 배열이 될 때까지 큰 배열을 나눠야한다.
이 때 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다. 그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.
pivot 왼쪽에 놓여진 기준 원소보다 작은 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 배열을 pivot을 기준으로 나눈다. 이 방법을 반복하면 결국 기본 단계인 원소가 하나만 있는 배열이 남는다.
기준 원소를 고른다. 여러 가지 방법이 있겠지만 위 그림에서는 배열의 첫 번째 요소를 기준 원소로 설정했다.
배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 2개의 하위 배열로 분할한다.
하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.
위 방법의 퀵 정렬은 in place 방법이 아니기 때문에 별도의 메모리 공간이 필요하므로 데이터의 양이 많으면 공간적인 낭비가 심해져 실제로는 잘 쓰이지 않는 방법이다. 그러나 위의 방법으로 퀵 정렬을 할 경우에 중복되는 데이터는 순차적으로 pivot에 넣으면 되기 때문에 정렬 전 중복 데이터의 순서가 바뀌지 않는 stable한 정렬을 구현할 수 있다.
In place Quick Sort
위의 방법은 이해하기에 훨씬 쉽고 구현도 간단하지만 메모리 공간의 낭비가 심하기 때문에 위 방법보다는 in place 방법이 훨씬 더 많이 사용된다.
정렬되지 않은 데이터에서 가운데 원소를 pivot으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점이다.
가장 왼쪽부터 값을 pivot값을 비교하여 pivot보다 큰 값이 나타날 때까지 칸을 오른쪽으로 이동한다.
가장 오른쪽부터 값을 pivot값을 비교하여 pivot보다 작은 값이 나타날 때까지 칸을 왼쪽으로 이동한다.
pivot보다 큰 왼쪽 값과 pivot보다 작은 오른쪽 값을 서로 교환한다.
왼쪽 인덱스가 오른쪽 인덱스보다 커지면 이동을 멈추고 그 자리에서 두 배열로 갈라서
각 배열에 위와 같은 방식으로 재귀 호출하여 정렬한다.
이 방법은 추가적인 공간을 필요로하지 않기 때문에 메모리 공간이 절약된다는 장점이 있으나, 왼쪽과 오른쪽 값을 교환하는 과정에서 중복값의 위치가 바뀔 수 있으므로 unstable한 정렬 방법이다.
기수 정렬(Radix sort) / 계수 정렬(Counting sort)
1. 기수 정렬(Radix sort)
자리 수를 비교해서 정렬하는 방식
가장 낮은 자리 수부터 비교하여 정렬 수행 (비교 연산을 하지 않음)
기수정렬이 올바르게 동작되기 위해 각 자리에 사용될 정렬 알고리즘이 안정적이어야 함
Radix sort(기수 정렬)는 0의 자리, 10의 자리, 100의 자리 ... 1 * (0의 n개) 자리수를 기준으로 정렬하는, 비교 연산을 하지 않는 정렬 기법이다.(기수 : 주어진 데이터를 구성하는 기본 요소. 2진수는 0과 1, 10진수는 0~9, 영문자는 a~z까지 각 기수의 개수만큼 만드는 것)
O(n)이라는 굉장이 짧은 시간복잡도로, 정렬법들 중 O(NlogN)을 깨는 유일한 정렬법으로, 문자열이나 정수 정렬에사용가능하며 속도도 매우 빠르지만 부동 소숫점 실수 같이 자릿수가 없는 경우 정렬할 수 없고 데이터 타입이 일정해야 하고, 양의 정수는 양의 정수 끼리 음의 정수는 음의 정수끼리 비교해야 하는 등 구현에 많은 조건이 붙어 사용이 까다롭다. 또한 제자리 정렬이 아니기 때문에 추가적인 메모리 공간이 필요하다.
기수 정렬은 보통 내부적으로 중간 정렬을 사용하는데, k(요소 중 최댓값)에 따라 사용되는 중간 정렬이 다르다.k가 작을 때는 counting sort(계수 정렬)을, k가 클 때는 quick sort를 사용하는 것이 좋다.
2. 계수 정렬(counting sort)
Counting sort(계수정렬)는 각 요소의 배열 등장 횟수를 count해 누적합으로 나타내는 배열을 만든 뒤, 그 누적합으로 요소들의 index를 알아내 작은 숫자 순서대로 정렬하는 기법이다.
비교 정렬이 아니기 때문에**O(n + k)**라는 특이한 시간 복잡도를 가진다. k는 Input 요소의 최댓값인데, k가 작은 수라면 O(n)이겠지만, k가 무한으로 커질 때는 O(무한)이 될 수도 있다.
따라서 요소의 최댓값에 영향을 받는 알고리즘이다.
각 원소들 사이에 **비교하지 않는 정렬이며 안정성(stable)**을 가짐
임시작업에 사용되는 메모리를 필요로 함 (각 숫자를 counting하여 누적시킬 배열과 정렬된 배열)
정렬할 배열의 원소와 숫자를 counting하여 누적시킨 후 그 값들을 정렬된 배열의 인덱스로 사용