목록2017/04/28 (2)
개인공부용123 프로그래밍 블로그
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. 먼저 임의의 피벗을 잡고 맨오른쪽 위치로 보냄 (저는 중간..