Written by Lee Jongseo
on May 13, 2021

Alogrithm[2]:⭐ - Bubble Sort, Selection Sort

Bubble sort

List가 주어여졌을 때, 왼쪽에 있는 숫자가 오른쪽에 있는 숫자보다 크다면 swap이 일어난다.

# swap
if a > b:
    a, b = b, a

# test
nums = [4,2,3,1]

for i in range(len(nums)-1):
    if nums[i] > nums[i+1]:
        # swap
        nums[i], nums[i+1] = nums[i+1], nums[i] 

이러한 순회가 리스트의 길이 - 1 만큼 일어나야 전체가 정렬된다.

def bubblesort(nums):
    for i in reversed(range(len(nums) - 1)):
        for j in range(i):
        if nums[j] > nums[j+1]:
            # swap
            nums[j], nums[j+1] = nums[j+1], nums[j]             

Selection sort

주어진 리스트에서 최솟값을 찾는 것이 핵심

Find index of minimum value

test = [4,3,1,2]
min_idx = 0
for i in range(len(test)):
    if test[i] < test[min_idx]:
        min_idx = i
print(min_idx) # 2

최솟값을 찾은 다음에 계속해서 맨 앞과 자리를 스왑한다.

def selection_sort(nums):
    for i in range(len(nums) - 1):
        min_idx = i
        for j in range(i, len(nums)):
            if nums[j] < nums[min_idx]:
                min_idx = j
        # swap
        nums[i], nums[min_idx] = nums[min_idx], nums[i]

👈 👉 Top