Sorting2 Sorting (2) - 정렬 알고리즘 구현하기 (Shell, Merge, Quick) (with.Python) Shell Sort (셸 정렬) 주어진 간격(일반적으로 k)만큼 떨어진 서브배열을 만들어 삽입정렬을 수행한다. 시간복잡도는 평균적으로 O(n log n), 최고 O(n), 최악의 경우 O(n^2)의 시간복잡도를 가지고 있다. 간격에 따른 성능이 제각각이라 시간복잡도 분석이 쉽지 않다. 간격은 홀수로 지정하여, 간격이 절반으로 줄어들 때 짝수가 나오면 +1을 하여 홀수로 만든다. def gapInsertionSort(x, start, gap): for target in range(start+gap, len(x), gap): val = x[target] i = target while i > start: if x[i-gap] > val: x[i] = x[i-gap] else: break i -= gap x[i.. 2021. 6. 28. Sorting (1) - 정렬 알고리즘 구현하기 (Bubble, Selection, Insertion) (with.Python) Bubble Sort (버블정렬) 인접한 두 원소를 검사하여 큰 값이 오른쪽으로 이동하는 과정을 반복하여, 비교했던 모든 값들의 최댓값을 맨 오른쪽으로 옮긴다. 시간복잡도가 최악의 경우 (Big O) O(n^2)로 (n-1) + (n-2) + ··· + 1번 비교가 이루어진다. 그러나, 데이터가 잘 정렬되어 있다면 O(n)으로 데이터 정렬 여부를 파악하기 위한 알고리즘으로 사용될 수 있다. def swap(x, i, j): x[i], x[j] = x[j], x[i] def bubbleSort(x): for size in reversed(range(len(x))): for i in range(size): if x[i] > x[i+1]: swap(x, i, i+1) return x if __name__ ==.. 2021. 6. 28. 이전 1 다음
