Python - 퀵 정렬

퀵 정렬

 기준 값을 정하고 기준값을 중심으로 나눠서 작고 큰 값을 정렬하여 합치는 방식이다.

 

예제

def qSort(ns):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    smallNums = []
    sameNums = []
    bigNums = []

    for n in ns:
        if n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        else:
            bigNums.append(n)

    return qSort(smallNums) + sameNums + qSort(bigNums)


nums = [2, 3, 4, 5, 2, 1, 4, 11, 14]

print(nums)
print(qSort(nums))

내용

 재귀함수를 이용하여 사용하며 코드에서는 기준을 리스트의 가운데 인덱스의 값으로 잡았다.

 가운데 인덱스를 기준으로 앞, 뒤, 같은 숫자 배열을 생성한다.

 인덱스 값으로 비교하여 작으면 작은 값을 모은 배열에, 크면 큰값을 모은 배열, 같은값을 넣는 배열에 각각 넣으며 한 번의 함수 실행에 정렬이 끝나면 3개의 배열을 합쳐서 리턴하고 재귀로 반복하여 결과적으로 정렬 완료된 상태가 된다.

 

결과

[2, 3, 4, 5, 2, 1, 4, 11, 14]
[1, 2, 2, 3, 4, 4, 5, 11, 14]