정글 1주차, 주어진 알고리즘 문제를 해결하다가 수 정렬하기 문제들을 마주하게 되었다. 다른 알고리즘 문제들과 달리 정렬에 대한 학습이 필요함을 느껴서 블로그에 정리해두려고 한다. 그럼 알고리즘의 꽃이라 할 수있는 정렬의 세계로 들어가보자!
정렬(Sorting)이란?
키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업. 목록의 요소를 특정 순서대로 넣는 알고리즘이다. 대개 숫자식 순서(Numerical Order)와 사전식 순서(Lexicographical Order)로 정렬한다.
알고리즘의 안정성
안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 반면, 안정적이지 않은 알고리즘은 정렬 후에도 원래의 순서가 보장되지 않는다.
예를 들어 안정 정렬의 경우 기존의 시간 순으로 정렬했던 순서는 지역명으로 재정렬하더라도 기존 순서가 그대로 유지된 상태에서 정렬이 이뤄진다. 그러나 불안정 정렬의 경우에는 기존의 정렬 순서는 무시된 채 모두 뒤죽박죽 뒤섞이고 만다.
대표적으로 병합 정렬과 버블 정렬은 안정 정렬이고, 퀵 정렬은 불안정 정렬이다.
정렬 용어
-
내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 (여기서 다룰 알고리즘은 모두 내부 정렬이다.)
-
외부 정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
-
패스(Pass) : 일련의 비교﹒교환하는 과정
정렬 알고리즘의 핵심
-> 교환, 선택, 삽입
목차
- 버블 정렬
- 단순 선택 정렬
- 단순 삽입 정렬
- 셸 정렬
- 퀵 정렬
- 병합 정렬
- 힙 정렬
- 도수 정렬
1. 버블 정렬
버블 정렬은 데이비드 핸슨이 화이트 보드에 버블정렬을 구하지 못할 것이라고 트윗한 것이 매우 유명한 밈(Meme)이 되었고, 버락 오바마가 구글 CEO였던 에릭 슈미트의 질문에 "버블 정렬은 잘못된 시작일 것 같습니다."라고 말할 정도로 비효율적이 정렬이다.
버블 정렬
이웃한 두원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘.
단순 교환 정렬이라고도 한다.
Pseudo Code
Bubblesort(A)
for i from 1 to A.length
for j from 0 to A.length -1
if A[j] > A[j+1]
swap a[j] with a[j+1]시간 복잡도
버블 정렬 알고리즘은 n번의 라운드로 이뤄져 있으며, 각 라운드마다 배열의 아이템을 한 번씩 쭉 모두 살펴본다. 배열 전체를 쭉 살펴보는 것을 n번 하기 때문에 시간 복잡도는 항상 O(n²)이다. 이보다 더 비효율적일 수는 없으며 구현 가능한 가장 느린 정렬 알고리즘이다.
알고리즘 개선
- 교환 횟수가 0이 되면 중단
from typing import MutableSequence
def bubble_sort(a: MutableSequence) -> None:
n = len(a)
for i in range(n-1):
exchng = 0
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
exchng += 1
if exchng == 0:
break- 이미 정렬된 원소를 제외한 나머지만 비교﹒교환하도록 스캔 범위 제한
from typing import MutableSequence
def bubble_sort(a: MutableSequence) -> None:
n = len(a)
k = 0
while k < n-1:
last = n-1
for j in range(n-1, k, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
last = j
k = last- 셰이커 정렬(shaker sort)
- 양방향 버블 정렬(bidirectional bubble sort), 칵테일 정렬(cocktail sort), 칵테일 셰이커 정렬(cocktail shaker sort)라고도 한다.
- 홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시켜 스캔 방향을 번갈아 바꾼다.
from typing import MutableSequence
def bubble_sort(a: MutableSequence) -> None:
left = 0
right = len(a)-1
last = right
while left < right:
for j in range(right, left, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
last = j
left = last
for j in range(left, right):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
last = j
right = last2. 단순 선택 정렬(Straight Selection Sort)
단순 선택 정렬
가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘
교환 과정 및 Pseudo Code
- 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택
- a[min]과 아직 정렬하지 않은 부분에서 맨앞에 있는 원소를 교환
for i in range(n-1):
min <- a[i]~a[n-1]에서 키값이 가장 작은 원소의 인덱스
a[i]와 a[min]의 값을 교환Code
from typing import 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]특징
- 단순 선택 정렬 알고리즘의 원솟값을 비교하는 횟수는 (n²-n)/2번이다. (버블 정렬과 비슷)
- 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않다.
3. 단순 삽입 정렬(Straight Insertion Sort)
단순 삽입 정렬
주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
단순 선택 정렬과 달리 값이 가장 작은 원소를 선택하지 않는다.
교환 과정 및 Pseudo Code
아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입
for i in range(1, n):
tmp <- a[i]를 넣는다.
tmp를 a[0], ﹒﹒﹒, a[i-1]의 알맞은 위치에 삽입- 종료 조건 1: 정렬된 배열의 왼쪽 끝에 도달한 경우
- 종료 조건 2: tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견한 경우
드모르간 법칙으로
- 계속 조건 1: j가 0보다 큰 경우
- 계속 조건 2: a[j-1]의 값이 tmp보다 큰 경우
Code
from typing import MutableSequence
def insertion_sort(a: MutableSequence) -> None:
n = len(a)
for i in range(1, n):
j = 1
tmp = a[i]
while j > 0 and a[j-1] > tmp:
a[j] = a[j-1]
j -= 1
a[j] = tmp특징
- 서로 떨어져 있는 원소를 교환하지 않으므로 안정적
- 원소의 비교 횟수와 교환 횟수는 모두 n²/2번
시간 복잡도
지금까지 다룬 3가지 단순 정렬(버블, 선택, 삽입) 알고리즘의 시간 복잡도는 모두 O(n²)으로 프로그램 효율이 좋지 않다. 다음 포스트부터 단순 정렬 알고리즘의 개선방법을 적용한 알고리즘에 대해 알아보자.
이진 삽입 정렬(binary insertion sort)
단순 삽입 정렬은 원소 수가 많아지면 비교﹒교환 비용이 커진다. 그러나 이진 삽입 정렬을 이용하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있다.
from typing import MutableSequence
def binary_insertion_sort(a: MutableSequence) -> None:
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
elif a[pc] < key:
pl = pc + 1 # 검색 범위를 뒤쪽 절반으로 좁힘
else:
pr = pc - 1 # 검색 범위를 앞쪽 절반으로 좁힘
if pl > pr:
break
pd = pc + 1 if pl <= pr else pr + 1 # 삽입해야 할 위치의 인덱스
for j in range(i, pd, -1):
a[j] = a[j-1]
a[pd] = key파이썬 표준 라이브러리에서 bisect 모듈의 insort() 함수로 제공한다.
이미 정렬이 끝난 배열의 상태를 유지하면서 원소를 삽입한다.
from typing import MutableSequence
import bisect
def binary_insertion_sort(a: MutableSequence) -> None:
for i in range(1, len(a)):
bisect.insort(a, a.pop(i), 0, i)