정렬 알고리즘이란?
정렬알고리즘이란 키를 항목값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꿔 늘어놓는 작업을 의미한다. 정렬에서 값을 나열하는것에 따라 두가지의 종류가 있다.
- 오름차순 : 값이 작은 데이터를 앞쪽에 늘어놓는것
- 내림차순 : 값이 큰 데이터를 앞쪽에 늘어놓는 것
정렬알고리즘은 어디에 활용이 되나?
- 파일 처리(파일 관리자의 파일 정렬)
- 데이터 베이스
- 전화번호부
주로 데이터를 일정하게 나열해야하는 상황에서 많이 쓰인다.
정렬 알고리즘에서 안정성
정렬알고리즘에는 "안정한 정렬" "불안정한 정렬" 두가지가 존재한다. 여러 정렬 알고리즘의 종류가 있는데, 앞으로 각 정렬알고리즘을 보면서 안정적인지, 불안정적인지 살펴볼 것이다. 추후 각 정렬별로 안정적인지, 안정적이지 않은지에 대해 다루어 볼 것이다,
- 안정적인 정렬 : 값이 같은 원소의 순서가 정렬 후에도 유지되는것 의미
- 안정적이지 않은 정렬 : 정렬 후에도 유지된다는 보장이 없는 정렬이다
내부 정렬과 외부정렬
정렬에서 하나의 배열에서 작업할 수 있는 경우와 하나의 배열에서 작업할 수 없는 경우 두가지로 나누어서 구분할 수 도 있다.
- 내부 정렬 : 하나의 배열에서 작업할 수 있는경우
- 외부 정렬 : 하나보다 더 많은 배열에서 작업해야하는 경우
정렬 알고리즘의 핵심
정렬 알고리즘의 핵심은 총 세가지이다.
- 교환
- 선택
- 삽입
대부분의 정렬 알고리즘은 데이터를 교환, 선택, 삽입 알고리즘을 사용해서 정렬을 완료한다. 이 세가지 개념이 정렬의 핵심 작동임을 기억하자
단순 버블 정렬(Bubble Sort)
단순 버블 정렬은 이웃한 두 원소의 대소관계를 비교해 필요에 따라 교환을 반복하는 알고리즘이다. 이는 단순 교환 정렬이라고도 한다.
버블정렬은 총 n-1번의 비교/교환이 이루어져야 한다. 한번 정렬을 한 다음에, 정렬된 이후의 배열의 값에 대해서만 검사를 하면 된다. 그렇기 때문에, 다시 배열의 범위를 정렬된 범위를 제외한 범위로 재정의 해주어야 한다. 버블정렬은 총 O(n^2)의 시간복잡도를 가지는 매우 비효율적인 알고리즘이다. 즉, 정렬할 데이터가 많을 수록 더더욱 비효율적이게 되는 것이다. 버블정렬은 이웃한 원소만 정렬하기 때문에 안정적인 정렬이라고 할 수 있다.
from typing import AnyStr, MutableSequence
def bubble_sort(a : MutableSequence) -> None:
n = len(a)
for i in range(n - 1):
for j in range(n - 1, i, -1):
if a[j] < a[j-1]:
a[j-1],a[j] = a[j],a[j-1]
if __name__ == "__main__":
a = [1,6,4,3,7,8,9]
bubble_sort(a)
print(a)단순 선택 정렬(Selection Sort)
단순 선택 정렬은 가장 작은 원소부터 선택하여 알맞은 위치로 옮기는 작업을 반복하는 알고리즘이다. 단순 선택정렬의 교환과정은 아래와 같다
- 정렬하지 않은 부분의 배열에서 가장 작은 원소를 선택한다
- 가장 작은 원소와 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.
위 두 과정을 총 n - 1번 반복하면 정렬이 완료된다.
단순 선택정렬은 이웃하지 않는 원소간의 교환이 이루어 지므로 안정적이지 않은 정렬이다. 불안정한 정렬이라고 하는 이유는 동일한 값이 두개가 있다고 가정 했을때, 선택정렬은 정렬되지 않은 범위를 모두 검색하면서 가장 작은 값을 선택하게 된다. 그렇기 때문에, 뒤에 있는 중복값이 우선적으로 선택되어 정렬되는 방식이므로, 안정적이지 못하다.
선택정렬 또한 버블정렬과 동일하게 이중 for문이 쓰이므로 총 O(n^2)의 시간복잡도를 가지게 된다. 단순 선택 정렬의 구현은 아래와 같다. 바깥쪽 루프 범위를 n-1로 잡는 이유는 가장 첫번째 값이 가장 작은 값이라고 가정하고 시작하기 위함이고(정렬되지 않은 부분 이라는 범위를 가져야하므로 최소 한개의 원소를 가지는 정렬되지 않은 범위 조건을 만족시켜주어야한다), 내부 루프의 범위를 i + 1로 잡은것은, 정렬된 부분을 제외한 나머지 범위 내에서 가장 작은 값을 검색하기 위함이다.
from typing import AnyStr, MutableSequence
def selection_sort(a: MutableSequence) -> None:
n= len(a) # 전체 길이를 저장한다
for i in range(n - 1):
min = i # 정렬되지 않은 부분의 가장 첫번째 원소를 선택한다.
for j in range(i + 1, n): # 정렬되지 않은 부분의 첫번째 원소를 제외한 부분에서 가장 작은 값을 찾는다.
if a[j] < a[min]:
min = j
a[i],a[min] = a[min],a[i] # 찾은 가장 작은 원소와 정렬되지 않은 부분 첫번째 원소를 바꿔준다.
if __name__ =="__main__":
a = [6,4,3,1,7,8,9]
selection_sort(a)
print(a)단순 삽입 정렬(Insertion Sort)
단순 삽입 정렬은 주목한 원소보다 더 앞쪽에 알맞은 위치로 삽입하여 정렬하는 알고리즘이다. 선택 정렬과 비슷해 보이지만, 가장 작은 원소를 선택하지 않는다는 점에서 다르다. 삽입 정렬은 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입해 주는 원리이다. 삽입정렬은 기본적으로 길이가 2 이상인 배열에서 성립이 되고 시작은 index 1부터 시작된다. 처음 시작할때 index 0을 정렬된 부분이라는 가정에서 시작을 해야하기 때문이다.
삽입 정렬 또한 크게 총 n-1번의 비교 / 교환 의 과정이 있어야한다. 그리고 각 한번씩의 비교 / 교환 삽입정렬의 종료 조건 두가지를 살펴보면
- 정렬된 배열의 왼쪽 끝에 도달한 경우(index 0번까지 정렬되지 않은 부분 첫번째 원소의 자리를 찾지 못한 경우)
- 정렬되지 않은 부분의 첫번째 값보다 작거나 키값이 같은 원소를 발견할 경우
이 조건 두가지에 대해서 드모르간 법칙을 적용해 보면 조건을 아래 두가지로 간추릴 수 있다.
- 검사중인 index가 0보다 큰 경우
- 정렬되지 않은 부분의 첫번째 값이 검사중인 index - 1번 보다 큰 경우
삽입정렬은 아래와 같이 구현할 수 있다. 삽입정렬 또한 O(n^2)의 시간 복잡도를 가지게 된다.
import random
from typing import MutableSequence
def selection_sort(a : MutableSequence) -> None:
n = len(a)
for i in range(1, n):
j = i
value = a[i]
while j > 0 and value < a[j-1]:
a[j] = a[j-1]
j = j-1
a[j] = value
if __name__ == "__main__":
li = [6,4,3,7,1,9,8]
selection_sort(li)
print(li)그리고 삽입 정렬의 원리가 선택 정렬과 유사한 감은 있지만, 선택정렬과 다르게, 안정적인 정렬 의 성격을 가지고 있다. 기본적으로 정렬하고자 하는 값보다 클때까지만 검색하고 정렬을 하기 때문이다. 유도를 해보면 아래와 같이 할 수 있다. 중복되는 두개의 1이 순서를 유지하면서 정렬되는 모습을 볼 수 있다.
이진 삽입 정렬(Binary Insertion Sort)
삽입정렬은 배열 원소수가 많아지게 되면, 비교/교환하는데 드는 비용이 커진다. 하지만, 이진 검색법을 사용해 삽입정렬을 하면, 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야하는 위치를 검사할 수 있기에, 비용을 줄일 수 있다. 이진검색을 사용해서 삽입정렬을 구현하면 아래와 같이 작성해 줄 수 있다
import random
from typing import MutableSequence
def binary_insertion_sort(a: MutableSequence):
n = len(a)
for i in range(1,n):
key = a[i]
pl = 0
pr = i - 1
while True:
pc = (pl + pr) //2
if a[pc] == key:
break
if a[pc] > key:
pr = pr - 1
else:
pl = pl + 1
if pl > pr:
break
if pl <= pr:
pd = pc + 1
else:
pd = pl
for j in range(i,pd,-1):
a[j] = a[j-1]
a[pd] = key
if __name__ == "__main__":
a = [1,3,11,8,7,12,5,4]
binary_insertion_sort(a)
print(a)기본적으로 만약 pc의 값이 정렬하고자 하는 값과 동일한 값이 나온다면, pc의 자리에 값이 들어가야 하므로 pc ~ i - 1번째 자리에 있는 값들을 pc + 1 ~ i범위 배열로 옮겨주고, pc의 자리에 정렬하고자 하는 값을 넣어주면 되는것이다. 이진 삽입정렬도 시간복잡도는 O(n^2)로 비효율적인 알고리즘이지만, 정렬해야하는 자리 검색에 있어서는 더 나은 효율성을 보여준다.
퀵 정렬(Quick Sort)
퀵정렬은 가장 빠른 정렬 알고리즘으로 널리 사용된다. 퀵정렬은 기본적으로 배열의 그룹을 나누는 '분할 정복법'을 접목하여 정렬을 하는 형태이다.
우선적으로 배열을 나누는 분할 정복법을 살펴보자. 배열을 나눌때 '피벗' 이라는 개념을 사용한다. 피벗이란, '기준점' 이되는 값을 의미한다.
예를 들어 [5,7,1,4,6,2,4,9,8] 이라는 배열이 있다고 가정하자. 가운데값 '6'을 피벗으로 선택하고 그룹을 나눈다. 가장 왼쪽의 인덱스 값을 pl, 오른쪽 인덱스 값을 pr이라고 하자. 이때 피벗 이하인 원소들을 피벗 기준 왼쪽으로, 피벗 이상인 원소들을 피벗 기준 오른쪽으로 이동시켜주어야 한다. 아래 두가지 조건을 따라 수행해야한다.
- a[pl] >= pivot가 성립하는 원소를 찾을때까지 오른쪽 스캔
- a[pr] <= pivot가 성립하는 원소를 찾을때 까지 왼쪽 스캔
이 과정을 거치고, pl,pr은 각각 조건에 해당하는 원소를 찾게되면 정지한다. 그 후 index pl과 index pr의 값을 교환해 준다. 이 과정이 완료되면 피벗 이하의 값은 왼쪽, 이상의 값은 오른쪽으로 가게 된다. 이 과정의 결론은 두가지 유형의 결과를 만들게 된다. 두가지 유형을 각각 살펴보자
<pl,pr이 교차하는 경우>
이와 같이 pr,pl이 교차되는 시점에 대해서는 두가지 그룹으로 나누어 진다.
- 피벗 이하 그룹 : a[0 : pl - 1]
- 피벗 이상 그룹 : a[pr + 1 :]
< pl > pr + 1의 경우>
이번에는 [1,8,7,4,5,2,6,3,9] 배열을 똑같은 방식으로 나누어 보자
이번에는 pl, pr이 교차가 되는 상태가 아닌 pr + 1 < pl 상태가 된다. 이런 경우에는 피벗과 일치하는 그룹이 만들어 지게 된다. 이런 경우에 대해서 아래와 같은 두가지 배열로 나눌 수 있다.
- 피벗 이하인 범위 : a[0 : pl]
- 피벗 이상인 범위 : a[pr + 1 :]
추가적으로 피벗과 일치하는 부분은 사실상 정렬이 완료된 상태인 부분이라고 볼 수 있다. 위 그림을 보면 피벗 5를 기준으로 왼쪽은 5보다 작은값들이, 오른쪽은 5보다 큰 값들이 집결한 것을 알 수 있다. 피벗 기준, 배열 나누는 코드를 간단히 작성하면 아래와 같이 작성할 수 있다.
from typing import MutableSequence
def partition(a: MutableSequence) -> None:
n = len(a)
pl = 0
pr = n - 1
pivot = a[(pl + pr) // 2]
while pl <= pr:
while a[pl] < pivot: pl += 1
while a[pr] > pivot: pr -= 1
if pl <= pr:
a[pl],a[pr] = a[pr],a[pl]
pl += 1
pr -= 1
if pl > pr + 1:
print(f"피봇 : {pivot}" )
print(f"피봇 이하 그룹 : {a[0 : pr + 1]}")
print(f"피봇 이상 그룹 : {a[pr + 1:]}" )
else:
print(f"피봇 : {pivot}" )
print(f"피봇 이하 그룹 : {a[0 : pr + 1]}")
print(f"피봇 이상 그룹 : {a[pl:]}" )
if __name__ == "__main__":
a = [5,7,1,4,6,2,3,9,8]
b = [1,8,7,4,5,2,6,3,9]
partition(a)
'''
피봇 : 6
피봇 이하 그룹 : [5, 3, 1, 4, 2]
피봇 이상 그룹 : [6, 7, 9, 8]
'''
partition(b)
'''
피봇 : 5
피봇 이하 그룹 : [1, 3, 2, 4]
피봇 이상 그룹 : [5, 7, 6, 8, 9]
'''
이 원리를 발전시켜, 퀵정렬을 구현할 수 있다. 기본적인 퀵정렬은 재귀적인 성격을 띄고 있다. 우선 위에 배열 분할하는것을 보았을때 배열을 나누는 과정을 마쳤을때 pr값과 pl값이 교차되어있는 형태로 볼 수 있다. 그리고 pr, pl을 가지고 왼쪽 범위, 오른쪽 범위로 나누어 배열 나누기를 계속 해주면 된다. 값은 재귀가 되는 기준은 아래 두가지와 같다.
- pr > left
- pl < right
구현 코드는 아래와 같다.
from typing import MutableSequence
def qsort(a : MutableSequence, left : int, right : int):
pl = left
pr = right
pivot = a[(pl + pr) // 2]
print(f"a[{left}] ~ a[{right}] : {a[left : right + 1]}")
while pl <= pr:
while a[pl] < pivot: pl += 1
while a[pr] > pivot: 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 right > pl: qsort(a,pl,right)
def quick(a : MutableSequence) -> None:
qsort(a,0,len(a) - 1)
if __name__ == "__main__":
a = [5,8,4,2,6,1,3,9,7]
quick(a)
print(a)퀵정렬의 평균 시간 복잡도는 O(nlogn)이며, 최악의 경우에는 O(n^2)라고 한다. O(n^2)인 경우는 정렬된 배열에 대해서, 역순으로 정렬된 경우(내림차순) 이 두가지에 대해서만 이라고 한다.
또한 데이터 개수가 매우 적은 상황이나, 거의 다 정렬된 상태에서는 O(nlogn)만큼의 속도가 나오지 않으며, 이런 경우에 대해서는 삽입정렬이 더 빠른 속도를 구현한다고 한다.
그리고 퀵정렬은 pl,pr값이 순회하며 이웃하지 않는 값들을 바꾸는 방식이므로, 안정적이지 않은 정렬 에 속하게 된다. 파이썬같은 경우 내장 함수중 sorted()함수가 퀵정렬을 이용해서 작동되는 함수이다.
퀵 정렬은 기본적으로, 피벗을 기준 왼쪽을 피벗보다 작은 원소로, 오른쪽을 피벗보다 큰 원소로 분류 한 후에 정렬을 한다. 이 원리를 활용해 두 부분만 바꿔주면, 내림차순을 하는 퀵정렬로 바꿀 수 있다.
from typing import MutableSequence
def qsort(a : MutableSequence, left : int, right : int):
pl = left
pr = right
pivot = a[(pl + pr) // 2]
print(f"a[{left}] ~ a[{right}] : {a[left : right + 1]}")
while pl <= pr:
while a[pl] > pivot: pl += 1 # 부호 변경 : 피봇보다 작거나 같은 원소 검색
while a[pr] < pivot: 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 right > pl: qsort(a,pl,right)
def quick(a : MutableSequence) -> None:
qsort(a,0,len(a) - 1)
if __name__ == "__main__":
a = [5,8,4,2,6,1,3,9,7]
quick(a)
print(a)병합정렬(Merge Sort)
from __future__ import annotations
from typing import MutableSequence
def merge_sort(a : MutableSequence):
def inner_merge_sort(a,left,right) -> None:
if left < right:
center = (left + right) // 2
inner_merge_sort(a,left,center)
inner_merge_sort(a,center + 1, right)
p = j = 0
i = k = left
while i <= center:
arr[p] = a[i]
p += 1
i += 1
while i <= right and j < p:
if arr[j] <= a[i]:
a[k] = arr[j]
j += 1
else:
a[k] = a[i]
i += 1
k += 1
while j < p:
a[k] = arr[j]
k += 1
j += 1
n = len(a)
arr = [None] * n
inner_merge_sort(a,0,len(a)-1)
del arr
a = [5,8,4,2,6,1,3,9,7]
merge_sort(a)
print(a)