본문 바로가기

알고리즘 이론/정렬5

합병/병합 정렬(merge sort) 분할 정복 알고리즘의 대표적인 예 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. * 시간 복잡도 : O(n log n) (= O(n) (각 단계의 노드 길이) * O(log n) (단계의 깊이)) - 문제에서 데이터 개수가 최대 1,000,000개, 제한 시간 2초 이내라면 시간 복잡도가 위와 같은 O(n logn)의 정렬 알고리즘을 이용해야 함 (2^10 = 약 1,000이므로 n=1,000,000일 때, n logn = 20,000,000이고, 파이썬에서는 1초에 2천~5천만 번의 연산이 가능하므로 제한에 걸리지 않는다(간신히 통과할 수도 있음)) de.. 2020. 10. 1.
퀵 정렬(quick sort) 분할 정복 알고리즘의 대표적인 예 1. 보통 리스트의 첫 번째 원소를 기준점(pivot)으로 한다 2. pivot보다 작은 데이터는 left 리스트, 큰 데이터는 right 리스트에 더한다 3. left 리스트 + [pivot] + right 리스트를 리턴한다 3-1. left, right 리스트는 재귀용법을 사용해서 위 작업을 반복한다 4. 리스트의 길이가 1이면 해당 리스트를 반환한다 * 시간복잡도 O(n logn) / 최악의 경우 O(n^2) import random def quick_sort(data): if len(data) 2020. 9. 29.
삽입 정렬(insertion sort) 삽입 정렬(insertion sort) 1. 두 번째 인덱스부터 시작한다 2. 인덱스 앞의 데이터들과 비교한다 2-1. 앞의 데이터가 해당 인덱스의 데이터보다 작으면 둘의 위치를 바꾼다 3. 위 과정을 다음 나머지 값에서 반복한다 * 시간복잡도 : O(N^2) - 최선의 시간 복잡도: O(N) import random # set up def insertion_sort1(data): for x in range(len(data) - 1): for y in range(x + 1, 0, -1): if data[y] < data[y - 1]: data[y - 1], data[y] = data[y], data[y - 1] else: break return data def insertion_sort2(data): f.. 2020. 9. 28.
선택 정렬(selection sort) 1. 주어진 데이터 중에서 최솟값을 찾는다 2. 맨 앞의 데이터와 찾은 최솟값의 위치를 바꾼다 3. 위 과정을 다음 나머지 값에서 반복한다 * 시간복잡도 : O(n^2) import random # set up def selection_sort(data): for x in range(len(data)-1): lowest = x for y in range(lowest+1, len(data)): if data[lowest] > data[y]: lowest = y data[lowest], data[x] = data[x], data[lowest] return data # given data = random.sample(range(30), 5) # when print(selection_sort(data)) # t.. 2020. 9. 28.

티스토리툴바