10000COW

계수 정렬 : 주어진 배열의 값의 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다. 우선, 이해하기 쉽게 nums = [5, 9, 3, 6, 9, 5, 2, 10, 1] 이라는 배열이 입력되었고, 이 nums 배열을 정렬한다고 해보자. 카운팅 정렬의 단계 0. 정렬할 nums 배열 입력 1. count 배열 생성 - 입력된 nums 배열의 최댓값을 길이로 갖는 count 배열을 생성한다. - 각 원소가 nums 배열에 몇 번 나오는지 횟수를 count 배열에 기록한다. 2. 이전까지의 누적개수를 기록하는 배열 생성(cumCount 배열) - count 배열에서 각 원소가 몇 개씩 나오는지 알 수 있으므로, - 이를 이용..

기수 정렬 : 주어진 수 들간의 비교를 하지 않고 버킷을 사용해 정렬하는 방법으로, 낮은 자리(1의 자리)에서 높은 자리(10^n 자리) 순으로 버킷에 넣는 방법으로 정렬한다. 실제로 숫자들 간의 비교를 통해 정렬을 하는 것이 아닌, 0~9까지의 버킷이 있고 이 버킷에 숫자를 넣어가며 분류한다고 생각하면 된다. 시간복잡도 O(r*n) : r은 숫자의 자릿수, n은 정렬될 수의 갯수 특징 1. 시간 복잡도에서 엄청난 이점을 갖는다. 무려 O(N).. 2. 하지만 그만큼 추가적인 메모리가 많이 필요하다. [153, 262, 37, 598, 433, 855]를 기수 정렬을 이용해 정렬해보자. 가장 낮은 1번째 자리부터(1의 자리) 가장 높은 3번째 자리(100의 자리) 순으로 정렬한다. 다음과 같이 0~9 까..

힙 정렬 : 기본 아이디어는 버블 정렬과 비슷하다. 1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내며 정렬한다. 버블 정렬과 다른 점은, 버블 정렬은 남은 원소에서 1등을 다시 비교를 통해 찾아야 하지만 힙 정렬은 힙(Heap)을 이용하면, 1등을 뽑아낸 뒤, 나머지 원소에서 1등을 뽑을 때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다. 그럼, 힙(Heap)에 대해 잠깐 알아보자. 힙의 성질 1. 리프 노드를 제외한 모든 노드는 자식이 반드시 2명 2. Max heap: 부모는 자식보다 반드시 크다. Min heap: 부모는 자식보다 반드시 작다. 힙의 삽입과 삭제 (출처: https://guides.codepath.com/compsci/Heaps) 자, 이제 힙 정렬에 대해 본격적으로 들어..

퀵 정렬 : 특정 기준 원소를 중심으로, 기준 원소보다 작은 것들은 기준의 왼쪽으로, 기준 원소보다 큰 것들을 기준의 오른쪽으로 정렬 + 재귀적으로 분할 정복 기법 사용. 가장 널리 쓰이는 정렬 알고리즘이기도 하다. 핵심 원리를 쉽게 이해할 수 있는 Python 코드 def quicksort(L): if(len(L) == 1) or (len(L) == 0): return L pivot = L[0] left = [] right = [] for x in L[1:]: if (x < pivot): left.append(x) else: right.append(x) return quicksort(left) + [pivot] + quicksort(right) 위의 코드는 기준 점을 주어진 배열의 0번째 인덱스, 즉 ..

선택 정렬: 총 n개의 원소가 있을 때, 0번째 원소부터 n-1 번째 원소까지 i 번째 원소부터 마지막 원소까지 최소값을 갖는 원소와 i 번째 원소를 swap해주는 정렬. 버블 정렬과 달리 한 Cycle 내에서 한 번만 swap(교환)이 일어난다. 시간복잡도: Θ(n^2) 선택 정렬 선택 정렬 Python 코드 def selectionSort(): nums = list(map(int, input().split(' '))) for i in range(0, len(nums)): min_num = nums[i] min_idx = i for j in range(i+1, len(nums)): if(nums[j] < min_num): min_num = nums[j] min_idx = j nums[min_idx] =..