정렬 알고리즘

정렬 알고리즘이란?

정렬 알고리즘은 원소들을 일정한 순서대로 열거하는 알고리즘을 말한다.
정렬 알고리즘의 대표적인 예시로는 삽입 정렬(Insertion sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble sort), 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap sort)이 있다.

---

Stable vs Unstable

정렬을 진행할 때, 같은 값의 원소더라도 상대적인 위치가 유지 되면 stable한 정렬 방식, 그렇지 않으면 unstable한 정렬 방식이다.

예를 들어, 아래의 숫자들을 오름차순으로 정렬해보자. 이때, 1’과 1은 같은 숫자이다.
5 3 1` 9 2 1
정렬 알고리즘이 수행 된 이후 1` 1 2 3 5 9 로 정렬 되었다면 상대적인 위치가 유지되었으므로 stable하다고 할 수 있고, 그렇지 않으면 unstable한 알고리즘이다.

stable 정렬에는 Insertion sort, Bubble sort, Merge sort가 있고,
unstable 정렬에는 Selection sort, Quick sort, Heap sort가 있다.

---

삽입 정렬 (Insertion sort)

새로운 원소를 삽입할 때, 기존의 정렬된 원소들 사이에서 올바른 자리를 찾아 삽입하는 정렬 방식이다.
2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입한다.

최악의 경우 (입력 자료가 역순인 경우) 외부 루프를 N-1번 도는 동안 비교연산은 1, 2, ... , (N-1)번 수행된다.
따라서 시간 복잡도는 (n-1)+(n-2)+(n-3)+ ... +2+1 => n(n-1)/2이 되어, O(N^2)이다.


장점

• 레코드의 수가 적은 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 비교할 수가 많고 크기가 클 경우에 적합하지 않다. (배열의 길이가 길어질수록 비효율적)

---

선택 정렬 (Selection Sort)

원소를 넣을 위치를 미리 정해두고, 그 위치에 어떤 원소를 넣을지 선택하여 정렬하는 방식이다.
- 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

한 회차가 수행될 때마다 1개 위치의 원소가 확정 되어, 다음 정렬에서 정렬해야 할 요소가 1개 감소한다.
따라서 시간 복잡도는 (n-1)+(n-2)+(n-3)+ ... +2+1 => n(n-1)/2이 되어, O(N^2)이다.

장점

• 정렬을 위한 비교 횟수는 많지만, 상대적으로 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬이다. ( 선택정렬이 불안정정렬인 이유: https://godgod732.tistory.com/13)

---

버블 정렬 (Bubble sort)

서로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방식으로 원소들을 정렬하는 방식이다.

한 회차가 수행될 때마다 가장 큰 자료가 맨 뒤로 이동하므로, 다음 정렬에서 정렬해야 할 요소가 1개 감소한다.
따라서 시간 복잡도는 (n-1)+(n-2)+(n-3)+ ... +2+1 => n(n-1)/2이 되어, O(N^2)이다.

장점

• 안정 정렬이다.
• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 정렬하는 방식이므로, 추가적인 메모리 공간을 필요로 하지 않는다.

단점

• 모든 다른 원소들과 교환이 이루어져야 하기 때문에 역순 배열을 정렬할 때 가장 느리다
  > 일반적으로 자료의 교환(swap) 작업이 이동(move) 작업보다 복잡하기 때문에 거의 쓰이지 않는 정렬 알고리즘이다.

---

힙 정렬 (Heap Sort)

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.
Heap sort가 이루어지는 과정은 다음과 같다. (예시는 최대 힙으로 들겠다.)

1. 최대 힙을 구성한다.
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서(이 때 루트 값이 꺼내진다) 배열의 뒤부터 저장한다..
3. 루트 노드를 마지막 노드로 대체하고 다시 최대 힙을 구성한다.

시간 복잡도는 힙은 완전 이진 트리이기 때문에 전체 높이가 logN이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 logN만큼 소요된다.
요소의 개수가 n개 이므로 전체적으로 O(NlogN)의 시간이 걸린다.

장점

• 시간 복잡도가 좋은 편이다.
• 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 정렬하면 될 때 특히 유용하다.

---

합병 정렬 (Merge Sort)

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 분할 정복 알고리즘을 통해 구현된다.

시간 복잡도를 계산 해 보면,

N = 2^k 개의 원소를 정렬한다고 가정할 때, 순환 호출의 깊이는 k가 된다.
k = logN이므로 재귀 호출이 실행되는 횟수는 logN이다.
그리고 한번의 합병이 일어날 때마다, 임시배열에 원소를 정렬하는 과정에서 원소 개수(N)만큼의 비교연산이 수행된다.
따라서 둘을 곱하여 시간 복잡도는 O(NlogN)이 된다.


장점

• 안정적인 정렬 방법이다.
• 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.

단점

• 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.

---

퀵 정렬 (Quick sort)

기본적으로 분할 정복 알고리즘을 사용한다는 점에서 합병 정렬과 매우 유사하나, 선택한 pivot을 기준으로 목록을 큰 값과 작은 값으로 나누어 가며 정렬한다는 점에서 차이가 있다.
Quick sort가 이루어지는 과정은 다음과 같다.

1. 배열 가운데서 하나의 원소를 골라 pivot으로 설정한다.
2. pivot을 기준으로 pivot보다 작은 원소들은 pivot의 왼쪽으로 옮기고, 큰 요소들은 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 같은 방법으로 정렬한다.

이 정렬 방식은 pivot을 어떻게 정하느냐에 따라 시간 복잡도가 달라지기 때문에, 시간 복잡도가 최선인 경우와 최악인 경우가 나뉜다.
레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, 시간 복잡도가 최선인 경우는 정확하게 절반씩 나누어져 재귀 호출이 logn번 실행되는 경우다.
따라서 merge sort 와 동일하게 재귀호출 logN번, 비교 연산 N번이 수행되어 O(NlogN)의 시간복잡도를 가진다.
그러나 시간 복잡도가 최악인 경우를 살펴보면,

리스트가 불균형하게 나누어지는 경우, 순환 호출이 n번 발생한다. 비교 연산 진행 시 각 호출에서 n번의 비교가 이루어지므로 최악 시간 복잡도는 O(n^2)이다.

장점

• 속도가 빠르다.
  평균적으로 O(n logn) 의 시간복잡도를 가지는데, 한 번 결정된 pivot들이 추후 연산에서 제외되는 특성 때문에 시간 복잡도가 O(nlogn)인 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 추가적인 메모리 공간을 필요로 하지 않는다.

단점

• 퀵 정렬의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸릴 수도 있다.

---

최종적으로, 모든 정렬 알고리즘의 시간 복잡도를 요약하면 다음과 같다.

참고 자료

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

https://github.com/WooVictory/Ready-For-Tech-Interview/tree/master/Algorithm

GitHub - WooVictory/Ready-For-Tech-Interview: 💻 신입 개발자로서 준비를 하기 위해 지식을 정리하는 공간

https://yabmoons.tistory.com/250

[ 정렬 ] 정렬별 장단점 및 시간복잡도