정렬 알고리즘 및 자료구조 구현

정렬 알고리즘

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())

 

총평

면접시 손코딩을 대비해서 기본적인 정렬 알고리즘과 자료구조 구현을 연습해보았습니다.
정렬 알고리즘에 어떤 것들이 있는지는 잘 알고 있었지만, 각각의 알고리즘이 어떤식으로 구현되어 있는지는 잘 알고 있지 못하고 있는 것을 발견했습니다.
그래서 하나씩 재밌게 구현해보았습니다.