퀵 정렬, 분할 알고리즘 파이썬 구현

퀵 정렬

- 평균적으로 가장 좋은 성능을 가짐

- 현장에서 가장 많이 쓰이는 정렬 알고리즘

 

1. 정렬할 배열에서 기준 원소를 고른다

2. 기준 원소보다 작은 수는 왼쪽에, 큰 수는 오른쪽에

3. 기준 원소의 왼쪽과 오른쪽 부분 배열을 다시 정렬 (퀵 정렬 재귀)

 

파이썬 코드 구현

타입 에러

- return값이 없어서 - X

- range 설정이 잘못됨

 

#Quik sort 퀵정렬

def quickSort(a, p, r):
    if p<r:
        q = partition(a, p, r)
        quickSort(a, p, q-1)
        quickSort(a, q+1, r)
    
def partition(a, p, r):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    
    a[r], a[i+1] = a[i+1], a[r]
    
    return i+1
    
arr = [5, 3, 1, 6, 2, 4]
quickSort(arr, 0, len(arr)-1)
print(arr)

깔끔하게 구현 완료!

 

 

참고 쉽게 배우는 알고리즘