데이터 분석 기술 블로그

주어진 배열을 두 개로 분할하고 각각을 정렬합니다.병합 정렬과 다른 점은 병합 정렬은 그냥 두 부분으로 나누는 반면에, 퀵 정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킵니다.또, 각 부분 정렬이 끝난 후, 병합 정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요로 하지 않습니다.

1. 분할 정복 알고리즘설계 전분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눕니다.정복(Conquer) : 나눈 작은 문제를 각각 해결합니다.통합(Combine) : (필요하다면) 해결된 해답을 모읍니다.2. 퀵 정렬주어진 배열을 두 개로 분할하고, 각각을 정렬합니다.합병정렬과 비슷다른 점 1 : 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것 오른편에 위치시킵니다.다른 점 2 : 각 부분 정렬이 끝난 후, 합병정렬은 "합병"이란 후처리 작업이 필요하나, 퀵정렬은 필요로 하지 않습니다. 퀵정렬의 최악의 시간 복잡도는 O(n2)로, 합병정렬에 비해 좋지 못합니다.그런데, 왜 "빠른" 정렬이라고..