인용 사이트

이번에는 먼저 정리하기 위해 배견 한 사이트를 소개하겠습니다.

알고리즘 참고

추적 참고

각각 조금만 알고리즘 자체가 다릅니다만 같은 퀵 소트이므로 씨의 알고리즘을 바탕으로 정리하겠습니다

프로그램

@ muijp 님의 퀵 정렬 에 요전날 씨로부터 어드바이스를 받은 랜덤 배열의 프로그램과 디버그용의 출력을 넣었습니다

q_sort.py

def qSort(a):
    print(a)#デバッグ用
    if len(a) in (0, 1):
        return a

    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

    return qSort(l) + [p] + qSort(r)
a = r.sample(range(1,11),k=9)
qSort(a)
#出力＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

그래, 프로그램이 너무 간결해서 모르겠어.

분해하고 생각하다

우선 주목해야 할 곳은return qSort(l) + [p] + qSort(r)라고 생각한다.
이거는 퀵 소트의 특징인 「피팟(주목하고 있는 셀)」의 오른쪽과 왼쪽에 작은 숫자(배열)와 큰 숫자(배열)를 둔다는 부분이 된다.　　　　

추적 참고
이 사이트의 gif를 보면
1. 한가운데 피포트를 취한다
2. 바깥쪽에서 순서대로 왼쪽에 있는 작은 수와 오른쪽에 있는 큰 수를 교환합니다.
3. 스캔 범위를 최소 ~ 피팟으로 변경하고 중앙에 피팟을 가져옵니다.
를 반복하고 있는 것을 알 수 있다.

　　
　　
다만 이번 프로그램에서는p = a[-1]로 피팟을 마지막 숫자로 가져가
그리고,
l = [x for x in a[:-1] if x <= p] r = [x for x in a[:-1] if x > p]그리고, 피팟트보다 큰 숫자와 피팟트보다 작은 숫자로 나누고, 그것을 return 로 (재기함수를 부르면서) 접합하고 있다.
　　
　　

첫

if len(a) in (0, 1):

        return a

는 문자가 1문자 이하라면 그것을 재기함수의 반환값으로서 돌려주고 있다.

추적하기

이상을 바탕으로 방금전의 난수로 추적해 보자

#出力＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

배열[3, 7, 1, 6, 9, 8, 2, 10, 4]
피팟 p = 4
작은 배열 l = {3,1,2}
큰 배열 r={7,6,9,8,10}
로 분해