6-2 Quick Sort 동작방식, 구현

Pivot을 기준으로 작은 것은 왼쪽, 큰 것은 오른쪽으로 정렬해가는 과정을 보겠습니다.

 

아래의 순서대로 순서가 체인지가 됩니다.

 

 

 

 

이렇게 바꾸고 나서, pivot의 위치도 변경해줍니다.

 

자, 이렇게 하면 pivot을 기준으로 작은 것은 왼쪽으로 몰았고, 큰 것은 오른쪽으로 몰았습니다.

 

여기에서 pivot값인 70을 기준으로 작은 것들 중 또 pivot을 정하고 큰 것들 중 또 pivot을 정해서 반복해줍니다.

 

왼쪽 것에 대한 pivot은 50이 되겠고, 오른쪽 것에 대한 pivot은 80이 되겠죠?

 

 

-----

 

자, 이제 코드를 한번 쳐 보겠습니다.

 

코드를 쳐서, 주석을 달아봤습니다.

 

 

 

 

 

이 2개를 프린터 찍어보면 잘 나오는 것을 확인하실 수 있습니다.

 

list = [10, 80, 30, 90, 40, 50, 70]
n = len(list)
quickSort(list, 0, n - 1)
print(list)

 

이것만 보고 이해하시는 분도 있으실 수 있지만, 저 같은 경우에는 print로 로그를 찍어

 

실제로 어떻게 동작하는지 확인합니다.

 

 

pivot: 70
list : [10, 80, 30, 90, 40, 50, 70]
list : [10, 30, 80, 90, 40, 50, 70]
list : [10, 30, 40, 90, 80, 50, 70]
list : [10, 30, 40, 50, 80, 90, 70]

pivot: 50
list : [10, 30, 40, 50, 70, 90, 80]
list : [10, 30, 40, 50, 70, 90, 80]
list : [10, 30, 40, 50, 70, 90, 80]

pivot: 40
list : [10, 30, 40, 50, 70, 90, 80]
list : [10, 30, 40, 50, 70, 90, 80]

pivot: 30
list : [10, 30, 40, 50, 70, 90, 80]

pivot: 80
[10, 30, 40, 50, 70, 80, 90]

 

 

쪼개는 부분을 그림으로 표현하면 이렇게 됩니다.

 

 

 

끝 :)