ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [python]퀵 정렬
    Programming/python 2019. 10. 18. 22:46

    퀵 정렬(Quick Sort)이란?


    퀵 정렬은 기준(Pivot)을 먼저 정하고 그 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트들을 기준과 비교해 정렬한 다음 정렬된 부분을 합하는 방법.

    그룹을 둘로 나누어서 재귀 호출한다는 방식은 병합 정렬과 비슷하지만 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다르다.

    1. 분할단계(divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽은 피벗보다 작은 요소들을 배치하고, 오른쪽은 피벗보다 큰 요소를 배치)로 분할한다.
    2. 정복단계(Conquer): 부분 배열을 정렬한다. 배열 크기가 충분히 작지 않다면 재귀 호출을 이용해서 다시 분할 정복 방법 적용(재귀는 리스트가 1이하가 될 때까지 반복된다)
    3. 결합단계(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

    오른쪽 애니메이션에 파란 가로줄은 Pivot, 즉 기준이 되고 그 피벗을 기준으로 위아래를 나눈다.

     

     

     

    핵심은 기준보다 작은 건 왼쪽으로 큰건 오른쪽으로 하는 재귀 함수로, 반복을 계속해서 나눈 리스트에서 기준을 정하고 피봇을 기준으로 나눈다는 것

     

     

    알고리즘의 특징


    장점

    • 재귀가 호출될 때마다 최소한 하나의 기준(Pivot)은 최종적으로 위치가 정해져서 이 알고리즘이 반드시 끝난다는 것을 보장할 수 있음
    • 퀵 소트라는 이름이 지어질 정도로 속도가 빠르다

    단점

    • 중복된 값이 있거나 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

     

    시간복잡도


    평균적인 시간 복잡도를 빅오표기법으로 쓰면 O(n * logN) 인데, 불 필요한 데이터의 이동을 줄이고(피봇은 항상 고정되어 있음)먼 거리의 데이터를 교환하며, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 덕분에 같은 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교했을 때에도 가장 빠르다는 것을 알 수 있다.

    코드


     

    # 퀵 정렬
    # 리스트 a를 퀵 정렬로 정렬함
    # 매게 변수로 어디서부터 어디까지 정렬할 건지 받음
    
    #범위를 지정하여 정렬하는 재귀 호출 함수
    def partition(a, start, end):
        #리스트가 한개 이하면 종료
        if end - start <= 0:
            return
        
        #기준값을 임의로 마지막 값으로 잡음 시작 값으로 잡아도 상관없음
        pivot = a[end] 
        i = start
    
        for j in range(start, end):
            if a[j] <= pivot:
               a[i], a[j] = a[j], a[i] #기준보다 작으면 왼쪽값과 교환하기
               i += 1
        a[i], a[end] = a[end], a[i]
        #재귀 호출 부분
        partition(a, start, i-1) #기준 값보다 작은 그룹들을 재귀 호출로 정렬
        partition(a, i+1, end) #기준 값보다 큰 그룹들을 재귀 호출로 정렬
    
    #리스트 전체를 다시 재귀 호출로 부름
    def quick_sort(a):
        partition(a, 0, len(a) - 1)
    
    a = [5,6,2,9,1,3,4,7,8,32,16]
    quick_sort(a)
    print(a)

     

    'Programming > python' 카테고리의 다른 글

    큐와 스택은 무엇인가  (0) 2019.11.03
    [python]버블 정렬  (0) 2019.10.20
    [python]합병 정렬  (0) 2019.10.18
    [python]삽입 정렬  (0) 2019.10.16
    [python]선택 정렬  (0) 2019.10.15

    댓글

Copyright 2023. 은유 All rights reserved.