- 전체 글 (350)
- Today
- Total
Priv's Blog
14. 정렬 알고리즘 본문
1. 정렬이란?
데이터의 집합을 일정한 순서로 바꿔 늘어놓는 작업.
정렬된 데이터 집합의 순서에 따라 오름차순 정렬과 내림차순 정렬로 구분된다.
정렬 알고리즘의 핵심은 교환, 선택, 삽입이다.
대부분의 정렬 알고리즘들이 이 3가지 핵심 요소들을 다양한 방법으로 응용하고 있다.
2. 안정적인 정렬 알고리즘 (Stable Sorting Algorithm)
정렬되기 전 데이터 집합에서 값이 동일한 데이터가 2개 이상일 때, 정렬을 수행한 이후에도 정렬 이전의 순서가 유지되는 알고리즘을 안정적인 정렬 알고리즘이라고 부른다.
안정적이지 않은 정렬 알고리즘도 존재한다.
이는 정렬을 수행한 이후에도 정렬 이전의 순서가 유지될 것이라는 보장이 없는 알고리즘이다.
3. 내부 정렬과 외부 정렬
뒤섞인 카드가 30장이 있고, 책상에 카드를 펼쳐두고 정렬을 수행하고자 한다.
책상 1개로도 충분히 카드를 모두 펼쳐둘 수 있기 때문에, 추가적인 공간 마련이 불필요하다.
이는 내부 정렬의 예시이다.
뒤섞인 카드가 9000000장이 있고, 책상에 카드를 펼쳐두고 정렬을 수행하고자 한다.
하지만 책상 1개로는 9000000장의 카드들을 모두 펼쳐둘 수가 없다.
여분의 다른 책상(그리고 더 큰 책상)을 가져와야 하는 준비가 필요해졌다.
이는 외부 정렬의 예시이다.
3.1) 내부 정렬 (Internal Sorting)
정렬할 모든 데이터를 1개의 배열에 저장해 수행할 수 있는 경우에 사용하는 알고리즘을 내부 정렬이라고 부른다.
3.2) 외부 정렬 (External Sorting)
정렬해야 하는 데이터의 양이 너무 많아서 1개의 배열에 저장할 수 없는 경우에 사용하는 알고리즘을 외부 정렬이라고 부른다.
4. 버블 정렬 (Bubble Sort)
이웃한 원소 2개의 대소 관계를 비교하여 필요할 경우 교환을 반복한다.
단순 교환 정렬이라고도 부르며, 안정적인 정렬 알고리즘이다.
4.1) 정렬 과정
- 우측 끝에 있는 원소 2개, 9와 8을 주목하면서 시작한다.
- 두 값의 대소 관계를 비교한다.
- 배열을 오름차순으로 정렬할 것이므로, 교환이 필요하다.
- 두 값을 교환한다.
- 왼쪽으로 1칸 이동한다.
2) ~ 5) 과정을 n-1번 반복한다.
이때 n은 배열의 길이다.
전체 원소 비교 횟수는 (n - 1) + (n - 2) + (n - 3) + ~ + 1 = n * (n - 2) / 2
4.2) 패스 (Pass)
위 사진을 보면 원소 수가 n개인 배열에서, n-2번 비교/교환을 수행하여 가장 작은 값인 3이 맨 앞으로 정렬되었다.
이처럼 일련의 비교, 교환하는 과정을 패스라고 부른다.
패스를 1번 수행할 때마다 정렬하는 대상이 1개씩 감소한다.
1번째 패스의 비교 횟수: (n-1)번
2번째 패스의 비교 횟수: (n-2)번
모든 정렬을 마치기 위해서는 패스를 (n-1)번 수행해야 한다.
패스를 k번 수행하면, 맨 앞부터 k개 원소가 정렬된다.
4.3) 버블 정렬 구현
### Lab8_BubbleSort.py ###
from typing import MutableSequence, Any
class Bubble :
def Bubble(lst: MutableSequence) -> None :
""" Original Ver. """
n = len(lst)
for i in range(0, n-1) : ## Pass (0 ~ n-1)
for j in range(n-1, i, -1) : ## 뒤에서 앞으로
if (lst[j] < lst[j-1]) : ## SWAP
lst[j], lst[j-1] = lst[j-1], lst[j]
먼저 for문을 사용해 패스부터 구현한다.
패스는 1번 진행될 때마다 길이가 1씩 줄어든다.
패스가 시작되면 배열 요소들을 뒤에서부터 앞으로 이동하며 1쌍을 주목해 대소 관계를 비교한다.
뒤에서부터 앞으로 이동해야 하므로, for문이 패스 안에 추가돼야 하며, 앞으로 이동할 때마다 if문으로 대소 관계를 비교해야 한다.
주목한 원소가 lst[j]이면, 비교돼야 하는 2번째 원소는 lst[j-1]이 된다.
두 원소 lst[j-1]과 lst[j]의 값을 비교한 뒤, lst[j-1]이 lst[j]보다 크면 SWAP.
4.4) 개선된 버블 정렬 1
위 사진을 통해 버블 정렬이 수행되는 과정을 다시 살펴보면, 3번 패스까지는 교환이 이루어졌지만, 4번 패스부터는 정령이 이미 완료되어 비교만 이루어질 뿐, 교환은 이루어지지 않는다는 것을 알 수 있다.
이는 즉, 패스가 끝날 때까지 교환이 1번도 발생하지 않았다면, 이미 정렬이 완료되었다는 것을 의미한다.
4.5) 개선된 버블 정렬 1 구현
### Lab8_BubbleSort.py ###
from typing import MutableSequence, Any
class Bubble :
def Bubble1(lst: MutableSequence) -> None :
""" Exhanded Ver.1 """
n = len(lst)
for i in range(0, n-1) : ## Pass (0 ~ n-1)
exchangeCounter = 0
for j in range(n-1, i, -1) : ## 뒤에서 앞으로
if (lst[j] < lst[j-1]) :
lst[j], lst[j-1] = lst[j-1], lst[j] ## SWAP
exchangeCounter += 1 ## SWAP 발생; 카운트 += 1
if (exchangeCounter == 0) : ## SWAP이 1번도 발생하지 않으면,
break교환이 발생한 횟수를 기록하는 정수형 변수, exchangeCounter를 추가한다.
패스를 시작할 때, exchangeCounter는 0으로 초기화된다.
패스 진행 도중, 원소 교환이 이루어지면 값이 1 증가한다.
패스를 끝났을 때, 원소 교환 횟수가 0인지(교환이 1번도 발생하지 않았는지)를 검사한다.
만약 0일 경우, 정렬이 끝난 것이므로, 프로그램 실행을 종료한다.
4.6) 개선된 버블 정렬 2
이미 정렬된 원소를 제외한 나머지 원소들만 비교/교환하도록 스캔 범위를 제한한다.
교환이 일어나지 않고 비교만 이루어졌다는 것은 이미 정렬이 끝났다는 것을 의미한다.
교환이 일어났던 마지막 지점을 기억해두고, 다음 패스부터는 n-1부터 기억해둔 마지막 지점까지만 교환을 진행하면 불필요한 비교 과정을 생략할 수 있다.
4.7) 개선된 버블 정렬 2 구현
### Lab8_BubbleSort.py ###
from typing import MutableSequence, Any
class Bubble :
def Bubble1(lst: MutableSequence) -> None :
""" Exhanded Ver.1 """
n = len(lst)
checkPoint = 0
while (checkPoint < n-1) : ## PASS
last = n - 1
for j in range(n-1, checkPoint, -1) : ## (n-1 ~ checkPoint)
if (lst[j-1] > a[j]) :
lst[j-1], lst[j] = lst[j], lst[j-1] ## SWAP
last = j ## last SWAP index Updating
checkPoint = last ## CheckPoint Update; Next PASS's END PointcheckPoint 변수는 패스가 끝나고 최종적으로 결정된 마지막 교환 발생 지점을 저장한다.
last 변수는 n-1부터 시작해서 SWAP이 진행될 때마다, 해당 지점을 저장한다.
SWAP이 발생할 때마다 last 변수가 업데이트되며, 패스가 끝날 때마다 최종적으로 업데이트가 끝난 last 변수 값이 checkPoint 변수에 삽입된다.
다음 패스가 시작되면 n-1부터 checkPoint까지만 교환/비교 연산을 수행하면 된다.
5. 셰이커 정렬 (Shaker Sort)
칵테일 정렬(Cocktail Sort) 또는 칵테일 셰이커 정렬(Cocktail Shaker Sort)이라고도 부른다.
양방향으로 전개되는 버블 정렬이다.
홀수 패스에서는 뒤에서 앞으로, 짝수 패스에서는 앞에서 뒤로 움직이며 버블 정렬을 전개한다.
5.1) 셰이커 정렬 구현
### Shaker Sort ###
from typing import MutableSequence, Any
class ShakerSort :
def Shaker(lst: MutableSequence) -> None :
""" Shaker Sort """
left = 0
right = len(lst) - 1
last = right
while(left < right) :
for i in range(right, left, -1) : ## right -> left; PASS
if (lst[i-1] > lst[i]) :
lst[i], lst[i-1] = lst[i-1], lst[i] ## SWAP
last = i ## End Point Update
left = last ## Next PASS(left -> right) Start Point
for j in range(left, right, 1) : ## left -> right; PASS
if (lst[j] > lst[j+1]) :
lst[j], lst[j+1] = lst[j+1], lst[j] ## SWAP
last = j ## End Point Update
right = last ## Next PASS(right -> left) Start Point홀수 패스에서는 기존 버블 정렬과 동일하게 가장 작은 원소를 맨 앞으로 이동시킨다.
짝수 패스에서는 앞에서부터 뒤로 이동하면서 가장 큰 원소를 맨 뒤로 이동시킨다.
이때, 각 패스가 끝날 때마다 이미 정렬된 부분(맨 앞과 맨 뒤)은 비교/정렬할 필요가 없다.
개선된 버블 정렬 2에서 구현했던 것처럼 SWAP이 이루어질 때마다 last 변수에 값을 업데이트하도록 만들어 다음 패스의 비교/정렬 횟수를 1씩 줄여준다.
6. 단순 선택 정렬 (Straight Selection Sorting)
가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하여 정렬하는 알고리즘이다.
원소 교환이 이루어질 때마다 최솟값을 선정하는 작업이 필요하며, 현재 주목한 맨 앞 원소와 최솟값 원소를 교환한다.
이는 즉, 서로 떨어진 자리에 있는 두 원소를 교환하는 것을 의미하므로, 안정적이지 않은 정렬 알고리즘에 해당한다.
최솟값 선택 후 맨 앞 원소와의 교환 과정을 (n-1)번 반복하면 전체 정렬이 완료된다.
여기서 n은 배열의 길이이다.
6.1) 단순 선택 정렬 구현
### StraightSelectionSort ###
from typing import MutableSequence, Any
class SelectionSort :
def Selection(lst: MutableSequence) -> None :
""" Selection Sort """
n = len(lst)
for i in range(0, n-1, 1) :
min = i
for j in range(i+1, n, 1) :
if(a[j] < a[min]) :
min = j ## minimum index Update
a[min], a[j] = a[j], a[min] ## SWAP최솟값을 저장하기 위해 min 변수를 둔다.
for문을 이용해 배열 전체를 탐색하면서 min 변수의 값을 업데이트하여 최솟값을 찾는다.
최솟값과 현재 주목한 노드를 교환한다.
7. 단순 삽입 정렬 (Straight Insertion Sorting)
주목한 원소보다 더 앞쪽에 있는 원소들과 비교하여 알맞은 위치로 이동시키는 알고리즘.
아직 정렬되지 않은 부분의 맨 앞 원소를 주목하고, 그 앞의 원소들은 이미 정렬이 완료된 원소들이라고 가정한다.
현재 주목한 원소와 이미 정렬이 완료된 원소들(가정)을 비교해 올바른 위치를 탐색한다.
배열의 길이가 길어질수록, 비교해야 하는 원소의 수가 늘어난다.
정렬된 부분의 알맞은 위치에 삽입하는 과정을 (n-1)번 반복한다. (시간 복잡도: O(n^2))
7.1) '알맞은 위치'에 삽입하기
배열에서 주목한 원소를 어떻게 해야 알맞은 위치에 삽입할 수 있을까?
'알맞은 위치'가 나타날 때까지 원소들을 한 칸씩 밀면 된다.
위 사진은 원소 3에 주목하여 알맞은 위치에 삽입하는 과정이다.
주목한 원소(3)보다 그 앞의 원소(7)이 더 크다.
주목한 원소(3)를 다른 변수에 백업한 뒤, 주목한 원소(3)이 있던 자리에 그 앞의 원소(7)을 복사해 넣는다.
이제 주목한 원소를 앞으로 한 칸 옮겨서 6에 주목한다.
주목한 원소(6)과 백업한 원소(3)과 비교한다.
주목한 원소(6)이 더 크므로, 기존에 7이 있었던 자리로 복사해 넣는다.
이제 주목한 원소를 앞으로 한 칸 옮겨서 4에 주목한다.
주목한 원소(4)와 백업한 원소(3)을 비교한다.
주목한 원소(4)가 더 크므로, 기존에 6이 있던 자리로 복사해 넣는다.
이제 주목한 원소를 앞으로 한 칸 옮겨서 1에 주목한다.
주목한 원소(1)과 백업한 원소(3)을 비교한다.
백업한 원소(3)이 주목한 원소(1)보다 더 크므로, 백업한 원소(3)을 주목한 원소(1) 바로 뒤에 넣는다.
그렇게 되면 바로 앞 단계에서 원소 4가 있던 자리에 백업한 원소(3)가 삽입된다.
즉, 원소 3개(4, 6, 7)을 뒤로 한 칸씩 밀어낸 뒤, 원소 3이 들어가야 할 알맞은 위치를 찾아낸 것이다.
7.2) 단순 삽입 정렬 구현
### Lab8_InsertionSort.py ###
from typing import MutableSequence, Any
class InsertionSort :
def Insertion(lst: MutableSequence) -> None :
""" Insertion Sort """
n = len(lst)
for i in range(1, n) :
j = i
tmp = lst[i]
while (j > 0) and (lst[j-1] > tmp) :
lst[j] = lst[j-1]
j -= 1
lst[j] = tmp알고리즘을 시작할 때, 인덱스 값이 1부터 시작한다.
이는 첫 번째 값, 0번 인덱스 원소는 이미 정렬이 마친 상태라고 가정한 뒤에 시작하기 때문이다.
주목하는 원소의 인덱스 값을 변수 j를 통해 표현하며, 주목한 원소의 앞 원소와 비교하는 과정을 거친다.
변수 tmp는 주목하는 원소를 백업한다.
배열 1개로 동작하는 내부 정렬 알고리즘이기 때문에, '알맞은 위치'를 찾는 과정에서 주목한 원소의 값이 배열 상에서 덮어써진다.
데이터 유실을 막기 위해서는 백업이 필수다.
주목한 원소의 앞 원소(lst[j-1])과 백업해둔 주목한 원소(tmp)의 대소 관계를 비교하여 앞 원소가 더 크면 위치를 뒤로 한 칸 당긴다.
그런 다음 비교할 앞 원소를 앞으로 이동시킨다. (j -= 1)
이때, (lst[j-1] < tmp) 관계가 성립되면, 백업해둔 주목한 원소(tmp)가 그 앞의 원소들보다 크다는 의미이므로, 해당 위치(j)에 백업해둔 주목한 원소(tmp)를 삽입한다.
7.3) 단순 삽입 정렬의 문제점
위의 사진과 같이 [1, 2, 3, 4, 5, 0, 6] 배열을 단순 삽입 정렬 알고리즘을 통해 정렬한다고 가정한다.
앞에서 언급된 다른 배열과는 달리, 0을 제외한 나머지 6개의 원소들은 이미 정렬이 완료되어 있는, 거의 정렬이 끝나 있는 상태의 배열이다.
그 덕분에 원소의 이동을 통한 '알맞은 위치' 찾기 작업은 1번만 수행되면 된다.
하지만 문제는 원소 0이 들어가야 하는 '알맞은 위치'를 만들기 위해, 원소 이동이 6번이나 필요하다는 것이다.
이는 이진 삽입 정렬로 최적화는 가능하겠지만, 이 방법 또한 원소 이동 자체는 필요하다.
단순 삽입 정렬의 특징은 다음과 같다.
- 장점: 이미 정렬을 마쳤거나, 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다.
- 단점: 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 늘어난다.
8. 이진 삽입 정렬 (Binary Insertion Sorting)
단순 삽입 정렬은 배열의 원소 수가 많아지면, 삽입에 필요한 비교/교환 비용도 커진다.
이진 검색을 활용하면 이 비용을 절약할 수 있다.
8.1) 이진 삽입 정렬 구현
### Binary Insertion Sort ###
from typing import MutableSequence
class InsertionSort :
def BinaryInsertion(lst: MutableSequence) -> None :
""" Binary Insertion Sort """
n = len(lst)
for i in range(1, n) :
key = lst[i] ## Attention num
pl = 0 ## Left Pointer
pr = i - 1 ## Right Pointer
while True :
pc = (pl + pr) // 2 ## Centor; Pivot
if (lst[pc] == key) : ## Found; Search END
break
elif (lst[pc] > key) : ## Move Right
pl = pc + 1
elif (lst[pc] < key) : ## Move Left
pr = pc - 1
if (pl > pr) : ## Search END
break
pd = (pc + 1) if (pl <= pr) else (pr + 1) ## Input Position SET
for j in range(i, pd, -1) : ## Make the 'Currect Pos'
lst[j] = lst[j-1] ## lst[i] ~ lst[pd] -> Move right(1 step)
lst[pd] = key ## Input num백업해둔 주목한 원소와 그 앞의 원소들을 하나씩 비교하며 '알맞은 위치'를 찾기 위해 위치를 뒤로 밀었던 것과 달리, 이진 검색을 통해 '알맞은 위치'를 먼저 찾아내고, 그 뒤의 원소들을 한꺼번에 뒤로 밀어버린다.
한 번에 한 번씩 if문을 꼬박꼬박 거쳐야 했던 단순 삽입 정렬 방식보다 훨씬 빠른 속도를 기대할 수 있다.
9. 셸 정렬 (Shell Sort)
셸 정렬은 단순 삽입 정렬의 장점을 유지한 채, 단점을 보완하여 속도를 최적화한 알고리즘이다.
먼저 정렬할 배열의 원소들을 일정 크기의 그룹으로 나눠서 각 그룹별로 정렬을 수행한다.
이후 정렬을 마친 각 그룹들을 다시 합치는 작업을 재귀적으로 반복하여 원소 이동 횟수를 감소시킨다.
퀵 정렬이 등장하기 전까지는 가장 빠른 정렬 알고리즘이라고 알려져 있었다.
9.1) h-정렬
셸 정렬은 여러 개의 h-정렬들의 모음으로 구성된다.
먼저 서로 h칸 떨어져 있는 원소들을 그룹으로 묶은 뒤, 그룹별로 각각 단순 삽입 정렬을 수행한다.
그룹이 나눠지면 전채 배열의 길이보다 훨씬 길이가 짧아지기 때문에, 불필요한 원소 이동 횟수를 크게 줄일 수 있다.
떨어져 있는 칸의 수(h)의 크기는 h-정렬이 1번 완료될 때마다 일정 간격으로 줄여 나간다.
(Ex. 4-정렬, 2-정렬, 1-정렬 순으로 진행)
마지막 1-정렬은 전체 배열을 기준으로 수행되므로, 단순 삽입 정렬과 방식은 동일하다.
하지만 그룹 별로 이미 일정 수준 이상 정렬을 수행했기 때문에, 원소 이동 및 삽입 횟수가 크게 줄어든다.
위 사진처럼 8개의 원소가 저장된 배열에서 h-정렬을 수행하면, 총 7번의 정렬을 수행하게 된다.
이처럼 단순 삽입 정렬보다 정렬 횟수는 늘어나지만, 이동 횟수가 줄어드는 것을 알 수 있다.
9.2) 셸 정렬 구현
### Lab8_ShellSort.py ###
from typing import MutableSequence, Any
class ShellSort :
def Shell(lst: MutableSequence) -> None :
""" Shell Sort """
n = len(lst)
h = (n // 2)
while (h > 0) :
for i in range(h, n) :
j = (i - h)
tmp = lst[i]
## Selection Sort ##
while (j >= 0) and (a[j] > tmp) :
lst[j + h] = lst[j]
j -= h
lst[j + h] = tmp
## END Selection Sort END ##
h //= 2h의 초기값은 n//2이다.
만약 n이 8이면, 4부터 시작해서 2, 1 순으로 바뀐다.
h의 크기에 따라 그룹이 묶이는데, 정렬 자체가 단순 삽입 정렬이기 때문에 일종의 스탭(step)이라고 보면 된다.
(단순 삽입 정렬은 스탭이 1인 정렬, h정렬은 스탭이 h인 정렬)
h만큼 떨어진 원소들만 가지고 단순 삽입 정렬을 수행한다.
h만큼 떨어진 원소들을 사용하므로, '알맞은 위치'를 찾는 과정에서도 h만큼 인덱스에 값을 빼줘야 한다.
(단순 삽입 정렬은 1만 빼줌)
'h만큼'의 요소를 제외한다면, 정렬 자체는 단순 삽입 정렬과 크게 다르지 않다.
9.3) 개선된 셸 정렬
원소 수가 8이라면, h 값은 4 → 2 → 1 순으로 변화한다.
이때, 4개의 그룹을 2개의 그룹으로 합치게 되면 다음 그림과 같이 바뀌게 된다.
그룹으로 원소를 나눠서 정렬했지만, 제대로 원소들이 섞이지 않아서 충분한 정렬이 이루어지지 않았음을 알 수 있다.
이를 해결하기 위해서는 h의 값이 서로 배수가 아니어야 한다.
최적의 h 값을 찾기 위한 방법을 수식으로 표현하면 다음과 같다.
h의 초깃값은 너무 크면 효과가 없기 때문에 여기서는 n // 9를 넘지 않는 큰 수에서 시작하도록 설정한다.
9.4) 개선된 셸 정렬 구현
### Lab8_ShellSort.py ###
from typing import MutableSequence, Any
class ShellSort :
def Shell(lst: MutableSequence) -> None :
""" Shell Sort """
n = len(lst)
h = 1
while (h < n // 9) :
h = (3 * h) + 1
while (h > 0) :
for i in range(h, n) :
j = (i - h)
tmp = lst[i]
## Selection Sort ##
while (j >= 0) and (a[j] > tmp) :
lst[j + h] = lst[j]
j -= h
lst[j + h] = tmp
## END Selection Sort END ##
h //= 3기존의 셸 정렬과 크게 달라지지 않았다.
h𝑖 =3h𝑖−1 + 1, h1 = 1 수열을 사용하여 n // 9를 넘지 않는 h 값을 계산하도록 만들었다.
또한 정렬을 마친 후, h 값을 2가 아닌 3으로 나눠주도록 바꿔주었다.
10. 병합 정렬 (Merge Sort)
배열을 앞부분과 뒷부분의 두 그룹으로 나눠서 각각 정렬한 후, 병합하는 작업을 반복하는 정렬 알고리즘이다.
각 배열에서 주목하는 원소의 값을 비교해서 작은 쪽의 원소를 꺼내 새로운 배열에 저장한다.
배열이 완료되면 새로운 배열 1개가 추가된다.
(총 3개의 배열이 필요)
10.1) 정렬을 마친 배열 2개 병합하기
### Lab8_Merge.py ###
from typing import MutableSequence, Sequence
class Merge :
def SortedListMerge(a: Sequence, b: Sequence, c: Sequence) -> None :
""" Sorted List Merge """
pa, pb, pc = 0, 0, 0 ## Pointer of a, b, c
na, nb, nc = len(a), len(b), len(c) ## len of a, b, c
while (pa < na) and (pb < nb) :
if (a[pa] <= b[pb]) :
c[pc] = a[pa]
pa += 1
else :
c[pc] = b[pb]
pb += 1
pc += 1
while (pa < na) :
c[pc] = a[pa]
pa += 1
pc += 1
while (pb < nb) :
c[pc] = b[pb]
pb += 1
pc += 1배열 a와 배열 b를 병합하여 새로운 배열 c를 완성하는 코드이다.
정렬 자체는 수행하지 않지만, 이 로직이 병합 정렬 알고리즘의 근본이 된다.
10.2) 병합 정렬 알고리즘 구조
배열을 우선 앞, 뒤로 나눠서 정렬을 진행한다.
정렬이 완료된 배열 2개를 병합하여 새로운 배열을 만든다.
큰 문제를 최대한 작은 단위로 나눈 뒤, 단계별로 해결해 나가는 과정을 거치므로, 분할 정복법에 해당한다고 볼 수 있다.
배열의 원소 수가 2개 이상인 경우, 다음 3단계를 따라 진행된다.
- 배열의 앞부분을 병합 정렬로 정렬
- 배열의 뒷부분을 병합 정렬로 정렬
- 배열의 앞부분과 뒷부분을 병합
10.3) 병합 정렬 알고리즘 구현
### Lab8_Merge.py ###
from typing import MutableSequence, Sequence
class Merge :
def MergeSort(a: MutableSequence) -> None :
def _MergeSort(a: MutableSequence, left: int, right: int) -> None :
if (left < right) :
center = (left + right) // 2
_MergeSort(a, left, center)
_MergeSort(a, center + 1, right)
bP_l = bP_r = 0 ## buffer list pointers
aP = anP = left ## a list pointer(aP); new a list pointer(anP)
## Left ~ Center Add -> Buffer List ##
while (aP <= center) :
buff[bP_l] = a[aP] ## Buffer list += a[aP] ~ a[center]
bP_l += 1
aP += 1
## END Left ~ Center Add -> Buffer List END ##
while (aP <= right) and (bP_r < bP_l) :
''' init: (aP, bP_l == center); (bP_r == 0); '''
## Make a Sorted list a; (buffer -> a) ##
if (buff[bP_r] <= a[aP]) :
a[anP] = buffer[bP_r]
bP_r += 1
else :
a[anP] = a[aP]
aL += 1
## END Make a Sorted list a; (buffer -> a) END ##
anP += 1
## Add the remain numes ##
while (bP_r < bP_l) :
''' init: (bP_r <= aP); (bP_l == center); '''
a[anP] = buff[bP_r]
anP += 1
bP_r += 1
## END Add the remain numes END ##
n = len(a)
buff = [None] * n
_MergeSort(a, 0, n-1)
del buff
11. 힙 정렬 (Heap Sort)
힙(Heap)의 특성을 사용한 정렬 알고리즘이다.
힙은 '부모의 값이 자식의 값보다 항상 크다' 또는 '부모의 값이 자식의 값보다 항상 작다'는 조건을 만족하는 완전 이진트리이다.
부모와 자식의 관계는 일정하지만, 형제 노드 사이의 대소 관계는 상관하지 않는다.
즉, 힙은 부분 순서 트리라고 볼 수 있다.
힙 정렬 알고리즘을 사용하려면, 먼저 힙을 구현해야 한다.
이때 힙을 어떻게 구현하느냐에 따라 오름차순, 내림차순 변경이 가능하다.
'부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 힙의 루트는 항상 최댓값이 된다.
반대로 '부모의 값이 자식의 값보다 항상 작다'는 조건을 만족하는 힙의 루트는 항상 최솟값이 된다.
일반적인 힙 정렬은 '힙에서 최댓값은 루트에 위치한다'를 기준으로 구현하는 알고리즘이다.
배열의 원소들로 힙을 우선 구성한 다음, 힙의 루트를 빼낸 뒤, 힙 재정렬을 반복하면 정렬이 완료된다.
11.1) 힙과 배열 원소와의 대응
힙은 완전 이진트리이므로, 너비 우선 탐색 개념을 적용하면 다음과 같은 특성을 만족한다.
힙을 배열로 표현할 때 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드를 찾기 위해서는 수식을 적용해야 한다.
- 부모 노드: a[(i - 1) // 2]
- 왼쪽 자식 노드: a[(i * 2) + 1]
- 오른쪽 자식 노드: a[(i * 2) + 2]
11.2) 힙 정렬 알고리즘 동작 과정
힙 정렬 알고리즘의 로직은 2단계로 나눠진다.
- 힙에서 최댓값인 루트를 꺼낸다.
- 루트 이외의 부분을 힙으로 만든다.
1, 2단계 반복하면서 힙에서 꺼낸 값을 나열하면 정렬된 배열이 완성된다.
11.3) 루트를 삭제한 힙의 재구성 과정
힙의 루트 노드가 삭제되면, 남은 노드 중 최댓값이 루트 노드가 되도록 힙을 재구성해야 한다.
재구성 과정은 3단계로 나눠진다.
- 루트를 삭제한다.
- 말단 노드(마지막 노드)를 루트로 이동시킨다.
- 자식 노드 2개 중, 값이 더 큰 노드와 자리를 바꾼다.
11.4) 힙 정렬 알고리즘의 흐름
최댓값을 힙에서 뽑아내 배열에 추가하는 방식으로 정렬하기 때문에 맨 뒤에서부터 앞으로 이동하며 정렬을 수행해야 한다.
정렬이 완료된 원소(힙에서 뽑아낸 최댓값 원소)는 배열의 맨 뒤(n-1)에서부터 추가된다.
배열에 정렬이 완료된 값이 추가될 때마다 정렬되지 않은 배열(힙)의 마지막 인덱스 값(i)을 1씩 줄인다.
정렬되지 않은 배열(힙)의 마지막 인덱스 값(i)이 0이 될 때까지 최댓값을 뽑아내 배열에 추가하는 과정을 반복한다.
11.5) 배열을 힙으로 만들기
서브 트리 A는 힙이 아니다.
하지만 서브 트리 B와 C는 힙이다.
서브 트리 A의 루트인 노드 4를 적합한 위치에 배치하면, 서브 트리 A, B, C 모두 힙으로 만들 수 있다.
트리의 가장 아랫부분의 작은 서브 트리부터 상향식으로 힙을 만들어가면, 전체 배열을 힙으로 만들 수 있다.
11.6) 힙 정렬 알고리즘 구현
### Lab8_HeapSort.py ###
from typing import MutableSequence, Any
class HeapSort :
def Heap(a: MutableSequence) :
def DownHeap(a: MutableSequence, left: int, right: int) -> None :
temp = a[left] ## Root Node
parent = left
while (parent < (right + 1) // 2) : ## (right+1)//2 == 마지막 원소의 부모 노드
cl = parent * 2 + 1
cr = parent * 2 + 2
child = cr if (cr <= right) and (a[cr] > a[cl]) else cl ## 교환될 큰 자식 노드
if (temp >= a[child]) : ## 루트 노드가 최댓값이면
break
a[parent] = a[child] ## 노드 자리 변경
parent = child ## 인덱스 변경
a[parent] = temp ## 정렬 전의 루트 노드 값을 자식으로
n = len(a)
for i in range((n-1)//2, -1, -1) :
DownHeap(a, i, n-1) ## a[i] ~ a[n-1]을 힙으로
for j in range((n-1), 0, -1) :
a[0], a[j] = a[j], a[0]
DownHeap(a, 0, j-1) ## a[0] ~ a[j-1]을 힙으로
12. 퀵 정렬 (Quick Sort)
일반적으로 가장 빠르다고 알려진 정렬 알고리즘이다.
피벗을 선택하고, 그룹 나누기를 반복하며 정렬한다.
그룹을 나누는 피벗 값은 임의로 설정 가능하다.
일반적으로는 중앙값을 선택한다.
피벗 값보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 몰아서 2개의 그룹을 먼저 만든다.
이후 각각의 그룹에서 다시 피벗을 설정하고, 왼쪽/오른쪽으로 몰아서 또 다른 2개의 그룹을 만든다.
이 과정을 원소가 1개만 남을 때까지 반복하고, 결합하면서 정렬된 배열을 완성한다.
재귀 호출을 통해 구현된다.
12.1) 배열을 2개의 그룹으로 나누기
피벗 x를 선택한 뒤, 두 그룹으로 분할해야 한다.
먼저 포인터 pl과 pr을 설정해 각각 배열 맨 왼쪽과 배열 맨 오른쪽에 배치한다.
피벗 이하인 원소들을 배열의 왼쪽, 피벗 이상인 원소를 배열의 오른쪽으로 이동시킨다.
포인터 pl을 x 방향으로 1칸씩 이동하면서 a[pl] > a[x]를 만족하는 지를 검사한다.
만약 조건이 참이라면 교환이 필요하므로 포인터 pl 이동을 중지한다.
포인터 pr 또한 x 방향으로 1칸씩 이동하면서 a[pr] < a[x]를 만족하는 지를 검사한다.
만약 조건이 참이라면 교환이 필요하므로 포인터 pr 이동을 중지한다.
포인터 pl, pr 모두 멈췄다면 값을 교환한다.
pl과 pr은 같아지거나 pl이 pr보다 커질 수 없다.
만약 pl과 pr이 같아지거나 pl이 pr보다 커지면 교환 작업을 멈춰야 한다.
12.2) 퀵 정렬 재귀 호출
원소 수가 2개 이상인 그룹이 존재한다면 피벗을 설정하고 pl, pr을 사용해 정렬하는 과정을 반복한다.
더 이상 분할이 불가능한 원소가 1개가 남을 때까지 반복해야 한다.
12.3) 퀵 정렬 구현
from typing import MutableSequence
class Quick :
def _Qsort(a: MutableSequence, left: int, right: int) -> None :
pl = left
pr = right
x = a[(left+right) // 2]
while (pl <= pr) :
while (a[pl] < x) :
pl += 1
while (a[pr] > x) :
pr += 1
if (pl <= pr) :
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if (left < pr) :
_Qsort(a, left, pr)
if (pl < right) :
_Qsort(a, pl, right)
def Qsort(a: MutableSequence) -> None :
_Qsort(a, 0, len(a) - 1)_Qsort() 함수는 배열 a와 배열을 분할할 구간의 1번째 원소의 인덱스(left)와 마지막 원소의 인덱스(right)를 전달받아 퀵 정렬을 수행한다.
12.4) 비재귀적인 퀵 정렬 구현
스택을 사용하면 비재귀적으로 퀵 정렬을 구현할 수 있다.
스택은 후입 선출 구조이므로, pl과 pr 인덱스 값을 1쌍으로 스택에 넣고, 분할이 이루어질 때마다 스택에서 값을 꺼낸다.
이때, 분할된 두 그룹 중에서 원소가 많은 쪽과 작은 쪽 중 어느 쪽을 먼저 스택에 푸시하는가에 따라 스택에 들어가는 데이터의 수가 달라진다.
원소가 많은 쪽 그룹을 먼저 푸시할 경우, 스택에 동시에 쌓이게 되는 데이터의 수가 줄어든다.
원소가 적은 쪽 그룹을 먼저 푸시할 경우, 스택에 동시에 쌓이게 되는 데이터의 수가 많아진다.
이때, 원소가 많은 쪽 그룹을 먼저 푸시할 때보다, 원소가 적은 쪽 그룹을 먼저 푸시하는 것이 속도가 더 빠르다.
12.5) 비재귀적인 퀵 정렬 구현
from stack import Stack
from typing import MutableSequence
class Quick :
def Qsort1(a: MutableSequence, left:int, right: int) -> None :
""" Quick Sort; Non-Recur Ver """
range = Stack(right - left + 1)
range.push((left, right))
while not range.is_empty() :
pl, pr = left, right = range.pop()
x = a[(left + right) // 2] ## Pivot
while (pl <= pr) :
while (a[pl] < x) :
pl += 1
while (a[pr] > x) :
pr -= 1
## SWAP ##
if (pl <= pr) :
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
## END SWAP END ##
if (left < pr) :
range.push((left, pr))
if (pl < right) :
range.push((pl, right))range 변수를 사용해 새로운 스택을 생성한다.
초기값은 전체 배열의 pl, pr 값이 된다.
푸시 이후, 배열을 나눌 때 스택에서 pop() 연산을 수행해 빼낸 값을 pl, pr 변수에 할당한다.
피벗을 설정한 뒤, pl과 pr 값을 비교해 교환하는 작업을 수행한다.
12.6) 효율적인 피벗 선택
피벗을 선택하는 것은 퀵 정렬의 실행 효율에 큰 영향을 미친다.
맨 앞의 원소를 피벗으로 설정했을 때와 배열의 중앙값 원소를 피벗으로 선택했을 때를 비교한다.
- 맨 앞 원소를 피벗으로 설정할 경우: 피벗이 완전히 한쪽으로 치우친 분할을 반복하게 되므로 빠른 정렬이 불가능해진다.
- 중앙값 원소를 피벗으로 설정할 경우: 한쪽으로 치우친 분할 대신 균형 잡힌 분할이 가능해진다. 하지만 배열에서 가운데 원소를 찾기 위한 처리가 추가로 필요하고, 이 또한 시간이 오래 걸리는 작업이다. 즉, 퀵 정렬을 사용하는 의미가 사라지게 된다.
- 분할할 배열의 원소 수가 3개 이상일 때, 임의의 원소 3개를 꺼내 중앙값을 피벗으로 선택하는 경우: 배열의 처음, 중간, 끝 값 중에 중앙값을 선정한다. 선정된 중앙값을 피벗으로 사용하여 퀵 정렬을 수행한다.
- 분할할 배열의 처음, 중간, 끝 원소를 정렬한 뒤, 중간 원소와 맨 끝에서 2번째 원소를 교환하여 맨 끝에서 2번째 원소 a[right-1]을 피벗으로 선택하는 경우: 그룹이 치우치는 현상을 방지함과 동시에, 스캔할 원소 3개를 줄이고 시작할 수 있다.
12.7) 효율적인 퀵 정렬 구현
일반적으로 퀵 정렬은 원소 수가 적은 경우에는 비효율적이라고 알려져 있다.
이를 보안하기 위해 원소 수가 9개 미만일 때는 단순 삽입 정렬을 사용하도록 구성한다.
from typing import MutableSequence, Any
class Quick :
def Qsort2(a: MutableSequence, left: int, right: int) -> None :
""" Quick Sort; Quick Sort + Insertion Sort Ver """
def Sort3(a: MutableSequence, idx1: int, idx2: int, idx3: int) :
if (a[idx2] < a[idx1]) :
a[idx2], a[idx1] = a[idx1], a[idx2]
if (a[idx3] < a[idx2]) :
a[idx3], a[idx2] = a[idx2], a[idx3]
if (a[idx2] < a[idx1]) :
a[idx2], a[idx1] = a[idx1], a[idx2]
return idx
if (right - left) < 9 :
Lab8_QuickSort.InsertionSort(a, left, right)
pl = left ## Left Point
pr = right ## Right Point
x = a[(left + right) // 2] ## Pivot
print(f"a[{left}] ~ a[{right}]: ", *a[left : right + 1])
while (pl <= pr) :
while (a[pl] < x) :
pl += 1
while (a[pr] > x) :
pr -= 1
## SWAP ##
if (pl <= pr) :
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
## END SWAP END ##
if (left < pr) :
Lab8_QuickSort.Qsort(a, left, pr)
if (pl < right) :
Lab8_QuickSort.Qsort(a, pl, right)
수고하셨습니다!
'Dev. Study Note > Algorithm (Python)' 카테고리의 다른 글
| 16. 트리 (0) | 2022.01.25 |
|---|---|
| 15. 리스트 (0) | 2022.01.22 |
| 13. 하노이의 탑과 8 Queens (0) | 2022.01.21 |
| 12. 재귀 알고리즘 (0) | 2022.01.19 |
| 11. 큐 (0) | 2022.01.18 |
