퀵 정렬 썸네일형 리스트형 [정렬 알고리즘] 퀵 소트(Quick Sort) 퀵 소트는 이름 그대로 빠른 성능을 제공하는 정렬 알고리즘입니다.평균적으로 O(n log n)으로, 최악의 경우 O(n2)의 시간 복잡도를 보입니다.기본적인 방식은 아래와 같습니다. 리스트에서 원소를 한 개 선택하는데 이 원소를 피벗(Pivot)이라고 부릅니다. 피벗이 선정되면 피벗보다 작은 값들은 피벗의 좌측에, 큰 값들은 우측에 위치시킵니다. 피벗은 자신의 자리를 찾았으므로 고정되며 좌우의 작은 값들과 큰 값들을 다시 재귀로 반복합니다. 이런 식으로 피벗의 위치를 전부 찾아주게 되면 결과적으로 정렬된 리스트가 됩니다.피벗은 다양한 방법으로 선택이 가능한데 보통 가장 앞의 원소나 가장 뒤의 원소를 선택해서 진행합니다.다음 코드는 가장 뒤의 원소를 피벗으로 선택하는 퀵 소트 코드입니다. #include .. 더보기 이전 1 다음