Algorithm

binary search

코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 # binary search(정렬을 전제로 함) def binary_search(a, l, r, x): # list a, find x # iterative while l x: # x가 더 작음 r = mid - 1 else: # x가 더 큼 l = mid + 1 return -1 # couldn't find def binary_search2(a, l, r, x): # recursive if l x: return binary_search2(a, l, mid - 1, x) else: return binary_search2(a, mid + 1, r, x) else: return -1 Co..

bubble sort(optimized)

최적화된 버블 소트 코드 1 2 3 4 5 6 7 8 9 10 11 def bubble_sort(a): # optimized n = len(a) for j in range(n): # 반복용 checked = False for i in range(0, n - 1): # 처음부터 끝까지 앞뒤 비교하며 자리 바꾸기 if a[i] > a[i + 1]: a[i], a[i + 1] = a[i + 1], a[i] checked = True if checked is False: # 모두 정렬되었으면 그냥 종료 break Colored by Color Scripter cs 버블 소트는 배열 처음부터 끝까지 앞뒤하고만 비교하며 정렬한다. 정렬된 경우는 swap이 일어나지 않기 때문에 bool로 체크해서 그 경우에는 정렬을..

quick sort (기본: 맨 끝을 pivot으로)

코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # quick (pivot은 끝 값) def quick_sort(a): quick_sort_sub(a, 0, len(a) - 1) def quick_sort_sub(a, start, end): # start, end 모두 포함 n = len(a) if end - start

merge sort

Divide and Conquer의 한 종류 merge sort의 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 # merge def merge_sort(a): n = len(a) if n