정렬3 Quicksort from CTCI 코딩 인터뷰 완전 분석(원제: Cracking the Coding Interview)에 소개된 Quicksort를 다시 한 번 정리 해보려고 한다. 기본적으로 퀵정렬은, 무작위로 한 원소를 정하고(이를 pivot이라 부른다), pivot보다 작은 원소들은 앞쪽에, 큰 원소들은 뒷쪽에 위치시킨다. 실행시간: 평균 O(n logn), 최악 O(n^2).메모리: O(logn)배열 분할(partition)에 사용되는 원소(pivot)가 배열의 중간값(median) 혹은 중간값에 가까운 값이라면 좋은 성능이 나오겠지만, 반드시 그러리라는 보장은 할 수 없다. 즉 퀵정렬은 pivot을 어떻게 정하느냐에 따라 느리게 동작할 수도 있으며, 최악의 경우 수행시간이 O(n^2)이 될 수 있다. 이전에 작성했던 퀵정렬(Ho.. 2019. 3. 2. Counting Sort (계수 정렬) Counting Sort(계수 정렬)에서 주목할 만한 점은, 이전까지 살펴봤던 다른 정렬 알고리즘들은 특정한 data type에 대한 가정을 따로 세우지 않았다. 하지만 지금 살펴 볼 Counting Sort는 정렬할 data의 type에 대한 가정을 세우고 시작한다. 무슨 말일까? 먼저 Counting Sort가 어떻게 동작하는지 몇 가지 사항을 간단히 살펴보자. 정렬할 data의 type에 대한 가정을 세운다.값들 끼리의 비교가 없다. 정렬이 끝날 때까지, 비교는 한 번도 이루어지지 않는다. — 대부분의 정렬 알고리즘은 요소 사이의 비교를 필요로 하고(comparison-based), O(NlogN) 이상의 성능을 기대할 수 없다. Counting Sort는 비교 대신 추가적인 배열을 이용하여, 시간.. 2018. 4. 7. Quick Sort (퀵 정렬) 퀵정렬은 임의의 한 요소(pivot이라 칭함)를 정한 뒤, pivot의 왼쪽에는 pivot보다 작은 것들만, 오른쪽에는 pivot보다 큰 것들만 오게 만드는 Divide & Conquer 알고리즘이다. Quick Sort 내부에서 divide, 즉 partition하는 과정에 있어 크게 두 가지 접근법이 있다.1) Hoare's Partition Scheme2) Lomuto's Partition Scheme 먼저 Hoare's Partition Scheme에 대해 살펴보자.전체 과정을 정리해 보면 다음과 같다. 특히 Partition 과정을 집중적으로 보도록 하자, 1. 배열의 첫 인덱스를 start로, 길이를 end로 하여 quickSort()를 호출한다. end는 배열의 마지막 index가 아닌 배열.. 2018. 4. 6. 이전 1 다음