Selection Sort(선택정렬) Inplace 정렬 알고리즘 중 하나(추가 메모리 필요X) n번째 index에 n번째로 작은 원소를 삽입한다. 알고리즘: 각 루프 마다: 최대 원소를 찾는다. 최대 원소를 가장 오른쪽의 원소와 교환한다. 1~2 를 반복하는데 1 에서 찾고 옮긴 원소를 제외하고 반복한다. 시간복잡도 및 의사코드: //n은 배열 A의 크기 cost times for j=1 ~ j=n-1 n smallest=j n-1 for i=j+1 ~ i=n Σ(n-j+1) if A[i] tj는 j=2,3,⋯,n=2,3,⋯,인 경우에 대해 while루프의 검사가 실행되는 횟수 따라서, BestCase: 이미 정렬 된 경우 while문의 실행되지 않으므로 위의 식에서 n에 대해 1차식으로 남는다. 따라..

MergeSort(병합정렬) 분할정복(devide and conquer)이라는 알고리즘 설계 패러다임을 이용한 대표적인 알고리즘이다. 즉, 어떤 문제(problems)를 재귀적으로 분할해 나가서 subproblems(부분문제?)들을 이용해 문제를 해결하고 다시 합치는 개념이다. 다음 사진에서 빨간부분이 분할단계, 초록부분이 합치는 단계이다. 분할을 해서 값을 비교하여 정렬하고 다시 합치는 로직이다. 알고리즘 정렬할 데이터의 크기가 0 또는 1이면 이미 정렬 된 것으로 본다. (사진에서 회색부분) 크기가 2 이상이면 반으로 쪼갠다. 1~2반복...(빨간색 부분) 원래 같은 집합에서 나온 데이터 집합 둘을 합치는데 정렬 순서를 맞춰서 합친다.(초록색 부분) 4 반복 시간복잡도 병합정렬을 재귀식으로 나타내면 ..

Worst-Case Linear-Time Selection 앞의 포스팅에서 분석한 바에 따르면 최상의 경우가 되기 위해 pivot을 고르는 방법은 언제나 n개의 배열의 원소가 있다면 그 중 $\frac{n}{2} $번째로 큰(혹은 작은) 원소를 pivot으로 정하는 것이었다. 2023.06.30 - [CS(Computer Science)/Algorithm] - QuickSort(2)-알고리즘03 QuickSort(2)-알고리즘03 Worst Case Partitioning 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라진다. 즉 퀵 정렬에서 pivot을 기준으로 분할을 할 때, pivot이 무엇이냐에 따라 연산횟수 loftspace.tistory.com 이 pivot..

Worst Case Partitioning 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라진다. 즉 퀵 정렬에서 pivot을 기준으로 분할을 할 때, pivot이 무엇이냐에 따라 연산횟수가 달라진다. 연산횟수를 최대로 만드는 pivot은 무엇일까? 일단 퀵 정렬의 시간복잡도는 T(n)= T(q) + T(n-q-1) + O(n) 이었다. 여기서 q가 n-1이라면 T(n)= T(n-1) + T(1) + O(n) = T(n-2) + T(1) + O(n-1) + T(1) + O(n) =... 이다. 한마디로 배열을 n-1개짜리와 1개짜리 로 분할을 하는 pivot을 선택하는 것이 퀵정렬에서의 최악의 경우이다. 따라서 T(n)=O(n^2) 인데 이를 증명하자. 재귀트리를 이용..

퀵정렬 많은 정렬 알고리즘 중에 퀵정렬을 다뤄본다. 퀵정렬을 공부하다보면 얻게 되는 것이 많다. Divide and Conquer(분할정복) , Pivot , Partition 에 대한 개념을 같이 공부하게 된다. 퀵 정렬은 다음과 같은 과정으로 정렬을 한다. (Input=array:ARR[0]) 1. 배열의 원소중 하나를 골르는데 이를 pivot이라고 한다. 2. pivot보다 큰 값의 원소들은 pivot의 오른쪽으로, pivot보다 작은 원소들은 pivot의 왼쪽으로 자리를 옮긴다 (partition) 3. pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 분할을 해서 각각의 배열에 대해 1,2의 과정을 반복한다. (Divide and Conquer) pivot을 정하는 방법과 partition의 방법..

재귀함수의 식을 예로 다음을 볼 수 있다. 이러한 재귀식은 알고리즘을 분석할 때, 특히 recursive algorithm을 분석 할때 많이 쓰인다 예를 들면 n!을 구하는 알고리즘의 T(n)은 어떻게 구할까? f(n)=n! 이라고 할때 f(n)=f(n-1)*n=f(n-2)*(n-1)*(n) .... 이다. f(n)의 연산횟수를 T(n)이라고 한다면 T(n) = T(n-1) + 1 (f(n-1)과 n의 곱셈) = T(n-2) + 1 (f(n-2)와f(n-1)의 곱셈) + 1 이므로 따라서 f(n) = O(n) 이다. 그렇다면 이런식은 어떻게 풀까? 이런 복잡한 식들을 푸는 방법 3가지를 오늘 알아보자. 1. Substitution Method 귀납적 풀이랑 비슷하다.(이산수학에서나오는 것과 똑같은 거 같..