O(N^2) 정렬
버블정렬(Bubble Sort)
버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다.
오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다. 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에 (전체 배열의 크기 – 현재까지 순환한 바퀴 수)만큼만 반복해주면 된다.
특징
시간복잡도는 거의 모든 상황에서 최악의 성능을 보여준다. 만들기 쉽고 직관적일 뿐 되도록이면 쓰지 말아야 할 정렬.
단 예외적으로 이미 정렬된 자료는 1번만 돌면 되기 때문에 최선의 성능을 보여준다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.
선택정렬(Selection Sort)
버블 정렬이 비교하고 바로 바꿔 넣는걸 반복한다면, 선택정렬은 모든 요소를 훑어서 가장작은 요소를 골라내는 방식을 n번 반복한다.
버블정렬과 비슷하지만 보다 개선된 알고리즘이라고 할 수 있다.
특징
어떻게 정렬되어있건 일관성 있게 n(n-1)/2 에 비례하는 시간이 걸린다는 특징이 있고, 버블 정렬보다 일반적으로 2배정도 빠르다.
공간복잡도는 역시 단 하나의 배열에서만 진행하므로 O(n)이다.
삽입정렬(Insertion Sort)
모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열과 비교하여 정렬된 배열 내 자신의 위치를 찾아 삽입 함으로서 정렬을 완성.
특징
평균적으로 O(n^2)중에서 빠른편이나 자료구조에 따라선 밀어내는데 오랜 시간이 걸린다.
하지만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우, 오버헤드가 매우 적기 때문에 이름처럼 최선의 알고리즘이 된다.
O( N * log(N) ) 정렬
합병정렬(Merge Sort)
원소 개수가 1 또는 0이 될 때 까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나간다.
병합된 부분은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다.
특징 :
합병정렬부터는 시간복잡도가 O(n log n) 이므로 위의 O(n^2)보다 비교도 안되게 빠르다.
이 중 합병정렬은, 퀵 정렬보다 느리고 데이터 크기만한 메모리가 더 필요하므로 공간복잡도도 크다.
하지만 합병정렬의 최대의 장점은 정렬 시 같은 값이라도 기존 데이터의 순서를 유지한다는 점이다. 이러한 정렬을 Stable Sort라고도 한다.
Q1 )같은 값들이 여러개인데 이들의 순서를 기존과 유지하고 싶을때 쓰는 정렬?
Q2 )정렬된 두 배열의 정렬된 합집합을 구하기 위해서 사용하는 방법은?
힙 정렬(Heap Sort)
원소들을 전부 힙에 삽입한다. 그리고 힙의 루트에 있는 값은 남은 수 들중에서 최소값(최대힙이라면 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.
이를 힙이 빌 때까지 반복한다.
특징
기본적인 알고리즘은 선택 정렬과 동일하다. 하지만 힙 정렬의 경우 최소값, 최댓값을 찾을때 배열을 순회하는게 아니라 만들어둔 힙을 사용하므로. 찾는데엔 O(log n) 그러므로 정렬에는 총 O(nlog n)의 시간복잡도를 갖게 된다.
힙정렬은 추가적인 메모리를 전혀 필요로 하지 않는다. 또한 최악의 경우 O(N^2)의 성능을 내는 퀵정렬과는 다르게 항상 일정한 성능을 발휘하므로 최소한의 알고리즘만 정의할 경우 힙정렬이 가장 안정적인 성능을 갖는다.
Q1) 힙 정렬이 퀵 정렬보다 좋은 점은?
Q2) 그럼에도 퀵 정렬이 일반적인 경우에 더 빠른 이유는?
퀵 정렬(Quick Sort)
이름처럼 평균적인 상황에서 최고의 성능을 나타낸다.
컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이며, C, C++, PHP, Java등 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다.
방식은 먼저 적절한 원소 하나를 기준(피벗 ,pivot)으로 삼아 그보다 작은것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈다.
그리고 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.
특징
합병정렬과는 다르게 unstable sort이므로 동일 값을 갖는 원소의 순서가 변할 수 있다.
최악의 경우엔 시간복잡도가 O(n^2)가 되는데 피벗을 최솟값이나 최댓값을 계속해서 잡게되는 경우가 그렇다.
퀵정렬의 경우 피벗을 어떤 값을 잡느냐에 따라 효율이 천차만별로 달라지므로 피벗고르는것이 가장 중요하다.
피벗 잡는 방법.
- 난수(Random Quick Sort), 중위법
- 가장 쉽고 비효율적인 방법.
- 배열 중에 3개나 9개의 원소를 골라서 이들의 중앙값을 피벗으로 고르는 것
- Visual c++과 gcc에서 구현하고 있는 방법이라고 한다.
- 이 방법을 사용하더라도 최악의 경우가 나올 수 있지만 그 경우가 극히 드물게 된다.
- 인트로 정렬
- 재귀 깊이가 어느 제한 이상으로 깊어질 경우 힙 정렬 알고리즘을 사용하여 항상 O(n log n)을 보장해주는 방법
팀 정렬
팀 정렬은 병합정렬과 삽입정렬을 혼합한 방법으로서, 2002년에 파이썬으로 최초구현됐다.
병합정렬은 원소의 개수가 적을 경우 오버헤드가 발생하기 때문에 파티션 크기가 특정 값 이하(보통 16 또는 32)가 되면 삽입 정렬을 사용한다.
병합 정렬과 비슷한 특징을 가지며 대부분의 경우 더 빠르다. 가장 많이 쓰이는 정렬 중 하나.
각 언어에서 사용하는 정렬 알고리즘은?
Java
Arrays.sort에서는 퀵 정렬
Collections.sort에서는 합병 정렬
Q. 퀵 정렬이 일반적으로 더 빠른데 Collcetions.sort에서 합병 정렬을 사용하는 이유는?
A. stable하지 않고, 일정한 효율 O(n log n)을 보장하지 않는다.
파이썬
파이썬도 역시 퀵정렬을 하지 않는다. 이유는 역시 Stable하지 않기 때문이다. 파이썬은 대신 팀 정렬(Tim sort)을 사용한다.
