Algorithm

수업 중 퀵 정렬에 대해서는 꼭 알고있으면 좋다고 하셔서, 너무 잘 정리해두신 다른 분의 블로그를 보고 정리하며 예전에 배웠던 걸 떠올려봐야겠다. 퀵정렬? 퀵 정렬은 분할 정복 방법으로 주어진 배열을 정렬한다. * 분할 정복 방법? 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 정렬 과정 배열 가운데서 하나의 원소를 고르고, 이 원소를 피벗(pivot) 이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 큰 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 피벗을 기준으로 둘로 나누는 것을 분할(divide)이라고 한다. 분할을 마친 뒤에 피벗은 더이상 움직이지 않는다. 분할된 두개..