정렬 고급

버블 정렬

--> 첫 번째 값부터 시작해서 바로 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법
--> 전체 비교로 시작
ex) 데이터가 4개를 정렬
1번째 사이클: 0 vs 1 -> 1 vs 2 -> 2 vs 3 ==> 데이터 갯수 - 1
--> 1번째 사이클이 완료되면 가장 큰 데이터가 맨 뒤에 위치한다.
2번째 사이클: 0 vs 1 -> 1 vs 2 ==> 데이터 갯수 - 2
3번째 사이클: 0 vs 1 ==> 데이터 갯수 - 3

버블 정렬 구현

## 클래스와 함수 선언 부분 ##
def bubbleSort(ary):
    n = len9(ary)
    for end in range(n-1, 0, -1): # cycle 크기가 전체에서 1개씩 점점 감소
        for cur in range(0, end):
            if (ary[cur] > ary[cur+1]):
                ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
    return ary

버블 정렬의 성능, 특이점

성능 : 삽입, 선택 정렬과 같이 연산 수는 O(n^2) 이다.
But, 기존의 배열이 어느 정도 정렬되어 있다면 연산 수는 급격하게 줄어든다.

이미 정렬된 상태이면 사이클을 종료하는 버블 정렬 구현

## 클래스와 함수 선언 부분 ##
def bubbleSort(ary):
    n = len(ary)
    for end in range(n-1, 0, -1):
        changeYN = False # 자리 바꿈이 발생했는지 확인하는 변수
        for cur in range(0, end):
            if (ary[cur] > ary[cur+1]):
                ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
                changeYN = True # 발생하면 True
        if not changeYN:
            break
    return ary

퀵 정렬

--> 기준을 하나 뽑은 후 기준보다 작은 그룹과 큰 그룹을 나누어 다시 각 그룹으로 정렬하는 방법
--> 나눈 그룹을 다시 정렬할 때 재귀 호출 사용, 완료 후 합친다.
--> 첫 번째로 기준(pivot)을 설정하는 것이 중요하다 -> 일반적으로 중간에 위치

퀵 정렬 구현

## 클래스와 함수 선언 부분 ##
def quickSort(ary):
    n = len(ary)
    if n <= 1:
        return ary # 정렬에 데이터가 1개 이하이면 정렬이 끝난 그룹
    pivot = ary[n//2] # 기준 (pivot) 지정
    leftAry, rightAry = [], []
    for num in ary:
        if num < pivot: # 기준보다 작으면 왼쪽으로 삽입
            leftAry.append(num)
        elif num > pivot: # 기준보다 크면 오른쪽으로 삽입
            rightAry.append(num)
    return quickSort(leftAry) + [pivot] + quickSort(rightAry)
    # 재귀호출로 나뉜 그룹 정렬

중복 값을 고려한 퀵 정렬

leftAry, midAry, rightAry 3개의 빈 배열을 만들어준다.

퀵 정렬의 일반 구현

--> 기존의 배열 하나로 퀵 정렬을 구현
low : 시작 부분 (start)
high : 끝 부분 (end)

## 클래스와 함수 선언 부분 ##
def qSort(arr, start, end):
    if end <= start:
        return
    low = start
    high = end
    pivot = arr[(low+high) // 2]
    while low <= high:
        while arr[low] < pivot:
            low += 1 # 첫 번째 데이터가 기준보다 작으면 +1
        while arr[high] > pivot:
            high -= 1 # 맨 끝 데이터가 기준보다 크면 -1
        if low <= high: # 기준보다 큰 값이 왼쪽, 작은 값이 오른쪽에 있는 경우
            arr[low], arr[high] = arr[high], arr[low]
            low, high = low + 1, high + 1
    mid = low
    qSort(arr, start, mid-1)
    qSort(arr, mid, end)
def quickSort(ary):
    qSort(ary, 0, len(ary)-1)

퀵 정렬 성능과 특이점

성능 : 연산 수 --> O(n^2)
But, 평균적인 연산 수는 O(nlogn)