자료구조 정리 : 정렬
정렬이란?
정렬 : 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
안정적인 정렬 알고리즘
-> 값이 같은 원소의 순서가 정렬한 후에도 유지되는 정렬 알고리즘
안정적이지 않은 정렬 알고리즘은 정렬한 후에 원래 순서가 유지된다는 보장 없음
내부정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 정렬
외부정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 정렬
정렬 알고리즘의 핵심
- 교환
- 선택
- 삽입
버블 정렬
- 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘
- 단순 교환 정렬
- 패스 : 일련의 비교를 수행하는 과정
- 패스를 한 번 수행할 때마다 정렬할 대상이 한개씩 감소
- 모든 정렬을 마치기 위해선 패스를 (n-1)번 수행해야함
- 패스를 k번 수행하면 맨 앞부터 k개 원소가 정렬됨
from typing import 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 - 1] > a[j]:
a[j], a[j - 1] = a[j - 1], a[j]
셰이커 정렬
- 칵테일 정렬, 칵테일 셰이커 정렬
- 양방향 버블 정렬
- 홀수 패스에서 가장 작은 원소를 맨 앞으로 이동
- 짝수 패스에서 가장 큰 원소를 맨 뒤로 이동
- 스캔 범위 첫 원소 이름 : left
- 스캔 범위 마지막 원소 이름 : right
from typing import MutableSequence
def shaker_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 = last
단순 선택 정렬
- 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하여 정렬
- 셔틀 정렬
- 안정적이지 않은 정렬 알고리즘
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-1)번 반복
- 알맞은 위치에 삽입
from typing import MutableSequence def insertion_sort(a : MutableSequence) -> None: n = len(a) for i in range(1, n): j = i tmp = a[i] while j > 0 and a[j - 1] > tmp: a[j] = a[j - 1] j -= 1 a[j] = tmp - 반복 제어 변수 j에 i를, tmp에 a[i]를 대입하고 종료조건 만족시까지 j를 1씩 감소하며 대입 작업을 진행
- 종료조건
- 정렬된 배열의 왼쪽 끝에 도달한 경우
- tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견한 경우
- 계속조건
- j가 0보다 큰 경우
-
tmp보다 a[j-1]의 값이 큰 경우
이진 삽입 정렬
- 단순 삽입 정렬은 배열의 원소 수가 많아지면 원소 삽입에 필요한 비교, 교환 비용이 커짐
- 이진 검색을 이용하여 원소 삽입 위치 계산에 필요한 비용을 절약
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()함수
- 파이썬 표준 라이브러리에서 단순 삽입 정렬 알고리즘 함수를 제공
- bisect.insort(a, x, lo, hi)
-
a가 이미 정렬된 상태를 유지하면서 a[io] ~ a[hi]사이에 x를 삽입
-
셸 정렬
단순 삽입 정렬의 문제
- 삽입할 위치가 멀리 떨어져 있으면 이동 횟수 증가
셸 정렬
- 단순 삽입 정렬의 장점을 살리면서 단점을 보완
- 먼저 정렬한 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한 뒤 정렬된 그룹을 합치는 작업을 반복 -> 이동 횟수를 줄임
h-정렬
- 서로 h칸 떨어진 원소를 정렬하는 것으로 셸 정렬 과정에서 수행하는 각각의 단순 삽입 정렬
셸 정렬의 수행 과정
- 모든 정렬은 단순 삽입 정렬을 수행
- 셸 정렬은 단순 삽입 정렬의 장점을 살리고 정렬 횟수는 늘어나지만 이동 횟수는 줄어듬
from typing import MutableSequence
def shell_sort(a : MutableSequence) -> None:
n = len(a)
h = n // 2
while h > 0:
for j in range(h, n):
j = i - h
tmp = a[i]
while j>= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 2
### h값의 선택
- 원소 수가 8이라면 h는 4, 2, 1 순으로 변화
- 학생 8명의 점수를 나열하는 문제
- 학생 2명씩 4개 그룹으로 나누어 정렬한 뒤, 학생 4명씩 2개 그룹으로 나누어 정렬
- 4개의 그룹에서 두 그룹을 합쳐 2개의 그룹으로 만들 때 두 그룹의 원소가 섞이지 않음
- h값은 서로 배수가 되지 않아야 원소가 섞일 수 있음
- h의 초기값은 n//9를 넘지 않은 큰 수에서 시작
from typing import MutableSequence def shell_sort(a : MutableSequence) -> None: n = len(a) h = 1 while h < n // 9: h = h * 3 + 1 while h > 0: for j in range(h, n): j = i - h tmp = a[i] while j>= 0 and a[j] > tmp: a[j + h] = a[j] j -= h a[j + h] = tmp h //= 2
# 퀵 정렬
- 일반적으로 사용되는 가장 빠르다고 알려진 정렬 알고리즘
- 피벗(중심 축)
- 그룹을 나누는 기준
- 임의로 선택할 수 있고, 선택된 피벗은 2개로 나눈 그룹 어디에 넣어도 무관
- 피벗을 선택하여 그룹 나누기를 반복하며 정렬
배열을 두 그룹으로 나누기
- 피벗을 선택하여 두 그룹으로 분할
- pl : 분할할 배열의 왼쪽 끝 원소의 인덱스
- pr : 분할할 배열의 오른쪽 끝 원소의 인덱스
- 피벗 이하인 원소를 배열의 왼쪽으로, 피벗 이상인 원소를 배열의 오른쪽으로 이동
- a[pl] >= x가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔, a[pr] <= x가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔
- pl과 pr이 서로 교차할 때까지 반복
- 그룹을 나누는 작업이 끝난 후 pl > pr +1 인 경우에 한하여 피벗과 일치하는 그룹이 생성
- a[pr + 1],…, a[pl-1]
- pl과 pr 모두 피벗과 같은 위치에 있음
- 이 경우에도 같은 원소를 교환하는 작업이 필요함
- 교환하는 작업을 하지 않으면 pl과 pr이 같은 위치에 있게 됨
퀵 정렬 만들기
- 원소 수가 2개 이상인 그룹을 반복해서 분할
- pr이 0보다 크면 (left < pr)왼쪽 그룹으로 분할
- pl이 n-1보다 작으면(pl < right)오른쪽 그룹으로 분할
- 원소수가 1개인 그룹과 가운데 그룹은 더 이상 분할할 필요가 없음
- 퀵 정렬은 분할 정복 알고리즘으로 재귀 호출을 사용하여 생성 가능 ```python from typing import MutableSequence def qsort(a : MutableSequence, left : int, right : int) -> None: n = len(a) 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 quick_sort(a : MutableSequence) -> None: qsort(a, 0, len(a) - 1)
## 비재귀적인 퀵 정렬의 구현
- 배열을 분할할 범위(맨 앞의 원소의 인덱스와 맨 끝의 원소의 인덱스를 조합)를 튜플 형태로 스택에 저장
- (left, right)
```python
%%writefile stack.py
from typing import Any
from collections import deque
class Stack:
def __init__(self, maxlen : int = 256) -> None:
self.capacity = maxlen
self.__stk = deque([], maxlen)
def __len__(self) -> int:
return len(self.__stk)
def is_empty(self)-> bool:
return not self.__stk
def is_full(self) -> bool:
return len(self.__stk) == self.__stk.maxlen
def push(self, value : Any) -> None:
self.__stk.append(value)
def pop(self) -> Any:
return self.__stk.pop()
def peek(self) -> Any:
return self.__stk[-1]
def clear(self) -> None:
self.__stk.clear()
def find(self, value : Any) -> Any:
try:
return self.__stk.index(value)
except ValueError:
return -1
def count(self, value : Any) -> int:
return self.__stk.count(value)
def __contains__(self, value : Any) -> bool:
return self.count(value)
def dump(self) -> None:
print(list(self.__stk))
from stack import Stack
def qsort(a, left, right):
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]
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 : range.push((left, pr))
if pl < right : range.push((pl, right))
def quick_sort(a : MutableSequence) -> None:
qsort(a, 0, len(a) - 1)
스택의 크기
- 퀵 정렬로 배열 나누기(피벗 : 2)
- 스택에 배열을 푸시하는 규칙
- 규칙 1 : 원소 수가 많은 쪽의 그룹을 먼저 푸시
- 규칙 2 : 원소 수가 적은 쪽의 그룹을 먼저 푸시
- 원소 수가 적은 배열일수록 나누는 과정을 빠르게 마칠 수 있으며, 규칙 1과 같이 원소 수가 많은 그룹의 나누기를 나중에 하면 스택에 동시에 쌓이는 데이터 수가 적어짐
- 규칙 1에 따르면 스택에 쌓이는 데이터의 최대 개수는 logn보다 작아짐
## 피벗 선택하기
- 피벗 선택 방법은 퀵 정렬 효율에 큰 영향을 미침
- 맨 앞의 원소를 피벗으로 선택한 경우
- 피벗만 있는 그룹과 나머지 원소 그룹으로 분할
- 한쪽으로 완전히 치우친 분할을 반복하게함
- 배열을 완전히 정렬한 뒤 피벗으로 중앙값을 선택하는 것이 가장 빠른 경우
- 정렬된 배열의 중앙값을 구하기 위한 처리에 대한 비용이 소모되어 피벗을 선택하는 의미가 없어짐
- 방법 1 : 분할할 배열의 원소수가 3개 이상이면 임의의 원소 3개를 꺼내 중앙값을 피벗으로 지정
- 방법 2 : 분할할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤, 가운데 원소와 맨 끝에서 두번째 원소를 교환하여 맨 끝에서 두번째 원소 a[right -1]을 피벗으로 선택
- 그룹이 한쪽으로 치우치는 것을 방지하여 스캔할원소를 3개 줄일 수 있음
효율적인 퀵 정렬의 구현
- 퀵 정렬은 원소 수가 적은 경우 비효율적이라 알려져있음
- 원소 수가 9개 미만인 경우 단순 삽입 정렬 사용
sorted() 함수
- 파이썬에서 정렬을 수행하는 내장 함수
- 전달받은 이터러블 객체의 원소를 정렬하여 리스트 형으로 반환
- 정렬을 수행한 뒤 늘어선 원소를 새로운 리스트로 생성하여 반환
- 오름차순을 기본
# 병합 정렬
- 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 뒤 병합하는 작업을 반복하는 정렬 알고리즘
- 각 배열에서 주목하는 원소의 값과 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장
- 각 배열을 스캔할 때 주목하는 원소의 인덱스를 pa, pb, pc라고 하고 0으로 초기화
from typing import Sequence, MutableSequence def merge_sorted_list(a : Sequence, b : Sequence, c : MutableSequence) -> None: pa, pb, pc = 0, 0, 0 na, nb, nc = len(a), len(b), len(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
병합 정렬 알고리즘
- 병합 정렬을 하는 방법
- 배열을 나누고 나눈 두 배열을 각각 정렬한 뒤 병합하여 배열 정렬을 완료(분할 정복법)
- 병합 정렬 알고리즘
- 배열의 원소 수가 2개 이상인 경우
- 배열의 앞부분을 병합 정렬로 정렬
- 배열의 뒷부분을 병합 정렬로 정렬
- 배열의 앞부분과 뒷부분을 병합
- 배열의 원소 수가 2개 이상인 경우
- 서로 떨어져 있는 원소를 교환하는 것이 아니므로 안정적임