pivot1 [C++] 퀵 정렬 (Quick Sort) 이번 시간에는 퀵 정렬에 대해 알아보도록 하겠다. 저번 시간까지 배웠던 선택 정렬, 버블 정렬, 삽입 정렬 모두 시간 복잡도가 O(n ^ 2)였다. 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 필요하고, 대표적인 빠른 알고리즘이 퀵 정렬로, O(N * logN)의 시간 복잡도를 가진다. 퀵 정렬(Quick Sort)는 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 일반적으로 퀵 정렬에서는 기준값이 있고, 이를 피벗(pivot)이라고 하는데, 보통 첫 번째 원소를 피벗 값으로.. 2020. 5. 6. 이전 1 다음