quick sort (1) 썸네일형 리스트형 [자료구조] Quick Sort 개념 및 Java로 구현하기 퀵 정렬 (Quick Sort) :분할 정복 (Divide and Conquer)방식을 이용한 알고리즘. pivot point 라는 기준점을 설정하여 왼쪽은 이 값보다 작은 값, 큰 값은 오른쪽으로 옮기면서 정렬을 진행, 따라서, 분할과 동시에 정렬을 진행하는 알고리즘이다. 보통 pivot을 맨 앞이나 맨 뒤, 혹은 중간에 위치한 값을 선택거나 전체 배열 값 중 중간값, 랜덤값으로 설정한다. 각 정렬은 배열의 크기 N만큼 비교하고, 이를 총 분할 깊이인 logN 만큼 실행한다. 즉, O(NlogN)의 시간 복잡도를 가진다. 이미 배열이 정렬이 되어 있는 경우(pivot이 항상 그 배열의 최솟값 혹은 최대값인 경우)는 최악의 시간 복잡도를 나타낸다. `(unbalanced-partition)` 이 경우에는.. 이전 1 다음