에르미타쥬 에르미타쥬

지금까지 배워온 정렬은 두 수의 대소를 '비교'하는 과정을 거쳐 정렬하는 comparison sort였습니다. 두 수를 반복적으로 비교해 정렬하는 comparison sort는 아무리 알고리즘을 잘 짜도 계산 복잡성이 O(nlogn)보다 큽니다. 예를 들어서 퀵 정렬(quick sort)의 계산 복잡성이 O(n^2)이고, 힙 정렬(heap sort)이 O(nlogn)이라는 점을 감안하면 이 같은 내용이 들어맞음을 확인할 수 있습니다. 하지만 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추려는 알고리즘입니다. - counting sort 예를 들어, 다음과 같은 input array에 대해 counting sort를 수행한다면, inp..

삽입 정렬(Insertion Sort) 123456789def insertionSort(x): for size in range(1,len(x)): val = x[size] i = size while i > 0 and x[i-1] > val: x[i] = x[i-1] i-= 1 x[i] = val return xcs버블 정렬(Bubble Sort)123456def bubbleSort(x): for size in reversed(range(len(x))): for i in range(size): if x[i] > x[i+1]: x[i], x[i+1] = x[i+1], x[i] return xColored by Color Scriptercs선택 정렬(Selection Sort)123456789def selec..