Quick Sort   퀵 정렬

1. 퀵 정렬 (Quick Sort)

  ㅇ 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
     - 1962년 영국의 컴퓨터 과학자 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 발표

  ㅇ 피벗 선정 및 분할 방식에 따라 여러가지의 변형과 개선 버전 있음


2. 퀵 정렬의 작동방식

  ㅇ 대소 그룹으로 나누는 분할을 반복해가며 정렬
     - 작은 값들을 왼쪽, 큰 값들을 오른쪽으로, 2개의 대소 그룹으로 나누고,
     - 각 그룹 내 다시 동일 동작을 반복하면, 전체가 작은 값부터 큰값으로 정렬됨

  ㅇ 구체적으로, 수열 내에서, 
     - 피봇(기준 원소)을 무작위로 1개 선택한 후,
        . 피봇 선택 방식 : 맨앞, 가운데값, 무작위, 무작위 3개 중 중앙값 등
     - 피봇 이외의 값들을,
        . `피봇 보다 큰 값`, `피봇 보다 작거나 같은 값`의 2 그룹으로 나누며, 이동시킴
     - 피봇 위치는 그대로 두고, 각 수를 피봇과 비교하면서 좌우로 교환 이동 시킴
        . 왼쪽 처음 나오는 큰 값과 오른쪽 처음 나오는 작은 값 간에 교환시킴
        . 교환 위치 이후부터 연이어 왼쪽,오른쪽으로 조사하며, 교환 이동시킴
        . 조사 위치를 관리하기 위한 인수 둘(2) : 시작 위치, 종료 위치
           .. 조사 종료는, 시작 위치와 종료 위치가 만날 때까지임
           .. 피벗은, 통상 시작 위치와 종료 위치 한가운데 값을 취함
     - 각 그룹별로 하나 만 남을 때까지, 재귀적으로 부분 이동 정렬하면,
        . 분할한 그룹별로 재귀 함수 호출에 의해 같은 방법으로 수행
     - 전체 정렬이 됨


3. 퀵 정렬의 특징

  ㅇ 분할 정복 알고리즘

  ㅇ 재귀 호출 활용
     - 통상, 재귀 함수를 사용하여 수행하되, 함수 밖 배열을 정렬하게 됨

  ㅇ 교환 횟수를 줄이기 위해, 교환할 필요가 있는 것끼리 만 교환함

  ㅇ 주요 연산 : 비교(compare), 교환(swap)

  ㅇ 계산 효율성 : O(n log(n))
     - 피벗을 어떻게 선택하는가에 따라, 성능 차이가 큼

  ㅇ (추가편집중)


3. 알고리즘 구현 例)

  ㅇ 파이썬 코드
     
def quicksort(data) :
    # 종료 조건
    if len(data) <= 1 :
        return data
    # 피벗 선택 
    pivot = data[(len(data)-1)//2]
    # 좌우 배열을 리스트 자료구조를 사용하여 생성
    left = []
    right = []
    # 피벗 비교 후 교환을 현재 배열 갯수 만큼 반복
    for i in range(0,len(data)) :
        # 피벗 보다 작으면
        if data[i] < pivot :
            # left(왼쪽그룹)에 추가
            left.append(data[i])
        # 피벗 보다 크면
        elif data[i] > pivot :
            # right(오른쪽그룹)에 추가
            right.append(data[i])
    # 분할된 결과 배열을 같은 방법으로 정렬 (재귀)
    left = quicksort(left)
    right = quicksort(right)
    # 최종 결과 리턴
    return left + [pivot] + right
     - 위 코드는, 함수 밖 배열을 사용하는 대신에, 
        . 새로운 배열을 만들어서 그 결과로써 돌려주는 형태임

  ㅇ (추가편집중)