개인공부용123 프로그래밍 블로그

FixHeapFast를 사용해서 HeapSort를 구현해봤습니다. 각 함수별 기능 설명 swap함수 : 두 배열의 원소를 바꿔주는 함수입니다. parent, left_child, right_child는 각각 부모 , 왼쪽 자식, 오른쪽 자식노드를 찾아주는 함수입니다.(없어도 무방합니다.) FixHeapFast 함수 : 이 함수는 down Heap을 실행하는 함수로 시작노드에 있는함수를 있어야할 위치까지 내리는 함수입니다. 단 이떄 FixHeapFast함수는 promote함수를 이용해서 높이의 절반 만큼씩 내려가게 됩니다. 그리고 vacant가 잘못 내려갔을경우 BubbleUpHeap함수를 이용해서 있어야할 위치로 올려줍니다. Promote 함수 : vacant를 높이의 절반만큼 내리는 함수입니다. (한칸..

MergeSort를 구현했습니다. 각 함수별 기능 설명 Merge : 분할된 두 부분을 합쳐주는 기능을합니다. MergeSort : 분할 정복을 이용해서 각각 Sort를 실행하는 함수입니다. 위 사진과 같이 분할 정복을 통해서 머지소트가 실행됩니다. Worst Case time Complexity 머지소트의 최악수행시간의 점화식은 W(n) = W(n/2) + W(n/2) + W(merge)(n)입니다. 이를 Master theorem을 이용해서 점화식을 풀면 O(nlogn)이라는 최악수행시간이 나옵니다. 즉 MergeSort의 최악수행시간 = O(nlogn) #include #include using namespace std; void Merge(vector& arr,int start, int mid, ..

퀵소트를 인플레이스로 구현해봤습니다. 퀵소트란 비교연산 기반의 Sorting으로서 Randomized Sorting알고리즘이고 또한 분할 정복이기도합니다. 퀵소트에는 주요한 원소가있는데 Pivot이라는 원소입니다.이 원소는 퀵소트를 수행시 소팅의 기준이 된다고 할수있는 원소입니다. 퀵소트를 정렬시 피벗의 왼쪽에는 피벗보다 작은값 오른쪽에는 피벗보다 크거나 같은값들로 정렬합니다. L은 피벗의 왼쪽 리스트 : 피벗보다 작은 원소들의 집합P는 피벗(원소)R은 피벗의 오른쪽 리스트 : 피벗보다 크거나 같은 원소들의 집합 InplacePartion을 실행하면 L P R 이런식으로 정렬이 되게됩니다. 제 코드에서 Inplace_Partion의 수행방식은1. 먼저 임의의 피벗을 잡고 맨오른쪽 위치로 보냄 (저는 중간..

백준 2751번 문제도 풀고 HeapSort도 구현해보기위해서 HeapSort를 구현해서 백준 2751 문제를 풀었습니다. 각 함수별 기능 설명 swap함수 : 두 배열의 원소를 바꿔주는 함수입니다. parent, left_child, right_child는 각각 부모 , 왼쪽 자식, 오른쪽 자식노드를 찾아주는 함수입니다.(없어도 무방합니다.) FixHeap 함수 : 이 함수는 down Heap을 실행하는 함수로 시작노드에 있는함수를 있어야할 위치까지 내리는 함수입니다. consturctHeap 함수 : 이 함수는 주어진 배열을 Heap으로 만들어주는 함수입니다. (아래 코드의경우엔 MaxHeap입니다.) HeapSort 함수 : Heap의 Root에 있는 노드를 배열 끝에 넣고 FixHeap시키는 함수..

구현방식 * 배열이 sorting되있지 않을시 sort를 시켜야함 (sorting된 data structure를 대상으로 하는 알고리즘)1. 시작 인덱스와 마지막 인덱스의 중간지점( (시작 인덱스 + 마지막 인덱스) / 2 ) 을 잡는다.2. 찾으려는 Key값과 비교해서 탐색범위를 1/2로 줄인다.3. 위와 같은 방법을 찾으려는 키값을 찾을때까지 재귀적으로 반복한다. #include using namespace std; // Edited by Survivalking 2017 03 25 int binarySearch(int e[], int first, int last, int K) { int index = 0; if (last < first) { cout K; cout