정렬 코드2(퀵 정렬, 병합 정렬)

퀵 정렬 (quick sort)

• 퀵정렬은 삽입정렬과 다르게 '이미 데이터가 거의 정렬된 경우' 시간복잡도가 거의 O(n^2)으로 매우 느리게 동작한다.
• 하지만 데이터가 무작위로 입력되는 경우 O(nlogn)의 속도로 매우 빠르게 동작한다. 그러므로 데이터의 상태를 보고 삽입정렬과 잘 선택하여 사용해야한다.

---

def quick_sort(array, start, end):
    if start >= end:                   # 아래 재귀함수에서 모든 정렬이 끝나고 원소가 1개인 경우 종료
        return
    pivot = start
    left = start + 1
    right = end
    while 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:             # left와 right가 교차할때 작은값(right(엇갈렸으므로))과 pivot 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 만약 교차하지 않았다면 left와 right 교체
            array[left], array[right] = array[right], array[left]

 

    quick_sort(array, start, right - 1) # pivot 기준 왼쪽
    quick_sort(array, right + 1, end) # pivot 기준 오른쪽 재귀함수를 통해 다시 정렬

 

---

퀵 정렬2 (quick sort)

• 파이썬의 장점을 살린 좀 더 짧고 직관적인 quick sort code (비교 횟수가 증가하여 효율은 조금 감소)

 

def quick_sort(array):

    if len(array) <= 1:

        return array

 

    pivot = array[0]

    tail = array[1:]

 

    left_side = [x for x in tail if x <= pivot]         # 피봇을 제외한 리스트 tail 중 피봇보다 작은 값을 left_side 객체에 저장 (모든 tail에 대해 비교를 하므로 더 연산횟수가 많음)

    right_side = [x for x in tail if x > pivot]         # 같은 방식으로 피봇보다 큰 값을 right_side 객체에 저장 return           

    quick_sort(left_side) + [pivot] + quick_sort(right_side)         # 재귀함수를 호출하여 len(array) <= 1 일때까지 반복하고 전체 리스트 반환

 

---

병합 정렬 (merge sort)

• 데이터를 더 이상 나눌 수 없을 때까지 나누고, 다시 병합하며 정렬하는 방법이다. (병합 할 때 정렬실행) 
• 데이터를 나눌 때 점차 반씩 줄어드므로 O(logN), 병합 할때 모든 값을 비교 해야하므로 O(N)이므로 총 O(NlogN)의 시간복잡도를 가진다.

---

def merge_sort(array):

    if len(array) <= 1:

        return array

 

    mid = len(array) // 2

    left_array = array[:mid]

    right_array = array[mid:]

 

    left_array = merge_sort(left_array)

    right_array = merge_sort(right_array)

    return merge(left_array, right_array)

 

def merge(left, right):

    result = []

    while ( len(left) > 0 or len(right) > 0 ):

        if ( len(left) > 0 and len(right) > 0 ):

            if ( left[0] <= right[0] ):

                result.append(left[0])

                left = left[1:]

            else:

                result.append(right[0])

                right = right[1:]

        elif len(left) > 0:

            result.append(left[0])

            left = left[1:]

        elif len(right) > 0:

            result.append(right[0])

            right = right[1:]

    return result