정렬 알고리즘 정리

정렬 알고리즘 정리

---

정렬은 쉽게 간단히 구현할 수 있는 간단한 정렬과 복잡하게 구현하는 복잡한 정렬이 있다. 당연한 이야기지만 간단한 정렬은 그만큼 성능이 떨어지며, 복잡한 정렬은 구현이 쉽지 않지만 그만큼 성능이 좋다. 이번 포스팅에서는 정렬 알고리즘에 대해 정리해보고자 한다.

 

버블정렬

---

버블정렬은 말 그대로 물방울이 터지듯이 하나씩 정렬이 되어가는 정렬이다. 예를 들어 가장 큰 것을 가장 오른쪽으로 보내고, 그 다음 두번째로 큰 것을 오른쪽에서 두번째로 보내는 방식으로 반복되는 정렬이다. 아래 그림을 통해 예시로 설명한다.

위 이미지는 초기 값으로 3,2,1,5,4가 정렬된 배열을 버블 정렬로 정렬하는 과정을 보여주는 그림이다. 왼쪽 그림은 좌측에 가장 큰 값을 가장 오른쪽으로 옮기는 경우, 오른쪽의 그림은 두번째로 큰 값을 오른쪽에서 두번째로 옮기는 경우를 보여준다.

인접한 칸을 대소비교하고, 결과에 따라 자리를 바꿔주는 연산을 계속 반복한다. 가장 큰 값을 오른쪽으로 보내줄 때 탐색에 필요한 연산 횟수는 4회, 두번째 작은 값을 오른쪽으로 보내줄 때 탐색에 필요한 연산 횟수는 3회이다. 이를 바탕으로 N개의 값의 정렬에 필요한 탐색 횟수는 O(N^2)으로 표현할 수 있다(이미 정렬된 상태라도 O(N^2)이 필요하다)

버블 정렬에는 값을 바꿔주는 연산도 필요하다. 최악의 경우 모두 값을 바꿔주어야 한다. 5,4,3,2,1로 정렬된 함수의 경우 5를 제일 오른쪽으로 보내는데 값을 바꿔주는 연산은 총 8회가 필요하다. 그 후, 4를 오른쪽에서 두번째로 보내주는데 필요한 연산은 6회가 필요하다. 따라서, 최악의 경우 값을 바꿔주는 연산에 O((2N)^2)의 연산이 필요하다.

이런 이유로 버블 정렬의 시간 복잡도는 Best와 Worst 경우 모두 O(N^2)이 필요한 것으로 이해할 수 있다.

 

선택 정렬

---

선택 정렬은 우선순위가 낮은 값을 선택해서 왼쪽으로 이동시켜주면서 정렬을 하나씩 해나가는 방법이다. 자세한 내용은 아래 그림을 보면 쉽게 이해가 가능하다.

위 그림처럼 3,4,2,5,1의 초기값이 주어진 배열이 있다고 가정하자. 이 때, 전체를 탐색해서 가장 우선순위가 낮은 값을 확인한다. 그리고 그 값을 가장 왼쪽으로 보내준다. 이제 가장 왼쪽 영역까지가 정렬이 완료된 영역이다. 가장 왼쪽에서 두번째 영역부터 여기에 올 값을 탐색해준다. 확인해보니 2가 올 수 있는 것이 확인되어, 위치를 바꿔준다. 이제 왼쪽에서 두번째 영역까지 정렬이 완료된 것으로 이해할 수 있다. 이를 계속해서 반복하면 정렬이 완료되게 된다. 

선택정렬은 보다시피 탐색을 하는데 첫번째는 5회, 두번째는 4회, 세번째는 3회가 필요하다. 이로 유추해보면, 선택정렬에 필요한 연산은 O(N^2)이 된다. 이는 최악이든, 최선의 경우든 동일하다. 왜냐하면 지금 1이라는 값이 나왔다고 하더라도, 컴퓨터는 뒷쪽에 1보다 작은 숫자가 있는지 없는지 확신할 수 없기 때문에 끝까지 탐색을 해야되기 때문이다.

반면 선택정렬은 교환하는데 필요한 연산은 각 정렬 당 1회임을 확인할 수 있다. 즉, 값을 바꾸는데 필요한 시간복잡도는 총 O(N)으로 정의할 수 있다. 따라서, 선택정렬의 시간복잡도는 BEST와 WORST 모두 O(N^2)이 됨을 알 수 있다.

연산 횟수가 버블 정렬이 3배 정도 많기 때문에 선택 정렬이 좀 더 빠를 것이라고 예상을 한다고 한다. 최선의 경우(모두 정렬이 된 경우), 값의 이동이 둘다 없기 때문에 사실상 성능은 거의 동일하다고 한다. 

 

삽입 정렬

---

삽입 정렬은 정렬된 영역을 조금씩 넓혀가며, 그 정렬된 영역에 값을 하나씩 넣고 제자리를 찾아가게 하는 방식으로 정렬이 진행한다. 마찬가지로 아래 그림을 참고하자.

가장 먼저 왼쪽 영역을 하나 선택해서 정렬한다. 이 때 원소는 자기 밖에 없기 때문에 정렬할 것이 없으므로 정렬이 완료되었고 파란색으로 처리한다. 두번째에 저장된 값 4를 정렬 영역에 넣어서 자기 자리를 찾아가게 한다. 이 때, 3과 4는 정렬된 순서이기 때문에 자리를 바꿀 필요가 없다. 두번째 인덱스까지 정렬이 완료되었다.

세번째 영역에 저장된 2를 정렬된 영역에 넣는다고 가정하자. 이 때, 2는 4보다 작은 것을 확인했으므로 2의 자리에 4를 넣어주고, 2가 저장될 위치를 업데이트 해준다. 2와 3을 비교해보니 2가 더 작은 것이 확인되었으므로 3을 2의 자리에 옮겨주고 2의 자리를 업데이트 해준다. 더 비교할 것이 없으므로 2를 저장해준다. 이제 세번째 영역까지 정렬이 완료되었다. 위처럼 정렬된 영역에 값을 하나씩 넣어보며 자기 자리를 찾아가게 하는 것을 삽입 정렬이라고 한다.

삽입 정렬의 탐색의 시간복잡도를 계산해보자. 첫번째 영역은 1번 탐색이 이루어졌다. 두번째 영역은 최악의 경우 2번 탐색이 이루어질 것이다. 세번째 영역은 최악의 경우 3번의 탐색이 이루어질 것이다. 이로 유추해보면 탐색의 시간복잡도는 O(N^2)이 필요하다.

데이터 교환 연산의 시간복잡도도 계산해보자. 첫번째 영역은 0번이다. 두번째 영역은 최악의 경우 1회가 필요하다. 세번째 영역은 최악의 경우 2회가 필요하다. 이 때 말하는 최악의 경우는 삽입하려는 수의 적절한 위치가 가장 왼쪽인 경우다. 이로 유추하면 최악의 경우 교환 연산은 총 O(N^2)의 시간복잡도가 필요하다.

이에 따라 삽입 정렬은 최악의 경우 O(N^2)의 시간복잡도를 보인다. 그렇지만 최선의 경우에는 시간복잡도가 상당히 좋아질 수 있다. 예를 들어 1,2,3,4,5처럼 정렬된 경우가 최선이 될 수 있다. 2는 1과 한번 비교, 3은 2와 한번 비교, 4는 3과 한번 비교를 하는 방식으로 정렬 연산이 끝날 수 있다. 즉, 최선의 경우 삽입 정렬은 O(N)의 시간복잡도를 보여준다.

 

병합 정렬

---

병합 정렬은 분할정복 방식이 적용된 정렬 알고리즘이다. 쉽게 말하면 각 원소를 더 이상 나눌 수 없을 정도로 쪼갠 후, 각각 정렬하면서 합치는 것을 반복하는 방식이다. 앞에서 보여주었던 O(N^2) 방식에 비하면 훨씬 개선된 시간복잡도를 보여준다.

병합 정렬은 위 이미지로 확인할 수 있다. 3,4,2,5,7,8,6,1를 쪼갤 수 있는 단위까지 쪼갠다. 즉, 원소가 하나가 있을 때까지 쪼갠 후, 그 때부터 재귀적으로 정렬하면서 결합하는 방식으로 접근한다. 예를 들어 3,4와 2,5를 병합할 때 각 순번을 비교해서 2,3,4,5 순으로 정렬하고, 다시 한번 재귀해서 최종꼴을 나타낸다.

병합 정렬의 비교 연산에 필요한 시간 복잡도를 계산해본다. 먼저, 3,4,2,5,8,8,1,6을 3,4 / 2,5 / 7,8 / 1,6로 만드는데 필요한 비교 횟수는 총 8회임을 알 수 있다. 34 / 25 / 78 / 16을 2345/ 1678로 만드는데 필요한 비교 횟수는 총 8회임을 알 수 있다. 각 층마다 비교 연산이 총 N번 발생하는 것을 확인할 수 있다. 그리고 층은 logn으로 표현이 가능하다. 따라서, 병합 정렬 비교의 시간복잡도는 O(nlogn)으로 표현할 수 있다.

병합 정렬의 자리 배치 연산에 필요한 시간 복잡도를 계산해본다. 병합 정렬은 임시 배열을 하나 선언한 후, 그곳에 데이터를 정렬해서 담고 그 배열을 반환하는 형태로 배치 연산이 진행된다. 각 층마다 임시 배열을 채우는데 필요한 연산은 n번이며, 이를 반환하는데는 배열의 길이만큼 필요하기 때문에 마찬가지로 n번이 필요하다. 즉, 2n번씩 logn번 연산이 필요하기 때문에 시간복잡도는 O(NlogN)이 되는 것을 알 수 있다.

병합 정렬은 어떤 경우에도 비교는 필요하기 때문에 BEST와 WORST 모두 시간 복잡도는 O(NlogN)으로 표현할 수 있으며, 정렬된 배열을 담은 별도의 배열 선언이 필요하기 때문에 메모리가 좀 더 많이 필요하다.

 

퀵 정렬

---

개인적으로 퀵 정렬은 사람보다는 컴퓨터처럼 생각하는 정렬 알고리즘이 아닌가 싶다. 정렬의 기준이 되는 Pivot을 설정하고, Low와 High를 Two Pointer로 선언해서 Low는 Pivot보다 높은 곳의 좌표를 찾고, High는 Pivot보다 낮은 곳의 좌표를 찾아서 Low와 High에 저장된 값을 반복해서 바꿔준다. 그리고 Low가 High보다 더 큰 좌표를 가질 때, 반복문을 종료하고 High와 Pivot을 바꿔주는 것을 재귀적으로 수행한다. 아래 그림으로 이해를 해보자.

먼저 3을 Pivot로 잡고, Pivot보다 바로 우측 한칸 좌표를 Low, 그리고 현재 정렬 구간의 마지막을 High로 잡는다. Low는 Pivot보다 큰 값이 나올 때까지 탐색을 계속하고, High는 Pivot보다 작은 값이 나올 때까지 탐색을 한다. 위의 경우 Low는 4를 가리키고 High는 1을 가리킨다. 이 때 교환을 해준다.

교환을 한 후, 다시 한번 High와 Low는 반복해서 탐색을 한다. 탐색을 하다가 Low > High가 되는 시점에서 반복문을 종료하고 High가 가리키는 시점에서 Pivot과 값을 교환해준다. Pivot과 High의 값을 교환해주는 이유는 High가 Pivot보다 작은 값을 가리키고 있기 때문이다. 이렇게 된다면 Pivot은 제 위치를 찾아갔다고 이해할 수 있다.

그 후에는 재귀적으로 Pivot 되지 않은 영역을 재귀적으로 퀵 정렬을 해주어야 한다. 즉, 24 구간과 57861구간에서 다시 한번 Pivot과 Low, High를 설정하고 각각 정렬을 해주어야 한다. 이 때부터는 병합정렬과 동일하게 구간 별로 분할 정복을 한다.

퀵 정렬의 시간복잡도는 Pivot이 생성되는 횟수 * 원소 갯수로 구할 수 있다. 이런 이유 때문에 적절한 Pivot을 잘 고르는 것이 퀵 정렬의 성능에 중요한 역할을 한다.  최악의 경우는 아래 상황을 볼 수 있다.

이미 정렬된 상황에서 Pivot을 항상 제일 작은 수를 가지게 될 경우, 공간이 2등분이 되지 않고 원소의 갯수만큼 Pivot을 해야한다. 따라서 이 때의 시간 복잡도는 O(N^2)이 된다. 개선을 위해서는 일반적으로 중간에 가까운 값을 Pivot으로 선택하는 방법이 많이 선택된다고 한다. 주로 세 개의 값을 뽑아서, 그 값 중 중간값을 Pivot으로 삼아 정렬을 한다는 것이다. 

퀵 정렬은 최악의 경우는 O(N^2)의 시간 복잡도를 보여주나, Pivot의 값을 잘 선택하는 기술이 많이 나와있으며, 병합정렬과는 다르게 값의 이동에 여분의 메모리가 필요하지 않기 때문에 좋은 성능을 보여준다고 한다. 

 

힙 정렬

---

힙 정렬은 힙 자료구조를 활용해서 정렬하는 방식이다. 배열로 힙을 만들고, 힙에서 자료를 하나씩 빼서 기록하는 것만으로 정렬이 완료된다. 배열을 힙으로 만드는데 O(NlogN)이 필요하며, 힙에서 자료를 빼오는데 O(NlogN)이 필요하기 때문에 시간복잡도는 BEST, WROST 모두 O(NlogN)으로 볼 수 있다. 자세한 설명은 아래의 포스팅을 참고하면 된다.

Heap 구조 및 파이썬 구현

Heap 구조 및 파이썬 구현

 

정렬 알고리즘에 따른 시간 복잡도 요약

---

알고리즘	BEST	WORST	메모리	비고
버블 정렬	O(N^2)	O(N^2)	↓	탐색 최소 N^2
선택 정렬	O(N^2)	O(N^2)	↓	탐색 최소 N^2
삽입 정렬	O(N)	O(N^2)	↓	정렬 시, 탐색 최소 N
병합 정렬	O(NlogN)	O(NlogN)	↑	-
퀵 정렬	O(NlogN)	O(N^2)	↓	최악 : 정렬된 배열에서 최소값을 Pivot로 계속 선택할 시
힙 정렬	O(NlogN)	O(NlogN)	↑	-

개인적으로 정렬 알고리즘을 다시 한번 공부하면서 본 경우를 하나의 표로 요약 정리했다. 비전공자가 공부하면서 남긴 기록이기 때문에 부정확할 수 있다. (부족한 부분은 조언 해주시면 수정 정리해두겠습니다.)