algorithm
정렬 알고리즘 및 자료구조 구현
big whale
2024. 4. 11. 23:57
정렬 알고리즘
1. 버블 정렬
def bubbleSort1(arr):
for i in range(len(arr)):
for j in range(len(arr) - 1):
if arr[j] > arr[j + 1]:
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
def bubbleSort2(arr):
idx = 0
temp = 0
while idx < len(arr):
for i in range(len(arr) - 1):
if arr[i + 1] < arr[i]:
temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
idx += 1
arr = [3, 1, 5, 2, 4]
bubbleSort2(arr)
print(arr)
2. 삽입 정렬
def insertSort(arr):
for i in range(1, len(arr)):
val = arr[i]
idx = i - 1
while idx >= 0 and arr[idx] > val:
arr[idx + 1] = arr[idx]
idx -= 1
arr[idx + 1] = val
arr = [3, 1, 2, 5, 2, 4, 2]
insertSort(arr)
print(arr)
3. 병합 정렬
def mergeSort(arr, st, en):
# 종료조건
if en - st < 1:
return
# 분할
mid = (st + en) // 2
mergeSort(arr, st, mid)
mergeSort(arr, mid + 1, en)
# 정복
merge(arr, st, mid, en)
def merge(arr, st, mid, en):
temp = []
p1 = st
p2 = mid + 1
while p1 <= mid and p2 <= en:
if arr[p1] <= arr[p2]:
temp.append(arr[p1])
p1 += 1
else:
temp.append(arr[p2])
p2 += 1
while p1 <= mid:
temp.append(arr[p1])
p1 += 1
while p2 <= en:
temp.append(arr[p2])
p2 += 1
for i in range(st, en + 1):
arr[i] = temp[i - st]
arr = [3, 1, 4, 2, 5, 3]
mergeSort(arr, 0, len(arr) - 1)
print(arr)
4. 퀵 정렬
def swap(arr, idx1, idx2):
temp = arr[idx1]
arr[idx1] = arr[idx2]
arr[idx2] = temp
def partition(arr, st, en):
p1, p2 = st + 1, en
while p1 < p2:
while arr[st] > arr[p1]:
p1 += 1
while arr[st] < arr[p2]:
p2 -= 1
if p1 < p2:
swap(arr, p1, p2)
swap(arr, st, p2)
return p2
def quickSort(arr, st, en):
if st >= en:
return
pivot = partition(arr, st, en)
quickSort(arr, st, pivot - 1)
quickSort(arr, pivot + 1, en)
arr = [3, 1, 4, 2, 5, 1]
quickSort(arr, 0, len(arr) - 1)
print(arr)
5. 선택 정렬
def swap(arr, i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
def selectSort(arr):
minIdx = 0
for i in range(len(arr)):
minIdx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIdx]:
minIdx = j
if i != minIdx:
swap(arr, i, minIdx)
arr = [3, 1, 44, 2, 9]
selectSort(arr)
print(arr)
6. 이진 탐색
def binarySearchSort(arr, num):
st, en = 0, len(arr) - 1
while st <= en:
mid = (st + en) // 2
val = arr[mid]
if val < num:
st = mid + 1
elif val > num:
en = mid - 1
else:
return mid
arr = [1, 4, 5, 7, 9]
num = 7
print(binarySearchSort(arr, num))자료구조
1. 스택
class StackNode:
def __init__(self, data = 0):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def pop(self):
if self.top == None:
return -1
temp, self.top = self.top.data, self.top.next
return temp
def push(self, data):
node = StackNode(data)
node.next = self.top
self.top = node
def peek(self):
if not self.top:
return -1
return self.top.data
def isEmpty(self):
return self.top == None
st = Stack()
arr = [3, 1, 45, 2, 56]
for num in arr:
st.push(num)
while not st.isEmpty():
print(st.peek(), st.pop())
2. 큐
class QueueNode:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.first = None
self.last = None
def add(self, data):
node = QueueNode(data)
if self.last:
self.last.next = node
self.last = node
if not self.first:
self.first = self.last
def remove(self):
if not self.first:
return -1
data = self.first.data
self.first = self.first.next
if not self.first:
self.last = None
return data
def peek(self):
if not self.first:
return -1
return self.first.data
def isEmpty(self):
return self.first == None
q = Queue()
arr = [3, 1, 45, 6, 2, 1]
for num in arr:
q.add(num)
while not q.isEmpty():
print(q.peek(), q.remove())
3. 힙
MAX_HEAP_SIZE = 200
class Heap:
def __init__(self):
self.heapSize = 0
self.heap = [0 for _ in range(MAX_HEAP_SIZE)]
def append(self, item):
self.heapSize += 1
idx = self.heapSize
# 부모가 더 작으면 위로 올라감.
while idx != 1 and item > self.heap[idx//2]:
self.heap[idx] = self.heap[idx//2]
idx //= 2
self.heap[idx] = item
def pop(self):
if self.heapSize == 0:
return -1
topNode = self.heap[1]
lastNode = self.heap[self.heapSize]
self.heapSize -= 1
parent = 1
child = 2
# 자식이 더 크면 밑으로 내려감.
while child <= self.heapSize:
# parent의 자식 중 더 큰 자식을 고른다.
if child < self.heapSize and (self.heap[child] < self.heap[child + 1]):
child += 1
# lastNode가 child와 같거나 크면 lastNode를 이 두 자식의 부모로 삼음.
if lastNode >= self.heap[child]:
break
# lastNode가 더 작으면 자식을 부모로 옮기고 다시 확인
self.heap[parent] = self.heap[child]
parent = child
child *= 2
self.heap[parent] = lastNode
return topNode
def isEmpty(self):
return self.heapSize == 0
arr = [3, 1, 4, 2, 9]
h = Heap()
for num in arr:
h.append(num)
while not h.isEmpty():
print(h.pop())
총평
면접시 손코딩을 대비해서 기본적인 정렬 알고리즘과 자료구조 구현을 연습해보았습니다.
정렬 알고리즘에 어떤 것들이 있는지는 잘 알고 있었지만, 각각의 알고리즘이 어떤식으로 구현되어 있는지는 잘 알고 있지 못하고 있는 것을 발견했습니다.
그래서 하나씩 재밌게 구현해보았습니다.