Py) 퀵정렬 Quick Sort

• 데이터 특성 상관 없이 가장 많이 사용되는 정렬 알고리즘
• 라이브러리에서 정렬함수를 호출하면 대부분 quick sort나 merge sort
• 복잡도 분석: 표준 라이브러리 이용시 항상 O(NlogN) 보장, 이상적인 경우- 왼쪽 오른쪽이 균등하게 나눠진 경우, 최악의 경우 - 편향된 경우

 

알고리즘

1. left는 피벗보다 큰 데이터를 찾을 때까지 왼쪽에서 오른쪽으로 탐색한다
2. right는 피벗보다 작은 데이터를 찾을 때까지 오른쪽에서 왼쪽으로 탐색한다
3. left와 right가 엇갈릴 경우 작은 데이터와 피벗의 위치를 바꾼다
4. 새롭게 생긴 두 리스트를 재귀함수로 호출해 퀵정렬을 시행한다

#데이터 특성 상관없이 일반적으로 가장 많이 사용되는 정렬알고리즘
#정렬 라이ㅣ브러리의 근간이 되는 (+병합정렬)
#기본적인 형태- 첫번째 데이터를 피봇으로
#표준라이브러리 이용시 항상 O(NlogN)보장
#이상적인 경우 - 왼쪽 오른쪽 균등하게 나눠진 경우, 최악- 편향된 경우
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: #원소가 1개인 경우
        return #종료
    pivot = start #피벗은 첫번째 원소
    left = start + 1
    right = end
    while(left <= right): #엇갈리기 전까지 반복
        #(선형탐색- left, right 찾는)
        #피벗보다 큰 데이터 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        #피벗보다 작은 데이터 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        #엇갈린 경우 작은 데이터와 피벗 값을 바꿈
        if(left > right): #l이 r보다 클 경우
            array[right], array[pivot] = array[pivot], array[right]
        else: #r이 l보다 클 경우
            array[left], array[right] = array[right], array[left]
    #새롭게 생긴 두 리스트를 재귀로 퀵정렬 시행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

######
#리스트 슬라이싱을 이용할 경우
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:] #피벗을 제외한 리스트

    left = [x for x in tail if x <= pivot] #하나씩 검사하면서 피벗보다 작으면 리스트로
    right = [x for x in tail if x > pivot] #하나씩 검사하면서 피벗보다 크면 리스트로
    #분할하고 재귀를 이용해 각각 정렬 수행하고 리스트 반환
    return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(array))

 

 

파이썬 최고다,,