반응형 퀵소트1 퀵 정렬(Quick Sort) Quick Sort는 진짜 혼신의 힘을 다해서 정리할 것이다. 얘는 대학원 면접 단골 문제는 물론 지금까지 최고라고 또, 앞으로도 최고일거라는 호평을 받은 정렬 알고리즘이다. 퀵 소트는 분할과 정복으로 이루어진 알고리즘 중 하나이다. 따라서 매우 복잡하지만 성능만큼은 확실하다. ## Quick Sort process 1. 배열 a[l:r]에서 가장 오른쪽에 있는 원소를 pivot 이라고 선정한다. 피봇은 분할 원소이다. 2. 이 피봇을 기준으로 두개의 partition으로 분할한다. 그리고 이 파티션은 다음과 같은 성질을 따른다. - 분할 후 피봇은 a[i]로 들어가게 되는데, 이는 정렬 후 피봇이 들어가는 정확한 위치가 된다(즉, 정렬이 된다) - 왼쪽 파티션에 있는 원소 a[l] , ... a[i-1.. 2021. 10. 23. 이전 1 다음 반응형
