정렬에 대한 내용 정리
선택 정렬
📋 정의
배열에서 아직 정렬되지 않은 부분에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 알고리즘
동작과정
- 주어진 리스트에서 가장 작은 요소를 찾습니다.
- 해당 요소를 리스트의 첫 번째 요소와 교환합니다.
- 첫 번째 요소를 제외한 나머지 리스트에서 다시 가장 작은 요소를 찾습니다.
- 해당 요소를 리스트의 두 번째 요소와 교환합니다.
- 반복합니다.
시간복잡도
📋 정의
선택 정렬의 시간 복잡도는 최선, 최악 모두 $O(n^2)$
이중 반복문을 사용해여 리스트를 탐색하고 교환하기 때문
이중 반복문을 사용해여 리스트를 탐색하고 교환하기 때문
특징
- 입력에 민감하지 않음 (항상 $O(n^2)$ 수행시간)
- 최솟값을 찾은 후 원소를 교환하는 횟수 → $n - 1$: 최악의 경우
- 선택 정렬은 효율성이 좋은 편이 아니여서 잘 쓰이지 않음
구현 코드
def selection_sort(a):
# 리스트의 길이만큼 반복
for i in range(0, len(a) - 1):
# 최소값의 인덱스를 현재 위치로 초기화
minimum = i
# 현재 위치 이후의 리스트에서 최소값 탐색
for j in range(i + 1, len(a)):
if a[minimum] > a[j]:
minimum = j
# 현재 위치와 찾은 최소값의 위치를 교환
a[i], a[minimum] = a[minimum], a[i]
# 예제 리스트
a = [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
# 정렬 전 리스트 출력
print('정렬 전:\t', end='')
print(a)
# 선택 정렬 함수 호출
selection_sort(a)
# 정렬 후 리스트 출력
print('정렬 후:\t', end='')
print(a)
정렬 전: [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후: [10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
삽입 정렬
📋 정의
배열이 정렬된 부분과 정렬 안 된 부분으로 나뉘며, 정렬이 안된 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입하여 정렬
동작과정
- 리스트의 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분에 적절한 위치에 삽입합니다.
- 현재 요소를 정렬된 부분의 마지막 요소와 비교하여, 더 작다면 그 요소를 오른쪽으로 이동시킵니다.
- 이 과정을 첫 번째 요소까지 반복하여, 적절한 위치에 현재 요소를 삽입합니다.
- 리스트의 모든 요소가 정렬될 때까지 1-3 과정을 반복합니다.
시간 복잡도
시간복잡도
최선 → $O(n)$ (리스트가 이미 정렬되어 있는 경우)
평균 → $O(n^2)$
최악 → $O(n^2)$ (리스트가 역순으로 정렬되어 있는 경우)
평균 → $O(n^2)$
최악 → $O(n^2)$ (리스트가 역순으로 정렬되어 있는 경우)
구현 코드
def insertion_sort(a):
# 두 번째 요소부터 시작하여 리스트 끝까지 반복
for i in range(1, len(a)):
# 현재 요소의 인덱스를 기준으로 내부 루프 시작
for j in range(i, 0, -1):
# 현재 요소가 그 이전 요소보다 작으면 위치 교환
if a[j - 1] > a[j]:
a[j], a[j - 1] = a[j - 1], a[j]
else:
# 현재 요소가 더 크거나 같으면 교환할 필요가 없으므로 내부 루프 종료
break
# 예제 리스트
a = [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
# 정렬 전 리스트 출력
print('정렬 전:\t', end='')
print(a)
# 삽입 정렬 함수 호출
insertion_sort(a)
# 정렬 후 리스트 출력
print('정렬 후:\t', end='')
print(a)
정렬 전: [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후: [10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
특징
- 리스트가 이미 정렬된 경우 매우 효율적임
- 안정적인 정렬 알고리즘으로 입력 크기가 작은 경우에도 매우 좋은 성능을 보임
- 합병 정렬이나 퀵 정렬과 함께 사용되어 실질적으로 성능 향상(단, 이론적인 수행 시간을 향상되지 않음)
힙 정렬(Heap Sort)
📋 정의
힙 자료구조를 이용하는 정렬, 힙은 완전 이진 트리의 일종, 최대 힙과 최소 힙으로 구분되는 자료구조.
힙 정렬은 주로 최대 힙을 사용해여 오름차순으로 정렬함
힙 정렬은 주로 최대 힙을 사용해여 오름차순으로 정렬함
동작 과정
- 힙 구성(Build Heap): 주어진 리스트를 최대 힙으로 구성합니다. 최대 힙이란 부모 노드가 자식 노드보다 항상 크거나 같은 완전 이진 트리입니다.
- 정렬(Sort): 최대 힙의 루트(가장 큰 값)를 리스트의 마지막 요소와 교환하고, 리스트의 길이를 줄여가며 다시 최대 힙을 구성하는 과정을 반복합니다.
구현 코드
def downheap(i, size):
# 루트로 올라온 키에 대해 힙속성을 회복시킴
while 2 * i <= size:
k = 2 * i
if k < size and a[k] < a[k + 1]:
k += 1
if a[i] >= a[k]:
break
a[i], a[k] = a[k], a[i]
i = k
def create_heap(a):
# 정렬하기 전에 최대힙 만들기
hsize = len(a) - 1
for i in reversed(range(1, hsize // 2 + 1)):
downheap(i, hsize)
def heap_sort(a):
N = len(a) - 1
for i in range(N):
# 루트와 힙의 마지막 항목 교환
a[1], a[N] = a[N], a[1]
downheap(1, N - 1)
# 힙 크기 1 감소
N -= 1
a = [-1, 54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
print('정렬 전:\t', end='')
print(a)
create_heap(a) # 힙 만들기
print('최대힙:\t', end='')
print(a)
heap_sort(a)
print('정렬 후:\t', end='')
print(a)
- 파이썬의 heapq를 활용버전
import heapq
a = [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
print('정렬전:\t', a)
heapq.heapify(a)
print('힙:\t', a)
s = []
while a:
s.append(heapq.heappop(a))
print('정렬후:\t', s)
정렬 전: [-1, 54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
최대힙: [-1, 93, 88, 77, 26, 77, 31, 49, 20, 17, 54, 11, 17, 22, 44, 17, 10]
정렬 후: [-1, 10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
시간 복잡도
시간복잡도
힙 구성 → $O(n)$
루트와 힙의 마지막 노드를 교환한 후 downheap() 수행 → $O(\log n)$
루트와 힙의 마지막 노드를 교환하는 횟수 → $n - 1$
총 수행시간 → $O(n) + (n - 1) \times O(\log n) = O(n\log n)$
최선 → $O(n\log n)$
평균 → $O(n\log n)$
최악 → $O(n\log n)$
공간 복잡도 → $O(1)$ (추가적인 리스트 사용하지 않음)
루트와 힙의 마지막 노드를 교환한 후 downheap() 수행 → $O(\log n)$
루트와 힙의 마지막 노드를 교환하는 횟수 → $n - 1$
총 수행시간 → $O(n) + (n - 1) \times O(\log n) = O(n\log n)$
최선 → $O(n\log n)$
평균 → $O(n\log n)$
최악 → $O(n\log n)$
공간 복잡도 → $O(1)$ (추가적인 리스트 사용하지 않음)
특징
- C/C++ 표준 라이브러리의 parial_sort는 힙 정렬로 구현됨
- 어떠한 입력에도 항상 $O(n\log n)$의 시간 복잡도 유지
- 루프 내의 코드가 길고 비효율적인 캐시 메모리 사용
합병 정렬(Merge Sort)
📋 정의
합병 정렬은 분할 정복 알고리즘을 사용하는 정렬 알고리즘
크기가 n인 입력을 $n/2$ 크기로 분할하고, 각각에 대해 순환으로 합병 정렬을 수행한후, 2개의 각각 정렬된 부분을 합병하는 알고리즘
크기가 n인 입력을 $n/2$ 크기로 분할하고, 각각에 대해 순환으로 합병 정렬을 수행한후, 2개의 각각 정렬된 부분을 합병하는 알고리즘
- 분할(Divide): 배열을 절반으로 나눕니다.
- 정복(Conquer): 나눠진 각각의 배열을 재귀적으로 합병 정렬을 사용하여 정렬합니다.
- 합병(Merge): 정렬된 두 배열을 합쳐 하나의 정렬된 배열로 만듭니다.
동작 과정
- 분할:
- 주어진 배열을 반으로 나누어 두 개의 하위 배열로 분할합니다.
- 이 과정을 배열의 크기가 1이 될 때까지 재귀적으로 반복합니다.
- 정복:
- 배열의 크기가 1이 되면, 이는 이미 정렬된 상태이므로 정복 과정에서는 아무 작업도 하지 않습니다.
- 합병:
- 두 개의 정렬된 배열을 하나의 정렬된 배열로 합칩니다.
- 이 과정에서 두 배열의 각 요소를 비교하여 작은 값을 먼저 결과 배열에 넣습니다.
구현 코드
def merge(a, b, low, mid, high):
i = low
j = mid + 1
for k in range(low, high + 1):
# a의 앞/뒷부분 합병하여 b에 저장
if i > mid:
b[k] = a[j]
j += 1
elif j > high:
b[k] = a[i]
i += 1
elif a[j] < a[i]:
b[k] = a[j]
j += 1
else:
b[k] = a[i]
i += 1
for k in range(low, high + 1):
# b를 a로 복사
a[k] = b[k]
def merge_sort(a, b, low, high):
if high <= low:
return
mid = low + (high - low) // 2
merge_sort(a, b, low, mid)
merge_sort(a, b, mid + 1, high)
merge(a, b, low, mid, high)
a = [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
b = [None] * len(a)
print('정렬 전:\t', end='')
print(a)
merge_sort(a, b, 0, len(a) - 1)
print('정렬 후:\t', end='')
print(a)
정렬 전: [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후: [10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
시간 복잡도
시간복잡도
최선 → $O(n\log n)$
평균 → $O(n\log n)$
최악 → $O(n\log n)$
공간 복잡도 → $O(n)$ (추가적인 배열 공간 사용)
평균 → $O(n\log n)$
최악 → $O(n\log n)$
공간 복잡도 → $O(n)$ (추가적인 배열 공간 사용)
특징
- 어떤 입력에 대해서도 $O(n\log n)$ 시간 보장
- 성능 향상 방법
- 합병 정렬의 순환 호출(재귀)시점 수정 → 원래는 배열의 크기가 1일때 합병 시작, 입력이 정해진 크기가 되었을때 삽입 정렬 할 수 있도록 수정가능
def merge_sort(a, b, low, high):
if high <= low + CALLSIZE{ # if high <= low: retrun
Insertion.sort(a, low, high);
return;
}
- 두 개의 리스트가 이미 정렬되어 있는 경우 merge() 호출을 방지하여 성능 향상
merge_sort(a, b, low, mid)
merge_sort(a, b, mid + 1, high)
if(a[mid] <= a[mid + 1])
return;
merge(a, b, low, mid, high)
- 보조 리스트 b를 입력 리스트 a로 복사하는 merge()방식을 a, b의 역할을 번갈아 사용하도록 수정해서 성능 향상
반복 합병 정렬
📋 정의
입력 리스트에서 바로 2개씩 짝지어 합병한 뒤, 다시 4개씩 짝지어 합병하는 상향식(Bottom-up)으로도 수행 가능
Bottom-up 합병, 반복 합병 정렬
Bottom-up 합병, 반복 합병 정렬
시간 복잡도
시간복잡도
최선 → $O(n\log n)$
평균 → $O(n\log n)$
최악 → $O(n\log n)$
평균 → $O(n\log n)$
최악 → $O(n\log n)$
- 입력 크기의 보조 메모리를 사용해야 하는 단점
퀵 정렬(Quick Sort)
📋 정의
분할 정복(Divide and Conquer) 방법을 사용하는 정렬 알고리즘
리스트를 피벗(Pivot)을 기준으로 두 부분으로 나눈 뒤, 각 부분을 재귀적으로 정렬하는 방식
피벗은 리스트에서 임의로 선택한 요소
리스트를 피벗(Pivot)을 기준으로 두 부분으로 나눈 뒤, 각 부분을 재귀적으로 정렬하는 방식
피벗은 리스트에서 임의로 선택한 요소
동작 방식
- 피벗 선택: 리스트에서 하나의 요소를 피벗으로 선택합니다.
- 분할: 피벗을 기준으로 리스트를 두 부분으로 나눕니다.
- 피벗보다 작은 요소들은 피벗의 왼쪽 부분에 위치합니다.
- 피벗보다 큰 요소들은 피벗의 오른쪽 부분에 위치합니다.
- 재귀 정렬: 분할된 두 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다.
구현 코드
def qsort(a, low, high):
if low < high:
pivot = partition(a, low, high) # 피벗을 기준으로 분할
qsort(a, low, pivot-1) # 앞/뒷부분 재귀호출
qsort(a, pivot+1, high)
def partition(a, pivot, high):
i = pivot + 1
j = high
while True:
while i < high and a[i] < a[pivot]: # a[i]가 피벗보다 작으면 i를 1 증가
i += 1
while j > pivot and a[j] > a[pivot]: # a[j]가 피벗보다 크면 j를 1 감소
j -= 1
if j <= i: # 루프 중단
break
a[i], a[j] = a[j], a[i] # a[i]와 a[j] 교환
i += 1
j -= 1
a[pivot], a[j] = a[j], a[pivot] # a[j]와 피벗 교환
return j # 피벗 인덱스
a = [54, 88, 77, 26, 93, 17, 49, 10, 77, 11, 31, 22, 44, 17, 20]
print('정렬 전:\t', a)
qsort(a, 0, len(a) - 1)
print('정렬 후:\t', a)
정렬 전: [54, 88, 77, 26, 93, 17, 49, 10, 77, 11, 31, 22, 44, 17, 20]
정렬 후: [10, 11, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
정렬 알고리즘의 복잡도 정리
댓글남기기