퀵정렬

퀵정렬이란???

• 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
• 전체리스트를 2개의 부분 리스트로 분할하고, 각가의 부분 리스트를 다시 퀵정렬하는 전형적인 분할정복법을 사용
• 퀵 정렬은 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않으므로 제자리 정렬이다.
• 두 개의 부분 리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나므로 불안정정렬 알고리즘이기도 하다.

분할정복법이란???

Divide and Conquer

• 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다.
• 대표적인 예시로는 퀵정렬과 병합정렬이 있다.
  

퀵정렬 방법

주어진 배열에서 하나의 요소를 선택하고 이를 피벗으로 둔다.
배열 내부의 모든 값을 검사하면서 Low와 High가 순회하여 피벗 값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치한다.
이렇게 하면 배열이 두 부분으로 나뉜다. 나뉜 이 두 개의 배열에서 각각 새로운 피벗을 만들어서 두개의 배열로 다시 쪼갠다.
더 이상 배열을 쪼갤 수 없을 때까지 진행한다.
이 과정은 분할 정복의 원리를 이용한 것이다. 피벗을 중심으로 문제를 분할 하고, 피벗을 기준으로 해서 작은 값과 큰 값을 나열하는 정복 과정을 거친 뒤, 모든 결과를 결합 해서 큰 전체 문제를 해결한다.