정렬 알고리즘5 - 퀵정렬(Quick Sort)

퀵정렬(Quick Sort)

출처- 위키백과

작동방식

• 정렬할 피봇(기준값)을 정하고, 피봇을 기준으로 크기가 큰 그룹과 작은 그룹으로 나눈다.
• 나뉜 각 그룹에서 다시 피봇을 정하고, 피봇 기준으로 크기가 큰 그룹과 작은 그룹으로 나눈다.
• 그룹을 더이상 나눌 수 없을때까지 위 과정을 반복한다.

 

특징

• 명칭에서 알 수 있듯이 빠른 정렬 방법이다
• 분할 정복 알고리즘의 한 기법
• 퀵 정렬은 부분교환 정렬(Partition Exchange Sort)이라고도 불림.
• 요소간 비교하는 방식으로 정렬되는 방식
• 그룹 나누는 함수를 재호출 하는 즉, 재귀적으로 호출하는 방식이다.
• 임의의 피봇(기준값을 정한다.
• 꽤 빠른 정렬 방법에 해당한다.
• 그룹에서 어떤 요소를 피봇으로 정하는지에 따라 정렬의 성능이 결정된다.
• 데이터를 나열한 순서가 좋지 않으면 효율이 좋지 않을 수 있다(어느정도 정리되어야 큰 효과를 발휘함).