퀵정렬, 병합정렬, 힙정렬

정렬

[안정적인 정렬 알고리즘] 
중복된 값을 입력 순서와 동일하게 정렬

[안정적이지 않은 알고리즘] 
중복된 값을 입력 순서와 상관없이 무작위로 정렬

[제자리 정렬] 
원본 배열 외에 추가적인 큰 메모리 공간을 사용하지 않는 정렬 알고리즘
- 버블정렬, 선택정렬, 삽입정렬, 퀵정렬

퀵정렬

가장 빠른 정렬 알고리즘
퀵정렬은 불안정 정렬 알고리즘 

[장점]
빠르게 정렬 가능 O(NlgN)
제자리 정렬로 추가 메모리 사용이 적음 

[단점]
불안정 정렬이므로 동일한 값에 대하여 순서 보장 못함 
최악의 경우 O(N^2) 소요 // 정렬된 배열이거나, 거의 정렬된 경우 최악의 경우 발생
피벗 선택 방법에 따라 성능 차이가 발생할 수 있다.
재귀호출로 인한 오버헤드가 발생한다. 

p (피벗, 중심축) - 그룹을 나누는 기준 
pl - 왼쪽 커서 
pr - 오른쪽 커서 

[퀵정렬 처리 과정]
1. pl는 배열의 오른쪽으로 이동하면서 중심축의 값보다 큰 값에서 멈춘다.
2. pr은 배열의 왼쪽으로 이동하면 중심축의 값보다 작은 값에서 멈춘다.
3. 이 때 pl이 pr보다 작다면 pl과 pr의 요소를 바꾼다.
4. 1 ~ 3번을 pl < pr인 경우 반복
5. 만약 pl < pr이 성립하지 않지만, 시작 인덱스가 pr 보다 작으면 재귀를 통해 quickSort를 수행 
-> 중심축을 기준으로 왼쪽 배열에 대하여 퀵정렬 수행
6. 만약 pl < pr이 성립하지 않지만, 끝 인덱스가 pl 보다 크면 작으면 재귀를 통해 quickSort를 수행
-> 중심축을 기준으로 오른쪽 배열에 대하여 퀵정렬 수행

# 퀵정렬 코드 1
def quickSort(arr, left, right) :
    pl = left
    pr = right
    p = (left + right) // 2

    # 등호를 붙이는 이유는 pl과 pr이 같을 때도 수행되어 교차되게 만들어야 함
    while pl <= pr :
        while arr[pl] < arr[p] :
            pl += 1 
        while arr[p] < arr[pr] :
            pr -= 1

        if pl <= pr :
            arr[pl], arr[pr] = arr[pr], arr[pl]
            pl += 1 
            pr -= 1
    # 시작 부분이 pr을 넘지 않았다면 
    if left < pr :
        quickSort(arr, left, pr)

    # 마지막 부분이 pl보다 작지 않았다면 
    if right > pl :
        quickSort(arr, pl, right)

# 퀵정렬 코드 2
def quickSort(arr) :

    if len(arr) <= 1 :
        return arr

    length = len(arr)
    p = len(arr) // 2

    smallList = list()
    equalList = list()
    largeList = list()

    for i in range(len(arr)) :
        if arr[i] < arr[p] :
            smallList.append(arr[i])
        elif arr[i] > arr[p] :
            largeList.append(arr[i])
        else :
            equalList.append(arr[i])

    return quickSort(smallList) + equalList + quickSort(largeList)

병합정렬

배열을 앞부분과 뒷부분 두 부분으로 나눠 각각 정렬한 후 병합을 반복하는 정렬 알고리즘
즉, 배열을 더 이상 쪼갤 수 없을 때까지 재귀적으로 배열을 절반으로 나누고, 다시 정렬하여 통합

[장점]
안정적인 정렬 알고리즘
시간 복잡도가 O(NlgN)이므로 요소 수가 많은 경우에 성능이 우수 

[단점]
제자리 정렬이 아님 즉, 추가 공간이 필요하여 메모리가 제한된 환경에 적합하지 않음 
재귀호출 및 병합 프로세스에 대한 오버헤드가 발생하여 작은 데이터셋인 경우 다른 정렬 알고리즘 보다 비효율

[병합 정렬 처리 과정]
1. 배열의 길이가 1이 될 때까지 중심축을 기준으로 왼쪽, 오른쪽 배열로 나눈다.
2. 모든 배열의 길이가 1이 되었을 때 배열의 원소를 하나하나 비교해가며 병합한다.

# 병합 정렬 코드 
def mergeSort(arr) :
    length = len(arr)
    if length <= 1 :
        return arr

    p = length // 2

    # 배열 크기가 1이 아니므로 왼쪽, 오른쪽으로 쪼갠다.
    left = mergeSort(arr[:p])
    right = mergeSort(arr[p:])

    lp = 0
    rp = 0
    leftLen = len(left)
    rightLen = len(right)

    resultList = list()

    # 왼쪽 배열과 오른쪽 배열의 원소를 비교하며 병합한다.
    while leftLen > lp and rightLen > rp :
        if left[lp] <= right[rp] :
            resultList.append(left[lp]) 
            lp += 1
        else :
            resultList.append(right[rp])
            rp += 1

    # 남은 원소를 넣는다.
    resultList.extend(left[lp:])
    resultList.extend(right[rp:])

    return resultList

힙 정렬

선택 정렬을 응용한 정렬 알고리즘 
힙의 특성을 이용하여 정렬하는 알고리즘
제자리 정렬

[최대힙] 
부모의 값이 자식의 값보다 항상 크다. // 형제 사이 대소 관계는 일정하지 않음(부분 순서 트리)
최대값은 루트에 위치
완전 이진 트리

[최소힙]
부모의 값이 자식의 값보다 항상 작다. // 부분 순서 트리
최소값은 루트에 위치
완전 이진 트리 

[장점]
최선, 평균, 최악의 경우도 모두 O(NlgN) 시간복잡도를 갖는다. 
제자리 정렬이므로 추가 메모리 사용이 적음
전체를 정렬하지 않고 가장 큰 또는 작은 K개의 요소만 필요할 때 효율적 

[단점]
불안정 정렬이므로 동일한 값에 대하여 순서를 보장하지 않음
같은 복잡도를 갖는 퀵 정렬이나 병합 정렬에 비해 실제 성능이 조금 떨어짐
다른 정렬에 비해 구현이 조금 더 복잡 
연결 리스트와 같은 순차적 접근 자료구조에서 효율이 떨어짐

[힙 정렬 처리 과정]
** 최대힙 기준 **
1. 입력으로 들어온 배열을 힙으로 만든다. // 초기힙 구성
2. 제일 큰 값인 root 값과 확정되지 않은 마지막 인덱스와 교환한다.
3. 확정된 인덱스 바로 앞 즉 맨 뒤 값을 꺼내어 루트에 삽입
4. heapfy()를 호출하여 배열을 힙으로 만든다. 
5. 1~4를 반복하여 힙 정렬을 수행한다.

1. 입력으로 들어온 배열을 힙으로 만든다.

2. 제일 큰 값인 root노드 값을 꺼내 확정되지 않은 마지막 인덱스 노드와 교환한다.

3. 확정된 인덱스 바로 앞 즉 맨 뒤 값을 꺼내어 루트에 삽입

4. heapify()를 호출하여 배열을 힙으로 만든다.

5. 1~4를 반복하여 힙 정렬을 수행한다.

# 힙정렬 코드 
from collections import deque
arr = [10,9,5,8,3,2,4,6,7,1]

def heapify(arr, root, length) :
    lc = root * 2 + 1
    rc = root * 2 + 2

    if rc < length :
        # 왼쪽, 오른쪽 둘 다 있는 경우
        if arr[lc] < arr[rc] :
            max = rc
        elif arr[lc] >= arr[rc] :
            max = lc
        else :
            # 자식이 아예 없는 경우
            return 
    elif lc < length :
        # 왼쪽만 있는 경우
        max = lc
    else :
        # 둘 다 없는 경우 (더 이상 실행할 필요 없음)
        return

    # 자식 요소가 부모 요소보다 더 큰 경우
    if arr[root] < arr[max] :
        arr[root], arr[max] = arr[max], arr[root]
        heapify(arr,max, length)

def heapSort(arr) :
    length = len(arr)

        # 초기힙 구성
    for i in range(length // 2 - 1, -1, -1) :
        heapify(arr, i, length)

        # 힙정렬 수행
    for i in range(length-1, 0, -1) :
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr,0 , i)

    return arr

print(heapSort(arr))