Quick Sort (퀵 정렬) python으로 구현하기

- Quick  Sort  설명

: pivot을 설정하고 partition을 수행하여 pivot값을 고정시킨다. 

 

<순서>

1. pivot을 설정하기
2. partition과정 수행 → pivot이 고정됨
3. pivot보다 큰 부분과 작은 부분 각각 quick sort 다시 시행 

Quick Sort 과정

 

 

- Partition 과정

1. i= 맨처음 수 , j= 맨 마지막 수 
2. 
(1) i가 하나씩 커지면서 i>pivot이 되면 멈춤 
(2) j가 하나씩 작아지면서 j<pivot이 되면 멈춤 
3.
If  i<j인 경우, List[i]와 List[j]의 값을 바꿔줌 
Else, List[j]와 pivot값을 바꿔주고 pivot은 고정된다.

 

Partiton 과정

 

- Python Code ( Partition )

 

 

- Python Code ( Quick Sort )