Algorithm

insertion sort 이해해보기

아래는 insertion sort의 코드이다 1 2 3 4 5 6 7 8 9 10 #insertion sort def insertion_sort(a): n = len(a) for i in range(1, n): key = a[i] j = i - 1 while j >= 0 and a[j] > key: # key가 더 작으면 앞으로 a[j + 1] = a[j] j -= 1 a[j + 1] = key cs selection sort가 어떤 위치에 들어갈 value를 뒤의 것들을 쭉 훑은 뒤에 '뽑아서' 가져오는 것이라고 한다면 insertion sort는 어떤 위치의 것을 그 앞 어디에 '넣을' 것인지 정하는 것이다. 위치를 정해야하는 value의 위치 i. value를 key에 저장하고 앞의 값들(위치 j)..

selection sort

내가 구현한 방법과 정식 알고리즘을 비교해보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 # selection def selection_sort_not_good(a): # 이 방법은 swap을 원래 방법보다 많이 하게 된다. 또한 insertion에 가까운 방법이다. n = len(a) for i in range(0, n - 1): for j in range(i + 1, n): if a[j] a[j]: # i 뒤의 애들을 전부 흝고 그 중 하나를 골라서 swap min_idx = j a[i], a[min_idx] = a[min_idx], a[i] # swap Colored by Color Scripter cs 원래의 방법은 기준이 되는 것 뒤의 애들을 한번 다 ..