hahahia

Heap(힙) 이라는 자료구조를 이용해 정렬을 하는 알고리즘입니다.일반적으로 버블정렬, 삽입정렬, 선택정렬은 O(n^2)의 시간복잡도 이지만힙정렬은 힙의 구조상 시간복잡도가 O(nlogn)으로 상대적으로 효율적인 알고리즘입니다. n^2 시간복잡도의 sort 알고리즘에 비해서 좀 구현이 까다로울 수 있지만 그래도 힙의 구조를 이해하면 쉽게 구현하실 수 있을꺼같아요. 아 그리고.... 힙소트는 힙이라는 자료구조를 만들어둔 상태에서 소트를 하는 알고리즘이기 때문에입력을 받을때부터 Insert함수에서 힙으로 만들어줍니다.이 밑에 있는 요상한 것이 바로 힙(Heap)이라는 건데요. 구조적으로 바이너리 트리를 만족하고,현재 노드v의 원소의 value는 노드v의 left, right(즉 자식이겠죠.)의 원소보다 va..

Selection Sort(선택 정렬)- n개의 원소들 중에서 첫 번째 값을 키로 하여 남은 데이터 중에서 최소 값을 선택하여 비교한 후, 선택한 값이 키 값보다 작으면 서로 교환, 그렇지 않으면 다음 값을 키로 하여 n-1만큼 반복 수행하는 정렬이다. ex) n=5, 8 3 4 9 7초기 : 8 3 4 9 7 1단계 : (3)(8 4 9 7) 2단계 : (3 4)(8 9 7) 3단계 : (3 4 7)(9 8) 4단계 : (3 4 7 8 9) /* selection.cpp */ #include using namespace std; void swap(int *, int *); int main() { int n, min; int arr[100]; cin >> n; for(int i=0; i> arr[i]; ..

분할정복 접근법을 이용한 merge sort 분할 : 정렬할 n개의 원소의 수열을 n/2개씩 두 개의 부분 수열로 분할한다. 정복 : 병합 정렬을 이용해서 재귀적으로 그 두 부분 수열을 정렬한다. 결합 : 정렬된 두 개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다. -> 여기서 정렬할 수열의 크기가 1이 되면 다 정렬된것이므로 더이상 재귀적 호출은 일어나지 않게됩니다. 병합을 위한 과정으로는 Merge(A,p,q,r)이 필요한데 여기서 A = 배열, p,q,r은 index입니다(p