Sort Algorithm 정리

O(N^2) Sort

• 버블 정렬(Bubble Sort)

시간복잡도는 거의 모든 상황에서 최악의 성능을 보여준다.

만들기 쉽고 직관적일 뿐 되도록이면 쓰지 말아야 할 정렬.

 

단 예외적으로 이미 정렬된 자료는 1번만 돌면 되기 때문에 최선의 성능을 보여준다.

공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다.

 

• 선택 정렬(Selection Sort)

버블 정렬이 비교하고 바로 바꿔 넣는걸 반복한다면, 선택 정렬은 모든 요소를 훑어서 가장 작은 요소를 골라내는 방식을 n번 반복한다.

버블 정렬과 비슷하지만 보다 개선된 알고리즘이라고 할 수 있다.

 

어떻게 정렬되어있건 일관성있게 n(n-1)/2에 비례하는 시간이 걸린다는 특징이 있고, 버블 정렬보다 일반적으로 2배정도 빠르다.

공간복잡도는 역시 단 하나의 배열에서만 진행하므로 O(N)이다.

 

• 삽입 정렬(Insertion Sort)

모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열과 비교하여 정렬된 배열 내 자신의 위치를 찾아 삽입함으로서 정렬을 완성.

 

평균적으로 O(N^2)중에서 빠른편이나 자료구조에 따라선 밀어내는데 오랜 시간이 걸린다.

하지만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우, 오버헤드가 매우 적기 때문에 이름처럼 최선의 알고리즘이 된다.

O(NlogN) Sort

• 합병 정렬(Merge Sort)

합병 정렬은 퀵 정렬보다 느리고 데이터 크기만한 메모리가 더 필요하므로 공간복잡도도 크다.

 

하지만 합병 정렬의 최대의 장점은 정렬 시 같은 값이라도 기존 데이터의 순서를 유지한다는 점이다.

이러한 정렬을 Stable Sort 라고도 한다.

 

• 힙 정렬(Heap Sort)

기본적인 알고리즘은 선택 정렬과 동일하다.

하지만 힙 정렬의 경우 최소값, 최대값을 찾을때 배열을 순회하는게 아니라 만들어둔 힙을 사용하므로,

찾는데엔 O(logN) 그러므로 정렬에는 총 O(NlogN)의 시간복잡도를 갖게된다.

 

힙 정렬은 추가적인 메모리를 전혀 필요로 하지 않는다. 또한 최악의 경우 O(N^2)의 성능을 내는 퀵 정렬과는 다르게 항상 일정한 성능을 발휘하므로 최소한의 알고리즘만 정의할 경우 힙정렬이 가장 안정적인 성능을 갖는다.

 

Q1) 힙 정렬이 퀵 정렬보다 좋은 점은?

Q2) 그럼에도 퀵 정렬이 일반적인 경우에 더 빠른 이유는?

 

• 퀵 정렬(Quick Sort)

평균적인 상황에서 최고의 성능을 나타낸다.

컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이며, 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다.

 

방식은 먼저 적절한 원소 하나를 기준(피벗, pivot point)으로 삼아 그보다 작은것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈다.

 

합병 정렬과는 다르게 unstable sort 이므로 동일 값을 갖는 원소의 순서가 변할 수 있다.

최악의 경우엔 시간복잡도가 O(N^2)가 되는데 피벗을 최솟값이나 최댓값을 계속해서 잡게되는 경우가 그렇다.

퀵 정렬의 경우 피벗을 어떤 값을 잡느냐에 따라 효율이 천차만별로 달라지므로 피벗고르는것이 가장 중요하다.

 

Q1) 그렇다면 피벗을 잡는 방법으로는 어떤것들이 있을까?

 

 

정렬 알고리즘 시간복잡도 비교

• 구현이 간단하지만 비효율적인 방법
  - 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort)
• 복잡하지만 효율적인 방법
  - 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort)