반응형 퀵정렬1 [자료구조] 퀵 정렬(Quick Sort) 퀵 정렬이란 - 분할 정복 방법을 통해 주어진 배열을 정렬한다.(분할, 정복, 결합) 과정 1. 배열 가운데서 하나의 원소를 골라 피벗(pivot)이라고 정한다. 2. 피벗 앞에는 피벗보다 우선순위가 높은 원소들이 오고, 피벗 뒤에는 우선순위가 낮은 원소들이 오도록 분할 한다. 3. 이렇게 두구역으로 나눈뒤 해당 구역에서의 피벗을 정하여 이과정을 재귀적으로 반복한다. - 이미 정렬되어있는 리스트에서 가장 최악의 시간복잡도를 갖게된다. O(n^2) - 평균적인 시간복잡도 : O(nlog2n) # include # define MAX_SIZE 9 # define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) ) // 1. 피벗을 기준으로 2개의 부분 리스트로 나눈.. 2024. 1. 15. 이전 1 다음 반응형