버블 정렬(Bubble Sort)
인접한 원소를 비교하여 자리를 교환하는 방식이다. 처음부터 마지막까지 원소를 비교하여 마지막에는 가장 큰 또는 작은 원소가 배치된다. 이를 정렬이 끝날때까지 수행하며 시간 복잡도는 O(n^2)이며 구현이 압도적으로 간단하다.
def bubble_sort(items: list):
for i in range(len(items) - 1):
for j in range((len(items) - 1) - i):
if items[j] < items[j+1]:
temp = items[j]
items[j] = items[j+1]
items[j+1] = temp
print(f'{i + 1} 회차 정렬 : {items}')
return items
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = bubble_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 40, 49, 65, 16, 43, 34, 77, 54, 3]
2 회차 정렬 : [100, 49, 65, 40, 43, 34, 77, 54, 16, 3]
3 회차 정렬 : [100, 65, 49, 43, 40, 77, 54, 34, 16, 3]
4 회차 정렬 : [100, 65, 49, 43, 77, 54, 40, 34, 16, 3]
5 회차 정렬 : [100, 65, 49, 77, 54, 43, 40, 34, 16, 3]
6 회차 정렬 : [100, 65, 77, 54, 49, 43, 40, 34, 16, 3]
7 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
8 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
9 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
선택 정렬(Selection Sort)
앞 원소부터 기준 위치로 지정하고 기준 위치에서 뒤쪽의 원소들과 크기를 비교하여 가장 큰 또는 작은 원소를 선택하여 교체하는 방식이다. 시간 복잡도는 O(n^2)이며 버블 정렬에 비해서 스왑이 일어나는 횟수가 비교적 적다.
def selection_sort(items: list):
for i in range(len(items) - 1):
selection = i
for j in range(i, len(items)):
if items[selection] < items[j]:
selection = j
temp = items[i]
items[i] = items[selection]
items[selection] = temp
print(f'{i + 1} 회차 정렬 : {items}')
return items
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = selection_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 3, 40, 49, 65, 16, 43, 34, 77, 54]
2 회차 정렬 : [100, 77, 40, 49, 65, 16, 43, 34, 3, 54]
3 회차 정렬 : [100, 77, 65, 49, 40, 16, 43, 34, 3, 54]
4 회차 정렬 : [100, 77, 65, 54, 40, 16, 43, 34, 3, 49]
5 회차 정렬 : [100, 77, 65, 54, 49, 16, 43, 34, 3, 40]
6 회차 정렬 : [100, 77, 65, 54, 49, 43, 16, 34, 3, 40]
7 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 3, 16]
8 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 3, 16]
9 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
삽입 정렬(Insertion Sort)
사람이 생각하는 정렬의 기본적인 모델로 적당한(?) 값 사이에 엘리먼트를 집어넣는다. 물론 그렇게 하기 위해서 n인 인덱스를 선택했다면 n-1까지 n 인덱스가 들어 갈 수 있도록 공간을 마련해야 한다. 아래 소스코드는 이론을 토대로 작성된 코드라 틀린 부분이 있을 수 있다.
def insertion_sort(items: list):
for i in range(1, len(items)):
if items[i] > items[i-1]:
for j in range(i, 0, -1):
if items[j] > items[j-1]:
temp = items[j]
items[j] = items[j-1]
items[j-1] = temp
continue
break
print(f'{i + 1} 회차 정렬 : {items}')
return items
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = insertion_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 3, 40, 49, 65, 16, 43, 34, 77, 54]
2 회차 정렬 : [100, 40, 3, 49, 65, 16, 43, 34, 77, 54]
3 회차 정렬 : [100, 49, 40, 3, 65, 16, 43, 34, 77, 54]
4 회차 정렬 : [100, 65, 49, 40, 3, 16, 43, 34, 77, 54]
5 회차 정렬 : [100, 65, 49, 40, 16, 3, 43, 34, 77, 54]
6 회차 정렬 : [100, 65, 49, 43, 40, 16, 3, 34, 77, 54]
7 회차 정렬 : [100, 65, 49, 43, 40, 34, 16, 3, 77, 54]
8 회차 정렬 : [100, 77, 65, 49, 43, 40, 34, 16, 3, 54]
9 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
병합 정렬(Merge Sort)
추후 추가할 예정
힙 정렬(Heap Sort)
값을 힙에 삽입하고 삭제 연산을 반복해서 정렬하는 방법이다. 실제로는 원본 배열에서 정렬을 실시하여 추가 메모리를 사용하지 않는 것이 정석인 것으로 보인다. 여기서는 리스트를 분리했지만 최대한 추가 메모리를 사용하지 않는 방향으로 작성하였다. 히프는 정렬을 할 수 있을 정도의 수준으로만 구현하였다.
class Heap:
def __init__(self):
self.array = []
def __str__(self):
return str(self.array)
def swap_array(self, x: int, y: int):
temp = self.array[x]
self.array[x] = self.array[y]
self.array[y] = temp
def insert_element(self, value: int):
self.array.append(value)
if len(self.array) > 1:
node_num = len(self.array) - 1
while node_num != 0:
next_node_num = int(node_num / 2)
if self.array[next_node_num] < self.array[node_num]:
self.swap_array(node_num, next_node_num)
else:
break
node_num = int(node_num/2)
def delete_root(self):
root_value = self.array[0]
del self.array[0]
last_index = len(self.array) - 1
if last_index < 0:
return root_value
tail_value = self.array[last_index]
del self.array[last_index]
self.array.insert(0, tail_value)
now_index = 0
next_index = 0
while True:
now_index = next_index
next_index *= 2
if next_index + 2 > last_index:
break
if self.array[next_index + 1] > self.array[next_index + 2]:
next_index += 1
else:
next_index += 2
if self.array[now_index] < self.array[next_index]:
self.swap_array(now_index, next_index)
return root_value
def heap_sort(items: list):
size = len(items)
heap = Heap()
for _ in range(size):
heap.insert_element(items.pop())
for i in range(size):
items.append(heap.delete_root())
print(f'{i} 원소 삭제 : {items}')
return items
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = heap_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
0 원소 삭제 : [100]
1 원소 삭제 : [100, 77]
2 원소 삭제 : [100, 77, 65]
3 원소 삭제 : [100, 77, 65, 54]
4 원소 삭제 : [100, 77, 65, 54, 49]
5 원소 삭제 : [100, 77, 65, 54, 49, 43]
6 원소 삭제 : [100, 77, 65, 54, 49, 43, 40]
7 원소 삭제 : [100, 77, 65, 54, 49, 43, 40, 34]
8 원소 삭제 : [100, 77, 65, 54, 49, 43, 40, 34, 16]
9 원소 삭제 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
퀵 정렬(Quick Sort)
피봇과 2개의 마커를 이용하여 정렬하는 방식이다. 피봇보다 큰 값을 찾는 L 마커와 피봇보다 작은 값을 찾는 R 마커가 존재하며 서로 원하는 값을 찾으면 마커끼리 값을 교환하고 R 마커와 L마커가 교차한 후 R 마커가 값을 찾으면 피봇과 값을 교환한다. R마커가 원하는 값을 찾지 못한 경우 이미 피벗은 정렬된 위치에 있는 것으로 간주한다.
def quick_sort(items):
pivot = 0
L = pivot + 1
R = len(items) - 1
while pivot != (len(items) - 1):
for i in range(R, pivot - 1, -1):
R = i
if items[R] < items[pivot]:
break
for i in range(L, R + 1):
L = i
if items[L] > items[pivot]:
break
if L < R:
temp = items[L]
items[L] = items[R]
items[R] = temp
print('마커간 교환 :', items)
continue
if R <= L and R > pivot:
temp = items[pivot]
items[pivot] = items[R]
items[R] = temp
print('피봇과 교환 :', items)
continue
if R <= pivot:
pivot += 1
L = pivot + 1
R = len(items) - 1
return items
if __name__=="__main__":
m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', m_list)
sort_list = quick_sort(m_list)
print('정렬 리스트 :', sort_list)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
피봇과 교환 : [3, 54, 40, 49, 65, 16, 43, 34, 77, 100]
피봇과 교환 : [3, 34, 40, 49, 65, 16, 43, 54, 77, 100]
피봇과 교환 : [3, 16, 40, 49, 65, 34, 43, 54, 77, 100]
마커간 교환 : [3, 16, 40, 34, 65, 49, 43, 54, 77, 100]
피봇과 교환 : [3, 16, 34, 40, 65, 49, 43, 54, 77, 100]
피봇과 교환 : [3, 16, 34, 40, 54, 49, 43, 65, 77, 100]
피봇과 교환 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
기수 정렬(Radix Sort)
기수 정렬은 각 원소끼리 비교하지 않고 각 원소의 자릿수에 맞게 배열에 저장했다가 다시 합치는 방식을 반복하여 정렬한다. 원소들의 자릿수가 적을때 용이한 정렬법이다. 아래 소스코드는 이론을 토대로 작성된 코드라 틀린 부분이 있을 수 있다.
def radix_sort(items: list):
# 끝자리부터 비교
pointer = -1
# 최댓값의 길이
max_len = max(map(lambda x: len(str(x)), items))
for i in range(max_len):
bukkit = [[] for __ in range(10) ]
for item in items:
radix = 0
try:
radix = int(str(item)[pointer])
except IndexError:
pass
bukkit[radix].append(item)
items = []
for x in range(10):
for y in range(len(bukkit[x])):
items.append(bukkit[x][y])
pointer -= 1
print(f'{i + 1} 회차 정렬 : {items}')
return items
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = radix_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 40, 3, 43, 34, 54, 65, 16, 77, 49]
2 회차 정렬 : [100, 3, 16, 34, 40, 43, 49, 54, 65, 77]
3 회차 정렬 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
트리 정렬(Tree Sort)
값 들을 이진 탐색 트리에 삽입하고 이진 탐색 트리를 중위 순회하면 정렬이 된다. 이진 탐색 트리는 정렬을 할 수 있을 정도의 수준으로만 구현하였다.
class Node:
def __init__(self, value: int):
self.value = value
self.right = None
self.left = None
def __str__(self):
return str(self.value)
class SearchTree:
def __init__(self):
self.root = None
self.inorder_list = []
def insert_element(self, value: int):
new_node = Node(value)
if self.root == None:
self.root = new_node
node = self.root
while True:
pre_node = node
if node.value > new_node.value:
node = node.left
if node == None:
node = new_node
pre_node.left = node
elif node.value < new_node.value:
node = node.right
if node == None:
node = new_node
pre_node.right = node
else:
return
def inorder_traversal(self, node=None, is_recursive=False):
if not is_recursive:
self.inorder_list = []
if not node:
node = self.root
if not node.left == None : self.inorder_traversal(node.left, True)
self.inorder_list.append(node.value)
if not node.right == None : self.inorder_traversal(node.right, True)
if not is_recursive:
return self.inorder_list
def tree_sort(items: list):
search_tree = SearchTree()
for _ in range(len(items)):
search_tree.insert_element(items.pop())
return search_tree.inorder_traversal()
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = tree_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 삽입 순회 : [3]
2 삽입 순회 : [3, 100]
3 삽입 순회 : [3, 40, 100]
4 삽입 순회 : [3, 40, 49, 100]
5 삽입 순회 : [3, 40, 49, 65, 100]
6 삽입 순회 : [3, 16, 40, 49, 65, 100]
7 삽입 순회 : [3, 16, 40, 43, 49, 65, 100]
8 삽입 순회 : [3, 16, 34, 40, 43, 49, 65, 100]
9 삽입 순회 : [3, 16, 34, 40, 43, 49, 65, 77, 100]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
유전 정렬(Genetic Sort)
랜덤으로 값을 정렬하는 보고정렬을 보고 만들어 본 정렬이다. 컴퓨팅 성능이나 유전자의 갯수, 변이율에 따라서 큰 속도차를 보일테지만 보고정렬보다 빠르게 정렬된다 뿐, 최악의 성능을 자랑한다.
import copy
import random
def evaluation(chromosome):
evaluation_value = 0
for i in range(len(chromosome) - 1):
if chromosome[i] <= chromosome[i + 1]:
evaluation_value += i + 1
return evaluation_value
def genetic_sort(items):
MAX_CHROMOSOME = 100
MUTATION = 0.35
chromosome = [random.sample(items, len(items)) for __ in range(MAX_CHROMOSOME)]
evaluation_value = [0 for __ in range(MAX_CHROMOSOME)]
selection_parents = [0, 0]
target_score = sum(range(len(items)))
while True:
for i in range(MAX_CHROMOSOME):
evaluation_value[i] = evaluation(chromosome[i])
max_value = 0
for i in range(MAX_CHROMOSOME):
if max_value < evaluation_value[i]:
max_value = evaluation_value[i]
selection_parents[1] = selection_parents[0]
selection_parents[0] = i
if target_score in evaluation_value:
break
evaluation_value = [0 for __ in range(MAX_CHROMOSOME)]
new_chromosome = []
for i in range(MAX_CHROMOSOME):
new_chromosome.append(copy.deepcopy(
chromosome[selection_parents[random.randint(0, 1)]]))
for j in range(len(items)):
if random.random() < MUTATION:
idx1 = random.randint(0, len(new_chromosome[i])-1)
idx2 = random.randint(0, len(new_chromosome[i])-1)
temp = new_chromosome[i][idx1]
new_chromosome[i][idx1] = new_chromosome[i][idx2]
new_chromosome[i][idx2] = temp
chromosome = copy.deepcopy(new_chromosome)
return chromosome[selection_parents[0]]
if __name__=="__main__":
items = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
print('원본 리스트 :', items)
sort_items = genetic_sort(items)
print('정렬 리스트 :', sort_items)
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
각 정렬의 성능
| Algorithm | Space Complexity | (average) Time Complexity | (worst) Time Complexity |
|---|---|---|---|
| Bubble sort | O(1) | O(n^2) | O(n^2) |
| Selection sort | O(1) | O(n^2) | O(n^2) |
| Insertion sort | O(1) | O(n^2) | O(n^2) |
| Merge sort | O(n) | O(nlogn) | O(nlogn) |
| Heap sort | O(1) | O(nlogn) | O(nlogn) |
| Quick sort | O(1) | O(nlogn) | O(n^2) |
| Radix sort | O(n) | O(n) | O(n) |
Ghost