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

퀵소트를 인플레이스로 구현해봤습니다. 퀵소트란 비교연산 기반의 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