정렬이란?
- 가장 기본적이고 중요한 알고리즘
- 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있음
- 정렬된 자료는 탐색에 더 효율적
정렬 알고리즘 종류
- 단순하지만 비효율적인 방법
- 복잡하지만 효율적인 방법
- 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등
선택 정렬
- 리스트에서 가장 작은 숫자를 선택하여 리스트 앞쪽으로 옮기는 방법
- 시간 복잡도: O(n²)
def selection_sort(A): # 선택 정렬
n = len(A)
for i in range(n-1):
least = i
for j in range(i+1, n):
if A[j] < A[least]:
least = j
A[i], A[least] = A[least], A[i]
printStep(A, i+1)
def printStep(arr, val):
print("Step {} = ".format(val), end='')
print(arr)
data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original:", data)
# Original: [5, 3, 8, 4, 9, 1, 6, 2, 7]
selection_sort(data)
# Step 1 = [1, 3, 8, 4, 9, 5, 6, 2, 7]
# Step 2 = [1, 2, 8, 4, 9, 5, 6, 3, 7]
# Step 3 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
# Step 4 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
# Step 5 = [1, 2, 3, 4, 5, 9, 6, 8, 7]
# Step 6 = [1, 2, 3, 4, 5, 6, 9, 8, 7]
# Step 7 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Step 8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print("Selection:", data)
# Selection: [1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입 정렬
- 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하는 방법
- 시간 복잡도
- 최선: O(n)
- 최악: O(n²)
- 평균: O(n²)
def insertion_sort(A): # 삽입 정렬
n = len(A)
for i in range(1, n):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j -= 1
A[j+1] = key
printStep(A, i)
def printStep(arr, val):
print("Step {} = ".format(val), end='')
print(arr)
data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original:", data)
# Original: [5, 3, 8, 4, 9, 1, 6, 2, 7]
insertion_sort(data)
# Step 1 = [3, 5, 8, 4, 9, 1, 6, 2, 7]
# Step 2 = [3, 5, 8, 4, 9, 1, 6, 2, 7]
# Step 3 = [3, 4, 5, 8, 9, 1, 6, 2, 7]
# Step 4 = [3, 4, 5, 8, 9, 1, 6, 2, 7]
# Step 5 = [1, 3, 4, 5, 8, 9, 6, 2, 7]
# Step 6 = [1, 3, 4, 5, 6, 8, 9, 2, 7]
# Step 7 = [1, 2, 3, 4, 5, 6, 8, 9, 7]
# Step 8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print("Selection:", data)
# Selection: [1, 2, 3, 4, 5, 6, 7, 8, 9]
버블 정렬
- 인접한 2개의 레코드를 비교하여 순서대로가 아니면 서로 교환
- 비교-교환 과정을 리스트의 전체에 수행
- 끝으로 이동한 레코드를 제외하고 다시 스캔 반복
- 시간 복잡도: O(n²)
def bubble_sort(A): # 버블 정렬
n = len(A)
for i in range(n-1, 0, -1):
bChanged = False
for j in range(i):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
bChanged = True
if not bChanged:
break
printStep(A, n-i)
def printStep(arr, val):
print("Step {} = ".format(val), end='')
print(arr)
data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original:", data)
# Original: [5, 3, 8, 4, 9, 1, 6, 2, 7]
bubble_sort(data)
# Step 1 = [3, 5, 4, 8, 1, 6, 2, 7, 9]
# Step 2 = [3, 4, 5, 1, 6, 2, 7, 8, 9]
# Step 3 = [3, 4, 1, 5, 2, 6, 7, 8, 9]
# Step 4 = [3, 1, 4, 2, 5, 6, 7, 8, 9]
# Step 5 = [1, 3, 2, 4, 5, 6, 7, 8, 9]
# Step 6 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print("Selection:", data)
# Selection: [1, 2, 3, 4, 5, 6, 7, 8, 9]
탐색이란?
- 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업
- 맵
- 탐색을 위한 자료구조
- 키를 가진 레코드(엔트리)의 집합
- 엔트리
- 키: 레코드를 구분할 수 있는 탐색키
- 값: 탐색키와 관련된 값
맵 ADT
- 데이터: 키를 가진 엔트리의 집합
- 연산
- search(key): 탐색키 key를 가진 레코드를 찾아 반환
- insert(entry): 주어진 entry를 맵에 삽입
- delete(key): 탐색키 key를 가진 레코드를 찾아 삭제
탐색 알고리즘 종류
순차 탐색
- 정렬되지 않은 배열에도 적용 가능
- 처음부터 마지막까지 하나씩 검사
- 시간 복잡도: O(n)
class Entry:
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return str("{}:{}".format(self.key, self.value))
def sequential_search(A, key, low, high): # 순차 탐색
for i in range(low, high+1):
if A[i].key == key:
return i
return None
이진 탐색
- 정렬된 배열에 적용 가능
- 찾고자 하는 항목이 배열의 중앙에 있는 값을 기준으로 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄어가며 탐색
- 시간 복잡도: O(log n)
class Entry:
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return str("{}:{}".format(self.key, self.value))
def binary_search(A, key, low, high): # 이진 탐색
if low <= high:
middle = (low+high) // 2
if key == A[middle].key:
return middle
elif key < A[middle].key:
return binary_search(A, key, low, middle-1)
else:
return binary_search(A, key, middle+1, high)
return None
리스트를 이용한 순차 탐색 맵
class Entry:
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return str("{}:{}".format(self.key, self.value))
class SequentialMap: # 순차탐색 맵
def __init__(self):
self.table = [] # 맵의 레코드 테이블
def size(self): # 맵의 크기 반환
return len(self.table)
def display(self, msg): # 맵의 전체 레코드 출력
print(msg)
for entry in self.table:
print(" ", entry)
def insert(self, key, value): # 삽입 연산
self.table.append(Entry(key, value))
def search(self, key): # 순차탐색 연산
pos = sequential_search(self.table, key, 0, self.size()-1)
if pos is not None:
return self.table[pos]
else:
return None
def delete(self, key): # 삭제 연산
for i in range(self.size()):
if self.table[i].key == key:
self.table.pop(i)
return
해싱이란?
- 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산
- 해시 함수
- 키 값에 의해 데이터가 저장된 위치를 계산하는 함수
- 해시 테이블
- 해시 함수에 의해 계산된 위치에 데이터가 저장된 테이블
- 충돌
- 서로 다른 키가 해시 함수에 의해 같은 주소로 계산되는 상황
- 충돌을 일으키는 키를 '동의어'라고 함
- 오버플로
- 충돌에 의해 해당 주소에 더 이상 저장할 곳이 없는 상태
- 이상적인 해싱
- 충돌이 일어나지 않음
- 해시 테이블의 크기가 크면 메모리 낭비가 심함 → 해시 테이블의 크기를 적절히 줄이고 충돌이 발생할 경우 처리방법(선형 조사법, 이차 조사법, 이중 해싱법, 체이닝)을 대비
- 시간 복잡도
선형 조사법
- 충돌이 일어나면 해시 테이블의 다음 위치에 저장
- 순서대로 조사 → h(k), h(k) + 1, h(k) + 2, ...
- 빈 곳이 있으면 저장
- 탐색하려는 키가 해시 테이블에 있음에도 불구하고 빈 버킷에 의해 제대로 탐색되지 않는 경우 → 삭제 연산시 빈 버킷을 두 가지로 분류(한번도 사용 안 한 버킷, 삭제된 빈 버킷)
이차 조사법
- 선형 조사법의 경우 충돌이 발생한 위치에서 항목들이 집중되는 군집화 현상을 볼 수 있는데, 이차 조사법을 통해 이를 완화할 수 있음
- 충돌이 발생하면, 다음에 조사할 위치를 다음 식에 의해 결정 → (h(k) + i*i) % M for i = 0, 1, ... , M-1
- 조사 위치: h(key), h(key) + 1, h(key) + 4, h(key) + 9, ...
- 해시 함수 값이 같으면 다음 위치도 동일
이중 해싱법
- 재해싱
- 충돌이 발생하면, 다른 해시 함수를 이용해 다음 위치 계산
- 해시 함수 값이 같아도 키가 다르면 다른 위치 가능
체이닝
- 하나의 버킷에 여러 개의 레코드를 저장할 수 있도록 하는 방법
- 버킷은 연결 리스트로 구현
체이닝을 이용한 해시 맵
class Node: # 연결 리스트를 위한 노드
def __init__(self, item, link=None):
self.data = item
self.link = link
class Entry: # 노드의 데이터 부분에 저장
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return str("{}:{}".format(self.key, self.value))
class HashChainMap: # 해시 체인 맵
def __init__(self, M):
self.table = [None]*M # 크기가 M인 테이블을 만듦
self.M = M
def hashFn(self, key): # 해시 함수
sum = 0
# 문자열의 모든 문자에 대해 아스키 코드 값을 모두 더함
for c in key:
sum = sum + ord(c)
return sum % self.M
def display(self, msg): # 맵 출력
print(msg)
for idx in range(len(self.table)):
node = self.table[idx]
if node is not None:
print("[{}] -> ".format(idx), end='')
while node is not None: # None이 아닐 때까지
print(node.data, end=' -> ')
node = node.link
print()
def search(self, key): # 탐색 연산
idx = self.hashFn(key) # 해시 주소 계산
node = self.table[idx]
while node is not None: # None이 아닐 때까지
if node.data.key == key: # 탐색하고 있는 레코드를 찾음
return node.data
node = node.link
return None
def insert(self, key, value): # 삽입 연산
idx = self.hashFn(key) # 해시 주소 계산
self.table[idx] = Node(Entry(key, value), self.table[idx]) # 전단 삽입
def delete(self, key): # 삭제 연산
idx = self.hashFn(key) # 해시 주소 계산
node = self.table[idx]
before = None
while node is not None: # None이 아닐 때까지
if node.data.key == key: # 삭제할 레코드를 찾음
if before == None: # 첫 번째 항목 삭제
self.table[idx] = node.link
else: # 두 번째 이후 항목 삭제
before.link = node.link
before = node # before 갱신
node = node.link # node 갱신
