[알고리즘] 분할 정복 알고리즘(Divide-and-Conquer) - 퀵 정렬(quick sort)
분할 정복에 대한 설명은 https://cuckoobird.tistory.com/153 을 참고해주세요. 퀵 정렬 퀵 정렬은 피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓습니다. 퀵 정렬은 분할된 부분문제들에 대해서도 위와 동일한 과정을 순환으로 수행하여 정렬합니다. 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않습니다. 피봇이 60이라면, 60은 [20, 40, 10, 30, 50] 과 [70, 90, 80] 사이에 위치하게 됩니다. 초기 배열이 { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 } 인 배열을 예시로 설명하겠습니다. 피봇을 중간에 있는 값으..
2023. 10. 6.
