[정렬 알고리즘][파이썬] 퀵 정렬

퀵 정렬(quick sort)에서는 기준이 되는 수(pivot)를 수열 안에서 임의로 하나를 선택합니다. 그리고 피봇 이외의 수를 '피봇보다 작은 수'와 '피봇 이상인 수'의 두 그룹으로 나누고 이것을 다음과 같이 배치합니다. '피봇보다 작은 수' < 피봇 < '피봇 이상인 수' 그리고 양쪽 그룹을 또 다시 퀵 정렬을 사용해 나누고 이것을 계속 반복하면 자연스럽게 정렬이 이루어집니다. - 책 알고리즘 도감

 

 

위의 막대기들을 퀵 정렬을 사용해 오름차순으로 정렬해 보겠습니다.

 

 

1. pivot을 임의로 하나 선택합니다.

여기서는 40이 선택되었다고 가정하겠습니다.

 

 

 

 

 

2. pivot 이외의 각 숫자를 pivot과 비교해 갑니다. pivot보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽으로 이동합니다.

 

 

20 < 40 이므로 20을 왼쪽으로 보냅니다. 그리고 10, 30 < 40 이므로 10과 30도 왼쪽으로 보냅니다.

또한 50 > 40 이므로 50은 오른쪽으로 보냅니다.

 

 

3. pivot보다 작은 수들과 pivot보다 큰 수들을 가지고 지금까지의 단계들을 정렬이 완료될 때까지 반복합니다.

정렬 완료

 

 

[퀵 정렬 코드] [파이썬]

퀵 정렬은 pivot을 어떻게 정하느냐에 따라 효율이 많이 달라진다고 합니다.

하지만 복잡하다고 하네요..ㅠㅠ

그래서 여기서는 단순하게 첫 번째 값을 pivot으로 정했습니다.

 

 

참고 - 책 알고리즘 도감