Algorithm (13) 썸네일형 리스트형 007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(결론) 결론 위에서와 같이 여러 가지 사항들을 고려해봤을 때, 가장 이상적인 구현 방법은 아래와 같고, 소스 코드는 위 쪽에 있는 quickSort_recur_median 함수가 되겠다. 1) 2개의 인덱스를 이용해서 구현하고, 2) 기준점 위치는 가운데로 하고, 3) 난수에 의한 교환을 하지 않고, 4) 중윗값을 기준값으로 해서 정렬 Resource 위에서 설명한 퀵 정렬을 구현한 코드 및 이를 테스트하는 전체 소스 파일. 위 코드를 실행시켰을 대 생성되는 수행 속도에 대한 로그 파일 -끝- 007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(5) 5. 기준값으로 중윗값 사용 지금까지 결과를 보면, 그냥 가운데 값을 기준값으로 해서 구현한 것이 제일 빠른 것으로 보인다. (인덱스 2개를 사용하고, 재귀 호출 사용하고, 난수 사용하지 않고) 그런데, 아주 특수한 데이터에 대해서는, 고정으로 가운데 값을 잡았을 때, O(n2)의 나쁜 성능이 나올 수도 있을 것이다. (가운데 값으로 잡히는 값이, 계속해서 최솟값 혹은 최댓값인 데이터) 이에 대한 대안으로, 난수를 이용해서 가운데 값을 계속해서 교환해가면서 정렬하는 것도 생각해볼 수 있으나 난수 생성에 의한 약간의 속도 저하를 감내해야 한다. 이보다 좀 더 좋은 방법은 중앙값을 잡고, 이 중앙값을 맨 가운데 위치에 넣고 정렬을 수행하는 것이다. /** 사용 인덱스 개수: 2개(양방향 증가) 재귀/스택 이.. 007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(4) 4. 스택을 사용한 비 재귀판 퀵 정렬 구현 너무 많은 재귀 호출에 의해 스택 오버플로가 염려될 때는, 재귀를 사용하지 않는 비 재귀형 퀵 정렬의 구현을 생각할 수 있다. 자체 스택을 가지고 구현된다. 아래 코드는 중앙을 기준값(pivot)으로 하는 코드를 스택을 이용하여 재귀 호출 없이 구현한 코드이다. /** 사용 인덱스 개수: 2개(양방향 증가) 재귀/스택 이용 : 스택 스택구현 방법 : vector pivot 결정 : 중앙값 */ void quickSort_stack_vectorInt_center(vector &v, int s, int e){ vector st((e-s+2)*2); int top = 0; st[++top] = e; st[++top] = s; while (top > 0) { int .. 007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(3) 3. 난수(Random)를 이용한 기준값(pivot) 선정 방법 바로 위에서 봤듯이, 기준값을 정할 때 난수를 이용하면 특수한 데이터에 대해서 기준값을 고정했을 때 발생하는 속도 저하 문제를 해결할 수 있다. 그러나, 이때 난수 생성을 위해 소모되는 약간의 속도 저하를 감수해야 한다. 아래 표는 가운데 값을 기준점으로 해서 구현한 것과, 난수를 이용해서 가운데 값을 변화시켜가면서 구현한 코드의 정렬 시간 비교이다. (500만 개 값에 대한 정렬) 그냥 가운데 값을 기준점으로 정했을 때가, 난수를 사용한 경우보다 좀 더 빠름을 알 수 있다. DataType/Algorithm stlSort quickSort_recur_center quickSort_recur_randomCenter ordered 1120 5.. 007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(2) 2. 기준점 위치 (오른 편? 중앙?) 위에서 1개 인덱스를 사용했을 때, 코딩은 간단해지나, 특수한 데이터에 대해 속도가 안 좋아짐을 살펴봤다. 따라서 인덱스 2개를 사용한 방법이 정석이라 할 수 있는데, 인덱스 2개를 사용할 때 기준값을 어디로 정하느냐도 생각해볼 만한 문제이다. 알고리즘 책에서 일반적으로 소개하는 기준값(pivot) 위치는 맨 오른쪽이다. 이렇게 구현한 코드는 아래와 같다. /** 사용 인덱스 개수: 2개(양방향 증가) 재귀/스택 이용 : 재귀 스택구현 방법 : N/A pivot 결정 : 후미값 */ void quickSort_recur_right(vector &v, int s, int e){ int p; //p:기준점이 들어갈 자리 if(s < e){ int i=s-1,j=e; w.. 007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(1) 퀵 정렬은 다른 정렬 방법보다 속도에 대한 가변성이 높다. 기본 아이디어는 어떤 값을 기준으로 해서 partition으로 나눈 후, 나눈 것에 대해서 계속 정렬해가는 것인데, 기준값 어떻게 잡느냐에 따라 수행 속도 차이가 많이 나고, 재귀 호출을 사용하는지 스택을 사용하는지에 따라서도 속도와 메모리 사용량이 달라진다. 이번 챕터에서는 이러한 여러 가지 사항들을 고려해가며 퀵 정렬을 구현해보고 서로 속도 비교를 해볼 것이다. 1) 인덱스 1개 이용한 구현 2) 기준점 위치 (오른 편? 중앙?) 3) 난수(Random)를 이용한 기준값(pivot) 선정 방법 4). 기준값으로 중윗값 사용 1. 인덱스 1개 이용한 구현 앞에서 소개한 퀵 정렬에 대한 소스 코드는, 모두 2개의 인덱스를 사용한 알고리즘을 구현한.. 006. 퀵 정렬(Quick Sort) 1. 알고리즘 설명 일반적으로 가장 많이 사용되는 정렬 방법이다. 지금까지 살펴봤던 정렬방법이(선택, 삽입, 거품) O(n2)의 성능을 보임에 반해, 퀵 정렬은 O(nlogn)의 성능을 보인다. ( O(nlogn) 성능을 보이는 정렬 방법으로는 퀵 정렬, 힙 정렬, 병합 정렬이 있다.) 알고리즘은 꽤 간단하다. (처음 접할 때는 생소해서 어려울 수도 있으나, 좀 익숙해지면 꽤나 직관적이라는 것을 느끼게 된다.) 기본 아이디어는 이렇다. 1. 어떤 기준점 p를 중심으로해서 왼 편에는 p보다 작은 값을, 오른 편은 큰 값이 되게한다. 2. 왼편 블록에 대해서 1번과 같은 작업을 진행 --> 재귀 호출 3. 오른편 블록에 대해서 1번과 같은 작업을 진행 --> 재귀 호출 아래 애니메이션은 데이터의 가운데 값을.. 005. 거품 정렬(Bubble Sort) 1. 알고리즘 설명 성능이 가장 안 좋은 정렬방법이다. 제일 왼쪽의 (0,1) 2개를 비교를 해서 큰 수가 오른쪽으로 가게하고, 그다음 (1,2)에 대해서 비교 후 교환하고 하는 작업을 (n-2, n-1)까지 반복해서 작업한다. 이렇게 하면 n-1 번 째에 가장 큰 값이 들어가게 되고, 그다음에 다시 (0,1)부터 (n-3, n-2)까지 비교하는 작업을 해서 n-2 번 째를 결정하고, 이러한 과정을 반복해서 정렬하는 것이다. 아래 애니메이션은 거품 정렬에 의해 수가 정렬되는 모습이다.(출처: wekipedia) 2. 알고리즘 Flow 1. i=n-1 2. i=0이면 끝낸다. 3. j=0 4. j=i가 되면 7로 간다. 5. if(v[j] > v[j+1])이 두 수를 바꾼다. 6. ++j하고 4로 간다. .. 004. 이진 삽입 정렬(Binary Insertion Sort) 1. 알고리즘 설명 삽입 정렬을 개선한 알고리즘이다. 삽입 정렬의 경우, i를 증가시키면서 왼편 정렬되어 있는 곳에서 v[i]가 들어갈 곳을 찾아서 집어넣는 작업을 해나가는데, 이때 '정렬되어 있는 곳에서 찾는' 작업을 이진 검색(binary search)로 해서 빠르게 찾는 것이다. 또한, 들어갈 곳을 만들기 위해 값들을 오른쪽으로 한 칸씩 이동시키는데, 이 작업을 하나씩 이동시키는 것이 아니라 블록 전체를 오른쪽으로 한 칸 이동시키면(move 함수 이용), 이론적으로는 교환에 O(n2)이지만 실제 move를 이용한 블록 이동을 하면 O(n)의 효과를 볼 수 있다. 개선 1. 순차 검색에 의해 '비교'에 대한 시간 복잡도 O(n2) --> 이진 검색으로 O(nlogn))으로 개선 개선 2. 값 1개씩 .. 003. 삽입 정렬(Insertion Sort) 1. 알고리즘 설명 왼쪽에서 오른쪽으로 정렬해 나가는데, 대상이 되는 i 번째 수에 대해, 이미 정렬되어 있는 왼편의 어디에 삽입하면 되는지를 찾아서 집어넣고, i를 증가시키면서 오른편 끝까지 정렬해 나간다. 아래는 삽입 정렬이 이루어지는 에니메이션이다. (출처: wikipedia) 2. 알고리즘 Flow 1. i=1 2. j=i 3. j>0 이고 (v[j-1] > v[i])인 동안 3.1 v[j] = v[j-1] //v[i]가 들어갈 공간을 만든다. (오른쪽으로 쉬프트) 3.2 --j 4. v[j] = v[i] //만들어진 공간에 v[i]를 넣음 5. ++i하고 2로 돌아간다. 3. 소스 코드 void insertionSort(vector &v){ int size = v.size(); for(int i.. 이전 1 2 다음
