퀵 정렬(파이썬)

 

 

 

 

퀵 정렬

---

 

 

 

 

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다

 

 

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 = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))

[1, 2, 3, 4, 4, 5, 6, 8, 8, 10]

 

 

 

1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자

import random as rd

def qSort(ns, asc=True):

    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)

    if asc:
        return qSort(smallNums, asc=asc) + sameNums + qSort(bigNums, asc=asc)
    else:
        return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)

if __name__ == '__main__':
    nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]

rNums = rd.sample(range(1, 101), 10)
print(f'not sorted rNums: {qSort(rNums)}')
print(f'merge sorted rNums by ASC: {qSort(rNums)}')
print(f'merge sorted rNums by DESC: {qSort(rNums, asc=False)}')

not sorted rNums: [20, 46, 48, 52, 56, 79, 90, 91, 92, 100]
merge sorted rNums by ASC: [20, 46, 48, 52, 56, 79, 90, 91, 92, 100]
merge sorted rNums by DESC: [100, 92, 91, 90, 79, 56, 52, 48, 46, 20]