첫 번째 반복문 루프는 데이터의 마지막이 자동으로 정렬되기 때문에 데이터의 수 -1로 정해준다.
최소값의 index를 저장할 수 있도록 변수를 선언해준다.
두 번째 반복문은 정렬된 인덱스 다음번부터 시작하면 된다.
차례대로 데이터 값을 비교하며 인덱스값을 알맞게 바꿔준다.
def selection_sort(data):
for index in range(len(data) - 1):
min_index = index
for index2 in range(index+1, len(data)): # index+1은 min_index와 index2를 비교할 때
if data[min_index] > data[index2]: # +1을 하지않으면 자기자신을 비교하여 불필요한 부분을 제거
min_index = index2
data[index], data[min_index] = data[min_index], data[index]
return data
두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘
버블정렬의 규칙찾기
n개의 리스트가 있는 경우 최대 n-1번의 로직이 적용된다.
로직을 1번 적용할 때 마다 가장 큰 숫자가 리스트의 가장마지막에 위치하므로 비교해야할 숫자가 하나씩 줄어들음
로직이 경우에 따라 일찍 끝날 수도 있다. 로직을 적용할 때 데이터의 교환이 한번도 일어나지 않으면 이미 정렬된 상태이므로 더 이상 로직을 반복할 필요가 없다.
버블 정렬(Bubble Sort) 알고리즘 구현
def bubble_sort(data):
swap = False
for index in range(len(data) - 1):
for index2 in range(len(data) - index - 1):
if data[index2] > data[index2 + 1]:
data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
swap = True
if swap == False:
break
return data
Insert를 구현할 때에는 조건문을 먼저 타는것이 아니라 데이터를 삽입한 후에 조건문을 이용하여 데이터를 한칸씩 상위노드로 올리는 작업을 해야한다. 최대 힙구조에서는 부모노드가 자식노드보다 작으면 안되기 때문에 삽입되어진 데이터가 부모노드보다 큰지 비교를하여 삽입된 데이터가 더 크다면 서로의 위치를 바꾸어 주는 과정을 반복한다.
Delete 구현
보통 삭제는 Root Node를 삭제한다.(힙의 용도는 최대값, 최소값을 Root Node에 놓아 바로 꺼내 쓸 수 있도록함)
Root Node 삭제시 가장 하단부 왼쪽에 위치한 Node를 Root Node로 이동
Root Node의 값이 Child Node보다 작을 경우 Root Node의 Child Node중 가장 큰 값을 가진 노드와 위치를 바꿔주는 작업을 함
# 반복문을 실행하는 조건함수
def move_down(self, root_idx):
left_child_idx = root_idx * 2
right_child_idx = root_idx * 2 + 1
# 왼쪽 자식 노드도 없을 때
if left_child_idx > len(self.heap_array):
return False
# 오른쪽 자식 노드만 없을 때
elif right_child_idx >= len(self.heap_array):
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
return True # Root Node가 자식노드보다 작기때문에 반복문을 돌아야한다.
else:
return False
# 자식이 둘 다 있을 때
else:
if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
return True
else:
return False
else:
if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
return True
else:
return False
def pop(self):
if len(self.heap_array) <= 1:
return None
returned_data = self.heap_array[1]
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
root_idx = 1
while move_down(root_idx):
left_child_idx = root_idx * 2
right_child_idx = root_idx * 2 + 1
# 오른쪽 자식 노드만 없을 때
if right_child_idx >= len(self.heap_array):
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]
root_idx = left_child_idx
# 자식이 둘 다 있을 때
else:
if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]
root_idx = left_child_idx
else:
if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
self.heap_array[root_idx], self.heap_array[right_child_idx] = self.heap_array[right_child_idx], self.heap_array[root_idx]
root_idx = right_child_idx
return returned_data
Delete를 구현할 때는 루트노드를 삭제하고 가장 뒤에있는 노드를 끌어올린 이후 부터 조건에 맞게 노드들을 이동시킨다.
데이터를 아래로 이동시키면 세가지 경우가 생긴다.
1. 자식노드가 존재하지 않을때
2. 부모노드아래에 왼쪽자식노드만 존재할 때
3. 자식노드가 둘 다 존재할 때
1번 경우는 자식노드가 없으니 더이상 내려갈 곳이 없어 아무런 행동을 취하지 않아도 된다.
2번경우는 자식노드가 부모노드보다 더 크다면 서로의 위치를 바꾸어 주어야한다.
3번경우는 자식노드 둘을 비교하여 둘중에 더 큰 노드를 부모노드와 비교하여 부모노드보다 더 크다면 위치를 바꿔준다.
이러한 과정을 조건이 맞을 때 까지 반복해준다.
전체 코드
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(None) # 0번 자리를 None으로 초기화하여 1번부터 시작
self.heap_array.append(data)
# 반복문을 실행하는 조건함수
def move_up(self, inserted_idx):
if inserted_idx <= 1:
return False
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
return True
else:
return False
def insert(self, data):
if len(self.heap_array) == 0:
self.heap_array.append(None)
self.heap_array.append(data)
return True
self.heap_array.append(data)
inserted_idx = len(self.heap_array[-1])
while move_up(inserted_idx):
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
inserted_idx = parent_idx
return True
# 반복문을 실행하는 조건함수
def move_down(self, root_idx):
left_child_idx = root_idx * 2
right_child_idx = root_idx * 2 + 1
# 왼쪽 자식 노드도 없을 때
if left_child_idx > len(self.heap_array):
return False
# 오른쪽 자식 노드만 없을 때
elif right_child_idx >= len(self.heap_array):
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
return True # Root Node가 자식노드보다 작기때문에 반복문을 돌아야한다.
else:
return False
# 자식이 둘 다 있을 때
else:
if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
return True
else:
return False
else:
if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
return True
else:
return False
def pop(self):
if len(self.heap_array) <= 1:
return None
returned_data = self.heap_array[1]
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
root_idx = 1
while move_down(root_idx):
left_child_idx = root_idx * 2
right_child_idx = root_idx * 2 + 1
# 오른쪽 자식 노드만 없을 때
if right_child_idx >= len(self.heap_array):
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]
root_idx = left_child_idx
# 자식이 둘 다 있을 때
else:
if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
if self.heap_array[root_idx] < self.heap_array[left_child_idx]:
self.heap_array[root_idx], self.heap_array[left_child_idx] = self.heap_array[left_child_idx], self.heap_array[root_idx]
root_idx = left_child_idx
else:
if self.heap_array[root_idx] < self.heap_array[right_child.idx]:
self.heap_array[root_idx], self.heap_array[right_child_idx] = self.heap_array[right_child_idx], self.heap_array[root_idx]
root_idx = right_child_idx
return returned_data
class Node:
def __init__(self, value):
self.value = value
self.right = None
self.left = None
이진 탐색 트리 구현
class BST(self, value):
def __init__(self, head):
self.head = head
Insert 구현
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
Search 구현
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
Delete 구현
# 삭제 할 값을 탐색
def delete(self, value):
searched = False
self.current_node = self.head
self.parent = self.head
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
if searched == False:
return False
Case1: Child Node가 없는 노드 삭제
# self.current_node가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
# Leaf Node삭제(Child Node가 없는 노드 삭제)
if self.current_node.left == None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
del self.current_node
Case2: Child Node가 한개 있는 노드 삭제
# 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
# Child Node가 자신보다 작을 때
if self.current_node.left != None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
# Child Node가 자신보다 클 때
if self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
Case3: Child Node가 두개 있는 노드 삭제
# 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
if self.current_node.left != None and self.current_node.right != None:
# 삭제할 Node가 Parent Node보다 작을 경우
if value < self.parent.value:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_parent = self.change_node
self.change_node = self.change_node.left
# 가장 작은 값을 가진 Node의 Child Node가 있을 때
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
# 삭제할 Node가 Parent Node보다 클 경우
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
# 가장 작은 값을 가진 Node의 Child Node가 있을 때
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.current_node.left
전체 코드
class Node:
def __init__(self, value):
self.value = value
self.right = None
self.left = None
class BST(self, value):
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
def delete(self, value):
searched = False
self.current_node = self.head
self.parent = self.head
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
if searched == False:
return False
# Leaf Node삭제(Child Node가 없는 노드 삭제)
if self.current_node.left == None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
del self.current_node
# 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
# Child Node가 자신보다 작을 때
if self.current_node.left != None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
# Child Node가 자신보다 클 때
if self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
# 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
if self.current_node.left != None and self.current_node.right != None:
# 삭제할 Node가 Parent Node보다 작을 경우
if value < self.parent.value:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
# 삭제할 Node가 Parent Node보다 클 경우
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.current_node.left
Close Hashing 기법 중 하나, 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
충돌이 일어나면 해당 hash address의 다음 address부터 맨처음에 나오는 빈공간에 저장하는 기법
https://en.wikipedia.org/wiki/Linear_probing
Linear Probling 기법 구현
hash_table = list([0 for i in range(10)]) # 0부터 9까지의 리스트를 0으로 초기화
def get_key(data):
return hash(data)
def hash_function(key):
return key % 10
def save_data(data, value):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0: # 해시 주소값안에 데이터가 존재할 때
for index in range(hash_address, len(hash_table)): # 현재 주소값 테이블의 끝까지 반복문을 돌며
if hash_table[index] == 0: # 빈 공간을 찾으면 데이터를 저장
hash_table[index] = [index_key, value]
return
elif hash_table[index][0] == index_key
hash_table[index][1] = value # 해시 주소값 안의 key값과 index_key값이 동일하면 데이터를 수정
return
else:
hash_table[hash_address] = [index_key, value]
def read_data(data):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:
for index in range(hash_address, len(hash_table)): # 해시 주소값 부터 테이블 끝까지 반복문을 돌며
if hash_table[index] == 0: # 해시 주소안의 키 값이 index_key와 동일한지 찾고
return None # 동일하다면 해당 value값을 반환
elif hash_table[index][0] == index_key:
return hash_table[index][1]
else:
return None
hash_table = list([0 for i in range(10)]) # 0부터 9까지의 리스트를 0으로 초기화
def get_key(data):
return hash(data)
def hash_function(key):
return key % 10
def save_data(data, value):
index_key = get_key(data)
hash_address = hash_function(index_key)
# 해시주소값에 데이터가 존재할 때
if hash_table[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
# 해당 해시 주소값의 key 값과 index_key가 같을 때 데이터를 덮어씀
if hash_table[index][0] == index_key:
hash_table[index][1] = value
return
# hash_address에 해당하는 key값과 index_key값이 일치하지 않으면 append해줌으로 데이터를 추가
hash_table[hash_address].append([index_key, value])
else:
hash_table[hash_address] = [[index_key, value]]
def read_data(data):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:
# hash_address에 해당하는 key값과 index_key가 일치하면 value를 반환해준다.
for index in range(len(hash_table[hash_address])):
if hash_table[hash_address][index][0] == index_key:
return hash_table[hash_address][index][1]
return None
else:
return None
