quicksort2 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. 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 다음