1. 시간 복잡도
먼저, 정렬의 성능과 관련된 시간 복잡도에 대해 알아보겠습니다.
1-1. 시간 복잡도
시간 복잡도란, 코드의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도입니다.
시간 복잡도의 점근 표기법으로는 3가지가 있습니다.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
이 중에서 알고리즘의 시간 복잡도를 측정할 때, 주로 빅오(Big-O) 표기법을 사용합니다.
이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이며, 입력값의 크기가 증가할 때 표기법을 보고 어떻게 증가하는지 파악할 수 있습니다.
1-2. Big-O 표기법


① O(1) - 상수 시간 복잡도
· 입력 크기에 관계없이 일정한 시간 안에 실행됩니다.
ex) 인덱스를 통한 배열의 요소 접근, stack의 push·pop
② O(n) - 선형 시간 복잡도
· 실행시간이 입력크기에 따라 선형적으로 증가합니다.
ex) 정렬되지 않은 배열에서의 선형 검색, 1중 for문
③ O(log n) - 로그 시간 복잡도
· 실행시간이 입력 크기에 따라 대수적으로 증가합니다.
ex) 정렬된 배열에서의 이진 검색, binary search 알고리즘
④ O(n log n) - 선형 시간 복잡도
· 실행시간이 입력 크기에 따라 n x log n만큼 증가합니다.
ex) 퀵 정렬, 병합 정렬, 힙 정렬
⑤ O(n²) - 2차 시간 복잡도
· 실행시간이 입력 크기에 따라 2차적으로 증가합니다.
ex) 입력을 반복하는 중첩 루프, 삽입정렬, 거품정렬, 선택정렬
⑥ O(2ⁿ) - 지수 시간 복잡도
· 실행시간이 입력 크기에 따라 기하급수적으로 증가합니다.
ex) 모든 가능한 조합을 시도하는 무차별 대입 알고리즘, 피보나치수열
⑦ O(n!) - 팩토리얼 시간 복잡도
· 실행시간이 입력 크기에 따라 팩토리얼적으로 증가합니다.
ex) 집합의 모든 순열을 생성하는 알고리즘
2. 정렬 알고리즘
2-1. Stable과 In-place
· Stable 정렬
정렬했을 때 중복된 값들의 순서가 변하지 않는 것을 말합니다.
arr = [ 1, 3(1), 3(2), 7, 5, 4 ]를 정렬했을 때,
- arr = [ 1, 3(1), 3(2), 4, 5, 7 ] ⇒ Stable( 안정 )
- arr = [ 1, 3(2), 3(1), 4, 5, 7 ] ⇒ Unstable( 불안정 )
· In-place 정렬
정렬하는데 추가적인 메모리 공간이 거의 들지 않는 것을 말합니다.
2-2. Bubble Sort ( 거품 정렬 )

- 마치 물속에서 올라오는 물방울과 같다고 하여, Bubble Sort라는 이름이 붙여졌습니다.
- 거품 정렬은 첫 번째 원소부터 인접한 원소끼리 비교하며 자리를 바꾸면서, 맨 끝부터 정렬하는 방식입니다.
- n번째 원소와 n+1번째 원소의 값을 비교하고, n+1째의 값이 더 크다면 둘의 자리를 바꿉니다. 이를 반복하여 가장 끝부터 큰 수가 쌓이도록 하는 정렬입니다.
# Bubble Sort (python)
def BubbleSort(arr):
n = len(arr)
for j in range(n-1):
for i in range(n-j-1):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
return arr
① 장점
- 코드가 직관적이며 구현이 간단합니다.
- Stable 정렬과 In-place 정렬에 해당합니다.
② 단점
- 데이터를 하나씩 비교하기 때문에 시간 복잡도가 최선, 평균, 최악이 모두 O(n²)이며 굉장히 비효율적입니다.
- 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않습니다.
③ 개선된 Bubble Sort
" 칵테일 셰이커 ( Cocktail Shaker ) 정렬" - 양방향 버블 정렬

- Bubble Sort가 한 방향으로 정렬하는 방식이라면, 칵테일 셰이커는 최댓값, 최솟값이 배열 가장자리에 위치하여 왕복하는 정렬이다.
- 정렬되는 동작이 칵테일 셰이커를 흔드는 것과 비슷하다고 하여 이름이 붙여졌다.
def Cocktail(arr):
a, b = 0, len(arr)-1 # 시작, 끝
direction = True # 방향 변환
swap = True #
while swap:
swap = False
# 정방향
if direction:
for i in range(a, b):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swap = True # 목표값 발견
b = b - 1
direction = False # 방향 전환
# 역방향
else:
for i in range(b-1, a-1, -1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swap = True # 목표값 발견
a = a + 1
direction = True # 방향 전환
2-3. Selection Sort ( 선택 정렬 )

- 거품 정렬과 반대로 앞 쪽부터 정렬합니다
- 정렬하고자 하는 범위에서 가장 작은 최솟값을 찾아 맨 앞의 값과 위치를 바꾸면서 정렬합니다.
- 가장 작은 값을 찾았다면, 맨 앞을 제외한 배열을 다시 정렬합니다.
- 비교 횟수는 많지만 실제로 값을 옮기는 횟수는 적다는 특징을 가지고 있습니다.
- 배열의 최솟값을 찾아 선택하여 정렬한다는 뜻에서 이름이 붙여졌습니다.
def SelectionSort(arr):
n = len(arr)
for i in range(n-1):
minIdx = i
# 최솟값 위치 찾기
for j in range(i+1, n):
if arr[j] < arr[minIdx]:
minIdx = j
arr[i], arr[minIdx] = arr[minIdx], arr[i]
① 장점
- 코드가 직관적이며 구현이 간단합니다.
- In-place 정렬에 해당합니다.
② 단점
- 데이터를 하나씩 비교하기 때문에 시간 복잡도가 최선, 평균, 최악이 모두 O(n²)이며 굉장히 비효율적입니다.
- 구현하는 방식에 따라 Unstable 정렬 형태를 가질 수 있습니다.
- 새로운 데이터 추가 시 정렬 효율이 좋지 않습니다. ( 비교 횟수가 많다 보니 )
2-4. Insertion Sort ( 삽입 정렬 )

- 거품 정렬의 비효율성을 개선하기 위해 등장한 방법입니다.
- 모든 요소를 앞에서부터 차례대로 이미 정렬이 된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬입니다.
- 버블 정렬보다 비교 및 교환 횟수가 적습니다.
def InsertionSort(arr):
n = len(arr)
for end in range(1, n):
for i in range(end, 0, -1):
if arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
① 장점
- 입력으로 들어오는 배열의 원소가 정렬되어 있으면 속도가 빠릅니다. ( 모두 정렬이 되어있으면 O(n) )
- 이미 정렬되어 있는 배열에 원소를 삽입/제거하는 경우에 효율적인 알고리즘입니다.
- Stable 정렬과 In-place 정렬에 해당합니다.
② 단점
- 평균과 최악의 시간복잡도가 O(n²)에 해당합니다.
- 배열의 길이가 길어질수록 비효율적입니다.
2-5. Quick Sort ( 퀵 정렬 )

- 분할 정복( Divide and Conquer ) 방법을 통한 정렬로, 하나의 축(pivot)을 정해서 축보다 작은 값은 왼쪽에 큰 값은 오른쪽에 정렬하는 방법입니다.
분할 정복
분할( Divide ) - 문제를 분할하여 비슷한 유형의 작은 문제로 분할이 가능할 때까지 나눈다.
정복( Conquer ) - 각 문제를 재귀적(반복적)으로 해결한다.
- 분할( Divide ) : pivot(축)을 선택하여 배열을 나눈다. (왼쪽과 오른쪽)
- 정복( Conquer ) : pivot을 기준으로 pivot보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 정렬한다.
- 일반적으로는 준수한 효율을 보이기 때문에 대부분의 내장 라이브러리에서 존재하는 정렬 함수는 QuickSort를 사용하고 있습니다.
def QuickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
tail = arr[1:]
left = [x for x in tail if x <= pivot] # pivot보다 작거나 같으면 왼쪽
right = [x for x in tail if x > pivot] # pivot보다 크면 오른쪽
return QuickSort(left) + [pivot] + QuickSort(right)
① 장점
- 불필요한 데이터의 이동을 줄일 수 있습니다.
- 최선과 평균의 경우 O(n log n)의 시간 복잡도를 가지고 있어 다른 정렬 알고리즘에 비해 빠른 편입니다.
- In-place 정렬입니다.
② 단점
- 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸릴 수 있습니다.
- pivot이 최솟값이나 최댓값으로 선택되어 분할이 불균형하게 이루어지는 경우 O(n²)의 시간복잡도를 가질 수 있습니다.
- Unstable 정렬입니다.
2-6. Merge Sort ( 병합 정렬 )

- 퀵 정렬과 마찬가지로 분할 정복( Divide and Conquer ) 방법을 이용한 정렬입니다.
- 분할( Divide ) : 배열을 더 이상 쪼갤 수 없는 단위( 1~2개 부분 배열 )까지 분할합니다.
- 정복( Conquer ) : 나누어진 부분 배열을 정렬합니다.
- 분할·정복을 통해 정렬된 배열을 마지막에 병합(Merge)하여 정렬을 완료합니다.
# Conquer
def Merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < len(left):
result.append(left[i])
i += 1
while j < len(right):
result.append(right[j])
j += 1
return result
# Divide
def MergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = MergeSort(left)
right = MergeSort(right)
return Merge(left, right)
① 장점
- 시간 복잡도가 최선, 평균, 최악이 모두 O(n log n)에 해당하며 빠른 정렬에 속합니다.
- Stable 정렬입니다.
② 단점
- 정렬을 하는 배열 이외에 추가적인 메모리 ( 임시 배열 )이 필요로 합니다.
- Not In-place 정렬입니다.
2-7. Heap Sort ( 힙 정렬 )
- 힙(Heap) : 우선순위 큐( Queue에 우선순위의 개념을 접목 )를 위해 고안된 완전이진트리 형태의 자료구조
- 완전이진트리(Complete Binary Tree) : 이진트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리

- 최대 힙 트리 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
- 최소 힙 트리 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
- 힙 정렬 개념
- 정렬해야 할 n개의 요소들로 힙(Heap)을 만듭니다. ( 내림차순은 최대 힙, 오름차순은 최소 힙)
- 힙 트리로 구한 최댓값(최솟값)에 해당하는 root 노드를 빼내면서 정렬을 수행합니다.
def heapify(arr,n,i):
root = i
left = 2*i + 1
right = 2*i + 2
# 왼쪽 노드가 존재하고, 루트보다 더 큰 값일 때
if left < n and arr[root] < arr[left]:
root = left
# 오른쪽 노드가 존재하고, 루트보다 더 큰 값일 때
if right < n and arr[root] < arr[right]:
root = right
# 왼쪽, 오른쪽 자식 노드들과 바꿔줄 위치를 찾았을 때
if root != i:
# 찾아낸 값과 swap
arr[i],arr[root] = arr[root],arr[i]
# 계속 heap 형태를 갖출 때까지 실행
heapify(arr,n,root)
def HeapSort(arr):
n = len(arr)
# heap 형태로 데이터를 정렬한다.
for i in range(n,-1,-1):
heapify(arr,n,i)
# root와 마지막값을 바꿔 정렬하고 바뀐값을 기준으로 다시 heapify
for i in range(n-1,0,-1):
arr[i],arr[0] = arr[0],arr[i]
heapify(arr,i,0)
return arr
① 장점
- 최댓값, 최솟값을 구할 때 매우 유용합니다.
- 항상 같은 시간 복잡도 O(n log n)를 유지하기 때문에 성능이 준수합니다.
- 주어진 배열 내부에서 위치를 바꾸는 방식을 적용하면 In-place 정렬도 가능합니다.
② 단점
- 퀵 정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않습니다.
- Unstable 정렬입니다.
③ Python "heapq" 라이브러리
- python에서는 heapq 모듈을 통해 힙을 제공합니다.
import heapq
arr = []
heapq.heapify(arr) # 기존의 리스트를 Heap 형태로 변환
# 힙 형태를 유지하면서 n값 추가
heapq.heappush(arr, 3) # arr = [3]
heapq.heappush(arr, 1) # arr = [1, 3]
heapq.heappush(arr, 2) # arr = [1, 3, 2]
# 힙 형태를 유지하면서 가장 작은 원소를 꺼낸다.
heapq.heappop(arr) # arr = [2, 3]
heapq를 이용한 heap정렬
import heapq
def HeapSort_heapq(arr):
heapq.heapify(arr)
result = []
for i in range(len(arr)):
x = heapq.heappop(arr)
result.append(x)
return result
arr = [0, 1, 5, 7, 4, 3, 2, 6]
HeapSort_heapq(arr) # [0, 1, 2, 3, 4, 5, 6, 7]
3. 그 외 정렬
위의 정렬들은 가장 많이 알려진 정렬이고, 다음의 정렬들은 이번에 공부하면서 새롭게 알게 된 정렬입니다.
3-1. Counting Sort ( 계수 정렬 )
- 데이터의 크기를 비교하지 않고, 각 데이터의 개수를 파악하여(Counting) 이를 앞 순서대로 정렬하는 방식입니다.
1) 인덱스를 이용한 계수정렬 ( Unstable )
- 가장 큰 데이터의 값을 담을 수 있는 카운팅 배열(Counting)과 결과 값을 담을 배열(result)을 준비합니다.
- 인덱스를 활용해 카운팅 배열에 데이터 값의 개수를 더합니다.
- Counting에서 0이 아닌 값들의 위치를 찾아 result에 해당 값만큼 인덱스를 넣어줍니다.
def CountingSort(arr):
Counting = [0] * (max(arr)+1)
result = []
for num in arr:
Counting[num] += 1
for idx in range(len(Counting)):
if Counting[idx] != 0:
for _ in range(Counting[idx]):
result.append(idx)
return result
arr = [1, 3, 5, 4, 2, 1, 2]
CountingSort(arr) # [1, 1, 2, 2, 3, 4, 5]
2) 누적합을 이용한 계수정렬 ( Stable )
- 가장 큰 데이터의 값을 담을 수 있는 카운팅 배열(Counting)과 결과 값을 담을 배열(result)을 준비합니다.
- 누적합을 활용해 카운팅 배열에 데이터 값의 개수를 더합니다.
- Counting에서 arr의 데이터 인덱스를 찾아 result에 바로 대입합니다.



# 누적합을 이용한 정렬
def CountingSort(arr):
Counting = [0] * (max(arr)+1)
result = [0] * len(arr)
for i in arr:
Counting[i] += 1
# 누적합을 이용하여 Counting 갱신
for i in range(1, len(Counting)):
Counting[i] += Counting[i-1]
# Stable한 정렬을 하기위해 뒤에서 부터 찾기
for num in ragne(len(arr)-1, -1, -1):
i = arr[num]
idx = Counting[i]
result[idx-1] = i # idx의 첫번째는 0이기 때문에 -1
Counting[i] -= 1
return result
① 장점
- 중복된 값이 많은 정렬을 정렬할 때 유리합니다.
- O(n)의 시간복잡도를 가집니다.
② 단점
- 정확한 시간 복잡도는 O(n + k)이며 k는 정렬하고자 하는 배열에서의 가장 큰 값입니다.
- 따라서, 입력 데이터의 최댓값에 따라 카운팅 배열의 크기가 매우 커질 수 있습니다. ( 메모리 낭비 발생 )
- 인덱스를 이용하는 정렬이기 때문에 데이터가 양의 정수인 경우에 사용할 수 있습니다.
- Not In-place 정렬입니다.
3-2. Radix Sort ( 기수 정렬 )
- 데이터의 각 자릿수를 낮은 자릿수에서부터 가장 큰 자릿수까지 올라가면서 정렬합니다.
- 최대 자릿수를 구하고, bucket배열을 만들어 순서대로 (1의 자리, 10의 자리, 100자리...) 같은 원소들을 생성한 배열에 모읍니다.
- 비교연산을 하지 않아 빠른 정렬 속도를 보여줍니다.
- 나올 수 있는 값의 최대 사이즈가 9이기 때문에, 계수 정렬의 단점을 보완할 수 있습니다.
from collections import deque
def RadixSort(arr):
buckets = [deque() for _ in range(10)]
queue = deque(arr)
maxNum = max(arr) # 가장 큰 값
digit = 1 # 자리수
while maxNum >= digit:
while queue:
number = queue.popleft()
idx = (number // digit) % 10
buckets[idx].append(number) # 자리수에 맞게 넣기
# queue 재 정렬
for bucket in buckets:
while bucket:
queue.append(bucket.popleft())
digit *= 10 # 자리수 점차 늘리기
return list(queue)

① 장점
- O(dn) 시간복잡도로 빠른 정렬을 보여줍니다. ( d는 데이터들의 최대 자릿수를 의미합니다. )
- Stable 정렬입니다.
② 단점
- 자릿수가 없는 것은 정렬할 수 없습니다. ( 부동 소수점 )
- 중간 과정을 담을 수 있는 bucket 공간이 필요합니다.
- Not In-plcae 정렬입니다.
3-3. Shell Sort ( 셸 정렬 )
- Donald L. Shell이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에서 빠르게 정렬된다는 사실에 착안한 방법입니다.
- 방법
1) 정렬할 배열을 일정한 간격(Gap)으로 나눕니다. ( 일반적으로는 반으로 나눈 값으로 시작합니다. )
2) 일정한 Gap으로 나눈 배열에 대해 삽입 정렬을 수행합니다.
3) 점차 Gap을 줄여가며 정렬을 반복합니다.
def InsertionSort(arr, first, last, gap):
idx = first + gap
while idx <= last:
cur = arr[idx]
position = idx
while (position > first) and (arr[position - gap] > cur):
arr[position] = arr[position - gap]
position -= gap
arr[position] = cur
idx += gap
def ShellSort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for start in range(gap):
InsertionSort(arr, start, n-1, gap)
gap //= 2
return arr

① 장점
- 어느 정도 정렬된 배열에서 O(n) 시간복잡도로 빠른 속도를 보여줍니다.
- Stable 정렬입니다.
② 단점
- 일정한 간격에 따라 배열을 보기 때문에, 간격 설정을 잘못할 경우 성능이 저하될 수 있습니다.
4. 시간 복잡도 정리
| 정렬 | 최악 ( Worst ) | 평균 ( Average ) | 최선 ( Best ) |
| Bubble Sort ( 버블정렬 ) | O(n²) | O(n²) | O(n²) |
| Selection Sort ( 선택정렬 ) | O(n²) | O(n²) | O(n²) |
| Insertion Sort ( 삽입정렬 ) | O(n²) | O(n²) | O(n) |
| Quick Sort ( 퀵 정렬 ) | O(n²) | O(nlogn) | O(nlogn) |
| Merge Sort ( 병합 정렬 ) | O(nlogn) | O(nlogn) | O(nlogn) |
| Heap Sort ( 힙 정렬 ) | O(nlogn) | O(nlogn) | O(nlogn) |
| Counting Sort ( 계수 정렬 ) | O(n) | O(n) | O(n) |
| Radix Sort ( 기수 정렬 ) | O(n) | O(n) | O(n) |
| Shell Sort ( 셸 정렬 ) | O(n²) | O(n^1.5) | O(n) |
Big O Notation: A Complete Overview With Real-World Applications
Big O Notation in Data Structure tells us how well an algorithm will perform in a particular situation. In other words, it gives an algorithm's upper-bound runtime or worst-case complexity. Click here to know more.
www.simplilearn.com
https://east-star.tistory.com/10
정렬 알고리즘(Sorting Algorithm) 정복하기 - with JS
안녕하세요. 동쪽별입니다. 이번 포스트에서는 여러 정렬 알고리즘에 대해 살펴보고, 자바스크립트로 구현해보도록 하겠습니다. 목차 거품 정렬(Bubble Sort) 선택 정렬(Selection Sort) 삽입 정렬(Insert
east-star.tistory.com
버블정렬, 칵테일정렬, 빗질정렬
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘정렬과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블정렬
velog.io
https://mong9data.tistory.com/45
[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)
정의 - 일정 간격(interval) 떨어져 있는 원소들끼리 부분집합을 구성한 후 각 부분집합의 원소들에 대해서 삽입 정렬을 수행하되, 간격을 줄여가며 삽입 정렬을 반복하여 전체 원소들을 정렬하는
mong9data.tistory.com
'Algorithm' 카테고리의 다른 글
| 동적 계획법(DP) [Python] (0) | 2022.04.29 |
|---|