Sort Algorithms: Bubble Sort, Selection Sort, Insertion Sort in Python

너무 헷갈리고 어려워서 정리. 특히 Linked List 버전으로 작성하기 까다로웠음

1. Bubble Sort

1.1. List

# 오른쪽 엘리먼트랑 비교해서 내가 더 크면 쭉쭉 오른쪽꺼랑 swap해줌
# 점점 큰 엘리먼트를 오른쪽에 먼저 보낸다는 게 버블같다는 의미에서 Bubble sort
def bubble_sort(list):
    for i in range(len(list) - 1, 0, -1):
        for j in range(i):
            if list[j] > list[j + 1]:
                temp = list[j]
                list[j] = list[j + 1]
                list[j + 1] = temp
    return list


my_list = [3, 1, 5, 2, 4]
print(bubble_sort(my_list))

1.2. Linked List

def bubble_sort(self):
    if self.length <= 1: return False
    
    sorted_until = None 
    
    while sorted_until != self.head.next:
        curr = self.head 
        
        while curr.next != sorted_until:
            next_node = curr.next 
            if next_node.value < curr.value:
                next_node.value, curr.value = curr.value, next_node.value 
            curr = curr.next 
        sorted_until = curr

 

2. Selection Sort

2.1. List

 

# i 돌면서, i 다음 인덱스들을 j로 돌며 제일 작은 값의 인덱스를 업뎃해줌
# 인덱스 업뎃하고 나면 i인덱스의 값이랑 비교해서 작을 때 i 인덱스의 값이랑 바꿈
# min_index를 골라잡아서 바꾼다는 의미로 selection sort인가 싶음
def selection_sort(list):
    for i in range(len(list) - 1):
        min_index = i
        for j in range(i + 1, len(list)):
            if list[j] < list[min_index]:
                min_index = j
        if i != min_index:
            temp = list[min_index]
            list[min_index] = list[i]
            list[i] = temp
    return list


my_list = [5, 1, 8, 23, 6]
print(selection_sort(my_list))

2.2. Linked List

def selection_sort(self):
    if self.length < 2: 
        return
    #     sort curr temp
    # 1 -> 3 -> 8 -> 4

    curr = self.head
    while curr.next:
        min_node = curr
        temp = curr.next
        while temp:
            if temp.value < min_node.value:
                min_node = temp
            temp = temp.next
        if curr != min_node:
            curr.value, min_node.value = min_node.value, curr.value

        curr = curr.next

 

3. Insertion Sort

3.1. List

# bubble sort랑 비슷한데, 버블은 for문 두개로 돌면서 swap한다면
# 이건 왼쪽이랑 비교해서 필요한 때만 오른쪽 index로 땡겨주는 개념인 것 같음.
# 따라서 베스트 케이스에는 O(N) time complexity가 소요됨
# i인덱스 값을 temp로 빼 놨다가, 오른쪽 인덱스 값들을 필요한 만큼 다 옮기고 나서 빈자리에 넣어준다는 의미에서 insertion sort 같음

def insertion_sort(list):
    for i in range(1, len(list)):
        temp = list[i]
        j = i - 1
        while list[j] > temp and j > -1:
            list[j + 1] = list[j]  # 서로 바꾼다기보단 옆으로 한 칸 간다는 의미에서.
            list[j] = temp
            j -= 1
    return list


my_list = [4, 5, 1, 13, 6, 9]
print(insertion_sort(my_list))

3.2. Linked List

def insertion_sort(self):
    if self.length < 2:
        return
    #sort temp     curr   
    #head         -> 2 -> 7
    # 1 -> 3 -> 5 
    sorted_head = self.head
    unsorted_head = self.head.next
    sorted_head.next = None # 끊음
    
    while unsorted_head:
        curr = unsorted_head 
        unsorted_head = unsorted_head.next
        
        if sorted_head.value > curr.value:
            curr.next = sorted_head
            sorted_head = curr
        else:
            search_pointer = sorted_head
            while search_pointer.next and search_pointer.next.value < curr.value:
                search_pointer = search_pointer.next
            curr.next = search_pointer.next
            search_pointer.next = curr
    
    self.head = sorted_head
    temp = self.head 
    while temp.next:
        temp = temp.next 
    self.tail = temp