'The Influences of Caches on the Performance of Sorting '리뷰 O(nlogn) 정렬 알고리즘이 O(n)정렬 알고리즘보다 빠르다??1. Introduction:Cache miss penalty의 문제가 performance에 큰 영향을 미침 & instruction count를 최소화 하기 위한 알고리즘이 필요.ex) radix sort는 lowest instruction count가 있으나, poor cache performance로 인해 merge sort, quicksort에 비해 성능이 떨어진다.이 논문의 목적은 4개의 정렬 알고리즘: heapsort, mergesort, quicksort, radixsort 를 cache의 측면에서 개선(메모리 최적화를..

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차식으로 남는다. 따라..

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의 방법..