[Algorithm] 정렬 알고리즘 간단 정리와 Python 구현 (버블정렬, 선택정렬, 퀵정렬, 병합정렬, 힙정렬)

 

데이터 베이스는 이론상 무한 개의 데이터를 다룰 수 있어야 하기 때문에, 수많은 데이터를 얼마나 빠르게 정렬하는 가는 중요한 문제이다. 

 

🤔 그렇다면 왜 데이터는 정렬되어 있어야할까?

간단히 말하자면 탐색을 위해서 이다. 

정렬되어 있지 않은 데이터에서는 순차 탐색(O(N)) 밖에 사용할 수 없으나, 데이터가 정렬되어 있다면 이진 탐색(O(logN))이라는 알고리즘을 활용할 수 있다.

삽입/삭제가 자주 일어나는 데이터의 경우 정렬에 더 많이 시간이 들어감으로 순차 탐색을 사용하는 경우도 있지만, 보통의 경우는 데이터를 조회하는 경우가 훨씬 많다. 그리고 조회에 필요한 것이 검색(탐색)이다.

 

 

1. 버블 정렬

---

최댓값을 우선적으로 정렬하는 알고리즘이다.

👉 동작 방식

• 0부터 N-1까지 탐색하면서 인접한 칸과 비교하여 swap하는 방식이다.
• 첫 번째는 0~N-1, 두 번째는 0~N-2 이런 식으로 진행되는데 그 이유는 1회 실시할 때 최댓값은 이미 맨 뒤로 저장되어 있기 때문이다.

 

 

이를 그림으로 살펴보자.

 

👉 시간 복잡도

시간 복잡도는 아래의 식으로 인해 N제곱을 가진다.

$$(N-1) + (N-2) + (N-3) + ... + 1 = 1/2N^2 - 1/2N = O(N^2)$$

 

 

 

2. 선택 정렬

---

최소값을 우선적으로 정렬하는 알고리즘이다.

👉 동작 방식

1. 탐색을 시작하는 Index를 최소 값을 가지는 Index라고 가정한다. 
2. 오른쪽으로 탐색을 진행하며 더 작은 값을 만나면 최소 값을 가지는 Index를 변경한다. 
3. 끝까지 도달했을 때, 탐색을 시작하는 Index의 값과 최소 값을 가지는 Index의 값을 swap 한다.

 

이를 그림으로 살펴보자.

 

👉 시간복잡도

시간 복잡도는 아래의 식으로 인해 N제곱을 가진다.

$$(N-1) + (N-2) + (N-3) + ... + 1 = 1/2N^2 - 1/2N = O(N^2)$$

 

 

 

3. 퀵 정렬

---

일정한 기준을 잡고, 더 작은 값은 왼쪽으로 더 큰 값은 오른쪽으로 정렬하는 알고리즘이다.

👉 동작 방식

1. pivot 값을 지정한다. (pivot 값을 지정하는 방식은 알고리즘마다 다르나, 현재는 가장 왼쪽의 값을 지정하겠다.)
2. left/right(배열 가장 왼쪽의 Index/배열 가장 오른쪽의 Index)를 지정한다.
3. left에서 오른쪽으로 탐색하며 pirvot 값보다 큰 값을 찾는다. right에서 왼쪽으로 탐색하며 pivot 값보다 더 작은 값을 찾는다.
4. left, right의 이동이 멈추면 "left <= right"를 확인한다.
   1. If true: 두 인덱스의 값을 swap한다. 그리고 3번으로 돌아간다. 
   2. If false: 5번으로 넘어간다.
5. right와 pivot의 값을 swap한다. (이로써 pivot 값에 대한 정렬은 완료되었다.)
6. pivot 값을 기준으로 왼쪽, 오른쪽 배열에 대해서 1번 과정부터 반복한다.

 

👉 시간 복잡도

이상적인 pivot 값을 골라 정확하게 반으로 나누어질 경우의 시간 복잡도를 계산해보자.

pivot값을 중심으로 2개로 나누어지는 것이 트리형 모델을 닮아있다.

그럼 원소가 1인 배열까지 쪼갰을 때, 이 모델의 깊이는? logN일 것이다. 

그리고 각 층에서 연산이 총 N번 반복되기 때문에 총 시간 복잡도는 O(NlogN)이다.

 

아래 그림을 보면 이해가 쉬울 것이다.

 

반대로 최악의 경우로 최소값과 최대값을 계속해서 뽑을 경우는 아래와 같다.

$$(N-1) + (N-2) + (N-3) + ... + 1 = 1/2N^2 - 1/2N = O(N^2)$$

 

👉 특징

• pivot 값에 따라 시간 복잡도가 달라지기 때문에 중앙값에 가까운 pivot 값을 선택할 수 있는 전략이 요구된다.
• 원소 개수가 적어질수록 나쁜 중간값이 선택된 확률이 높다. 원소 개수에 따라 퀵 정렬에 다른 정렬을 혼합해서 쓰는 경우가 많다.
• Python의 list.sort() 함수가 퀵 정렬을 기본으로 사용한다. 

 

 

 

4. 병합 정렬

---

배열을 모두 분리하고, 정렬하면서 합치는 알고리즘이다.

👉 동작 방식

1. 재귀 함수를 통해서 요소가 1개가 될 때까지 나눈다. 
2. 나누어진 배열을 다시 합친다. 
   
   1. 두 배열의 가장 왼쪽의 인덱스를 각각 left_index, right_index로 지정한다. 
   2. 임시 배열(temp)를 생성하고, left_index와 right_index의 값을 비교해 더 작은 값을 temp에 삽입한다. 더 작은 값을 삽입한 배열의 index는 1을 더한다. (오른쪽으로 탐색)
   3. 두 배열 중 한 배열의 탐색이 끝날 때까지 2번 과정을 반복한다.
   4. 한 배열의 탐색이 끝났다면 나머지 배열의 값을 temp에 삽입한다.

 

그림으로 보면 아래와 같다.

 

👉 시간 복잡도

퀵정렬과 비교해보자!

병합정렬은 퀵정렬과 비슷하게 트리형의 모델을 띄어서 나누는 횟수가 같고, 층마다 N번 연산을 하기 때문에 총 시간 복잡도는 O(NlogN)이다.

 

하지만 이는 퀵정렬에서 pivot 값을 이상적으로 잡았을 때의 얘기이다. 퀵정렬의 최악의 경우에는 N제곱의 시간복잡도를 가진다. 

그런데 병합정렬은? 그럴 일이 없다. 어떤 상황에서는 정확히 반으로 나누기 때문이다. 

🤔 그렇다면 병합정렬이 퀵정렬보다 더 좋은 알고리즘일까?
그렇다고 할 수는 없다. 왜냐하면 병합정렬에서는 임시 배열인 temp가 배열을 합칠 때마다 발생하는 큰 단점이 있기 때문이다. 

 

 

 

5. 힙 정렬

---

최대 힙의 루트 노드에 가장 큰 수를 뒤로 보내, 큰 수부터 순서대로 정렬하는 알고리즘이다.

👉 동작 방식

1. 최대 힙을 구성한다. 
2. 0번 인덱스와 N-1번 인덱스를 swap한다. (N-1 위치의 정렬이 끝난다.)
3. 새로운 루트 노드로 N-2번째 인덱스까지 배열에 대해 최대힙을 진행한다. 
4. 0번 인덱스와 N-2번 인덱스를 swap한다. (N-2 위치의 정렬이 끝난다.)
5. 위 사항을 반복한다.

 

👉 시간 복잡도

• 최대힙 구성: root를 제외한 모든 노드를 확인 > N-1
• 최대힙 재구성: root에서 내려옴으로 O(logN). 이를 N-1번 반복하니깐 > (N-1)O(logN)

총 시간복잡도: N-1 + (N-1)O(logN) > O(NlogN)

 

 

 

결론

---

이름	장점	단점	시간복잡도 (최선/보통/최악)
버블 정렬	구현이 쉬움	비효율적	$$O(N^2)/O(N^2)/O(N^2)$$
선택 정렬	구현이 쉬움	비효율적	$$O(N^2)/O(N^2)/O(N^2)$$
퀵 정렬	실행시간이 O(NlogN)	성능차이가 심함	$$O(NlogN)/O(NlogN)/O(N^2)$$
힙 정렬	실행시간이 O(NlogN)	추가적인 메모리 필요	$$O(NlogN)/O(NlogN)/O(NlogN)$$
삽입 정렬	실행시간이 O(NlogN)	실제 시간이 다른 O(NlogN)보다 느림	$$O(NlogN)/O(NlogN)/O(NlogN)$$

 

 

 

---

참고 👍

https://yabmoons.tistory.com/250

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