기본 정렬을 구현하고 백준 문제를 풀어서 익히자

selection

import numpy as np

n, c = map(int, input().split())
arr = np.random.choice(range(1, n), c, replace=False)

def selection_sort(arr):
    for idx in range(len(arr)):
        min_idx = idx
        for j, ele in enumerate(arr[idx+1:], start=idx+1):
            if arr[min_idx] > ele:
                min_idx = j
        arr[min_idx], arr[idx] = arr[idx], arr[min_idx]

print(*arr, sep=' ')
selection_sort(arr)
print(*arr, sep=' ')

insertion

거의 정렬이 완료된 배열의 경우, 정말 빠르다. 내장된 sorted보다 빠를 수 있다.

import numpy as np

n, c = map(int, input().split())
arr = np.random.choice(range(1, n), c, replace=False)

def insertion_sort(arr):
    for i, target in enumerate(arr[1:], start=1):
        for j in range(i-1, -1, -1):
            if target < arr[j]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            else:
                break

print(*arr, sep=' ')
insertion_sort(arr)
print(*arr, sep=' ')

quick

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    
    left = [ele for ele in arr[1:] if pivot >= ele]
    right = [ele for ele in arr[1:] if pivot < ele]
    
    return quick_sort(left) + [pivot] + quick_sort(right)

arr = [3,2,654,234,4563,23,12,3]
print(*arr, sep=' ')
print(*quick_sort(arr), sep=' ')

import numpy as np

n, c = 8, 4
arr = [1, 2, 5, 3]
arr = [7,3,1,5]
# n, c = map(int, input().split())
# arr = np.random.choice(range(1, n), c, replace=False)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]    
    left, right = 1, len(arr) - 1
    while True:
        while left <= len(arr)-1 and pivot > arr[left]:
            left += 1
        while right > 0 and pivot < arr[right]:
            right -= 1
        
        if left > right:
            arr[right], arr[0] = arr[0], arr[right]
            break
        else:
            arr[left], arr[right] = arr[right], arr[left]
            left, right = left + 1, right - 1
    
    return quick_sort(arr[:right]) + [pivot] + quick_sort(arr[left:])

print(*arr, sep=' ')
arr = quick_sort(arr)
print(*arr, sep=' ')

index

bitwise로 하는 것과 유사한 느낌

구현할 필요는 없어서 넘어간다.

백준