8. 퀵정렬
알고리즘 공부
2019. 9. 27.
퀵정렬 찰스 앤터니 리처드 호어가 1959년에 개발한 알고리즘이다. 퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다. C, C++, PHP, 자바 등 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다. 방식은 적절한 원소 하나를 기준(피봇, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피봇을 옮겨 피봇보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 피봇을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다. 이렇게 피봇을 잡고 이보다 작은 원소들을 왼쪽으로, 보다 큰 원소들을 오른쪽으로 나누는걸 partition step이라 한다. 퀵 정렬에도 이..
