quicksort (1) 썸네일형 리스트형 [Algorithm] Quick Sort (퀵정렬) 1. Quick Sort (퀵정렬) 퀵 정렬은 병합 정렬과 같은 divide and conquer 기반의 알고리즘이다. 정렬시에 한 요소를 pivot으로 지정하고 pivot을 기준으로 배열을 두 부분으로 나눈다. 이때 pivot을 선택하는 방법은 여러가지가 있다. 첫번째 요소를 pivot으로 지정한다. 마지막 요소를 pivot으로 지정한다. 랜덤하게 pivot을 지정한다. 중간에 위치한 요소를 pivot으로 지정한다. 퀵 정렬은 정렬 알고리즘 중 가장 빠른 알고리즘으로 알려져 있지만, 배열의 정렬 상태와 pivot 선택 방법에 따라 worst case에 O(N^2)의 시간 복잡도를 가질 수 있다. 퀵 정렬의 핵심은 pivot을 중심으로 partition을 나누는 과정이다. pivot으로 지정된 요소의 값.. 이전 1 다음