Kim-Baek 개발자 이야기

Heap Sort는 Heap 이라는 자료구조를 이용해 정렬을 하는 알고리즘이다. Heap 이란 완전 이진 트리 형태로 Paren Node 는 Child Node 보다 반드시 큰(작은) 값을 가진다. Heap Sort의 경우 항상 O( N log(N) ) 의 시간복잡도를 가진다. 우선 모든 원소를 최대(최소) Heap에 삽입한다.( O(logN) ) Heap 트리의 최대(최소) 값을 출력한다.( O(1) ) 최대(최소) 값을 제거하고 Heap을 재배열 한다.( O(logN) ) Heap이 빌때가지 반복한다.( O(N) ) Stable 을 만족하지 않는다. #include #include #include using namespace std; int main() { vector v = { 3,1,4,1,5,9..

Quick Sort는 데이터내의 Pivot 값을 정하고 그 기준으로 두 개의 부분집합으로 나눈다. 한쪽은 Pivot보다 작은 값을 다른 한쪽은 Pivot보다 큰 값으로 나눈다. 더 이상 쪼갤 부분집합이 없을 때까지 재귀적으로 진행한다. Quick Sort는 어떤 Pivot 값을 고르는지에 따라 성능이 결정된다. 가장 이상적인 Pivot은 전체 데이터를 절반씩 쪼갤 수 있어야 한다. 이 경우 O(N log(n)) 의 복잡도를 가진다. 최악으 경우는 집합의 최소(최대) 값을 Pivot으로 고른 경우이다. 그러면 한쪽의 부분집합은 비어있고, 다른 한쪽은 n-1개의 원소가 있다(pivot 제외). 이 경우 재귀호출 횟수가 O(N)이며, 최악의 경우 O(N^2) 의 복잡도를 가진다. 하지만 평균적으로 O(N lo..

Insertion Sort는 단순한 정렬 알고리즘 중 하나이다. 한번의 한 원소씩 이미 정렬된 다른 원소들과 비교하여 올바른 위치에 삽입하는 정렬이다. 삽입 정렬은 이미 정렬되어 있을때 O(N) 의 효율이다.(Best Case) Average, Worse Case의 경우 O(N^2) 이다. Bubble Sort에서 발전된 형태이다.(비교 횟수를 줄였다) 소량의 데이터를 처리할때 좋다. Stable 하다 무작위로 정렬된 많은 데이터의 효율이 매우 안좋다. #include using namespace std; void insertion_sort(int data[], int size); int main() { int data[] = {3,7,9,4,5,1,3,4,6,9}; insertion_sort(data,..

알고리즘 문제에서 정렬(Sort)는 중요한 기술이다. 여러가지 정렬 알고리즘이 있지만 기본적인 것 부터 하나하나 알아보자. 선택 정렬 (Selection Sort) 단순한 정렬 알고리즘 중 하나이다. 배열의 첫 번째 원소에서 시작하여 배열 전체를 훓으면서 작은(큰) 값을 찾아 첫 번째 원소와 바꿔준다. 이 작업을 (배열의 길이 - 1 ) 만큼 진행한다. 선택 정렬은 Best, Average, Worst Case 모두 O(N^2) 의 효율이다 - 원소를 바꾸는 횟수가 최대 n -1 이다. 즉 원소를 바꾸는 과정에서 많은 비용이 드는 경우에 효율적일 수 있다. - 선택 정렬은 다른 알고리즘에 비해 효율(performance) 가 좋지 않다. - stable을 만족하지 않는다. #include using na..