mergesort_cnt = 0
merge_two_section_cnt = 0

def MergeTwoSection(unsorted_list, start, mid, end):
    global merge_two_section_cnt
    merge_two_section_cnt+=1
    print(start, end, "in MergeTwoSection cnt : ", merge_two_section_cnt)
    #정렬하고자 하는 리스트의 왼쪽 부분 index
    leftIdx = start
    #정렬하고자 하는 리스트의 오른쪽 부분 첫번째 idx
    rightIdx = mid + 1
    #정렬될 데이터의 수
    numOfData = (end - start) + 1

    #정렬된 데이터를 임시 저장할 리스트
    #데이터 개수만큼 초기화한다
    temp_list=[0 for i in range(numOfData+1)]

    #왼쪽 혹은 오른쪽 부분이 모두 temp_list에 저장되고 난 후
    #다른 쪽의 나머지를 temp_list에 담기 위한 idx
    tempIdx = 0

    #데이터의 총 개수 만큼 돌다가
    #왼쪽 부분이든 오른쪽 부분이든
    #한쪽이 모두 temp_list에 담기면 빠져나간다
    for i in range(numOfData):
        #양쪽 인덱스의 값을 비교하여 작은 수를 임시 리스트에 저장
        if unsorted_list[leftIdx] < unsorted_list[rightIdx]:
            temp_list[i] = unsorted_list[leftIdx]
            leftIdx+=1

            #leftIdx가 mid보다 커진다면
            #왼쪽 부분은 이미 모든 데이터가
            #임시 리스트에 들어간 상황
            #for문을 빠져나간다
            if leftIdx > mid:
                tempIdx = i+1
                break
        else:
            temp_list[i] = unsorted_list[rightIdx]
            rightIdx+=1

            if rightIdx > end:
                tempIdx = i + 1
                break


    #왼쪽 부분이 모두 임시 리스트에 올라간 상황이라면
    #오른쪽 부분의 나머지를 모두 임시 리스트에 올린다
    if leftIdx > mid:
        for i in range(rightIdx, end+1):
            temp_list[tempIdx] =unsorted_list[i]
            tempIdx+=1
    #오른쪽 부분이 모두 올라간 상황이면
    #왼쪽 부분의 나머지를 올린다
    elif rightIdx > end:
        for i in range(leftIdx, mid+1):
            temp_list[tempIdx] = unsorted_list[i]
            tempIdx+=1

    #정렬된 리스트 temp_list를
    #정렬이 안된 원본 리스트에 업데이트
    tempIdx = 0
    for i in range(start, end+1):
        unsorted_list[i] = temp_list[tempIdx]
        tempIdx+=1

    #임시 리스트는 지운다
    del temp_list

def mergesort(unsorted_list, start, end):
    #재귀함수 호출 순서를 알아보기 위한 테스트 코드
    global mergesort_cnt
    mergesort_cnt+=1
    print(start, end, "in mergesort cnt : ", mergesort_cnt)
    if start >= end:
        return

    mid = (start + end) // 2

    mergesort(unsorted_list, start, mid)
    mergesort(unsorted_list, mid+1, end)

    MergeTwoSection(unsorted_list, start, mid, end)

if __name__ == "__main__":
    unsorted = [8, 3, 7, 1, 2, 6, 4, 5]
    end = len(unsorted)-1
    mergesort(unsorted, 0, end)
    print(unsorted)

# 파티션 (pivot)

def partition(data, start, end):
    pivot = data[start]

    idx_low = start + 1
    idx_high = end

    # low와 high가 교차해야한다. (중요)
    while idx_low <= idx_high:
        # low가 end보다 같거나 작고, low index에 해당하는 값이 pivot값 보다 작거나 같으면 low는 오른쪽으로 계속 이동
        while idx_low <= end and data[idx_low] <= pivot:
            idx_low += 1

        # high가 start+1 보다 같거나 크고, higt index에 해당하는 값이 pivot값 보다 크거나 같으면 high는 왼쪽으로 계속 이동
        while idx_high >= (start + 1) and data[idx_high] >= pivot:
            idx_high -= 1

        # low 값과 high 값을 교환
        if idx_low <= idx_high:
            data[idx_low], data[idx_high] = data[idx_high], data[idx_low]

    # low와 high가 교차하면 pivot과 high의 값을 교환
    data[start], data[idx_high] = data[idx_high], data[start]

    return idx_high

def quick_sort(data, start, end):
    if start >= end:
        return

    idx_pivot = partition(data, start, end)

    quick_sort(data, start, idx_pivot - 1)
    quick_sort(data, idx_pivot + 1, end)

if __name__ == '__main__':
    li = [2, 5, 4, 1, 8, 10, 5, 3, 6, 6, 5, 7, 9, 12, 11] # [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 9, 10, 11, 12]

    quick_sort(li, 0, len(li) -1)

    print(li)

#성능 비교를 위한 변수
call_of_partition = 0



#정렬된 리스트에서 맨 앞 값을 pivot으로 지정한다면
#예를 들어 1
#성능이 매우 안 좋을 수 있다
#그러므로 pivot 값을 정하는 함수를 따로 만들어
#pivot 값이 가장 작은 값이 되지 않도록 한다
def get_pivot(li, start, end):
    mid = (start + end)//2
    list_idx = [start, mid, end]
    #버블 정렬로 리스트에서의 값을 비교해
    #[가장 작은 값의 index, 가운데 값의 index, 가장 큰 값의 index]
    #순으로 정렬한다
    if li[list_idx[0]] > li[list_idx[1]]:
        list_idx[0], list_idx[1] = list_idx[1], list_idx[0]
    if li[list_idx[1]] > li[list_idx[2]]:
        list_idx[1], list_idx[2] = list_idx[2], list_idx[1]
    if li[list_idx[0]] > li[list_idx[1]]:
        list_idx[0], list_idx[1] = list_idx[1], list_idx[0]
    #정렬이 완료되면 가운데 idx의 값이 중간 값이므로 이를 반환해
    #pivot으로 정하도록 한다
    return list_idx[1]



def partition(li, start, end):
    #partition 함수가 몇 번 호출되었는가를 계산
    global call_of_partition
    call_of_partition += 1



    #pivot 값을 정한다
    idx_pivot = get_pivot(li, start, end)
    #pivot을 리스트의 start index에 두기 위해
    #리스트의 start 값과 pivot idx의 값을 교환한다
    li[start], li[idx_pivot] = li[idx_pivot], li[start]



    #pivot 여기서는 start index의 값을 의미한다
    pivot = li[start]
    #pivot 값을 기준으로 왼쪽에 낮은 값들이 존재할 수 있도록
    #low idx는 검색 도중 pivot보다 큰 값이 있으면
    #그 값을 가리킨다
    low = start + 1
    #pivot 값을 기준으로 오른쪽에 높은 값들이 존재할 수 있도록
    #high idx는 pivot 값보다 작은 값이 있으면
    #그 값을 기리킨다
    high = end

    #반드시 low와 high idx가 교차하게 만든다
    #그 전까지는 교환 규칙에 따라 계속 루프가 돌도록 한다
    while low <= high:
        #low idx는 pivot보다 큰 값을 가진 idx를 만나기 전까지
        #오른쪽으로 이동한다
        #대신 low가 end를 벗어나면 안된다
        while low <= end and li[low] <= pivot:
            low+=1

        #high idx는 pivot보다 작은 값을 가진 idx를 만나기 전까지
        #왼쪽으로 이동한다
        #대신 high가 start + 1을 벗어나면 안된다
        while high >= (start + 1) and li[high] >= pivot:
            high-=1

        #low와 high가 교차 전이라면 두 idx가 가리키는 값을 서로 바꾼다
        if low <= high:
            li[low], li[high] = li[high], li[low]

    #교차했다면 pivot의 idx와 high idx의 값을 서로 교환한다
    #high가 가리키는 idx가 정렬되었을 때의 pivot 값의 위치이기 때문
    li[start], li[high] = li[high], li[start]

    #최종적으로 pivot 값의 최종 idx를 반환
    return high

def quicksort(li, start, end):
    #재귀함수 이므로 탈출 조건이 필요하다
    if start >=end:
        return;

    #정렬된 pivot값의 idx를 가져온다
    idx_pivot = partition(li, start, end)

    #idx_pivot은 정렬이 된 상태 이므로 이를 기준으로
    #앞 부분과 뒷 부분을 quicksort를 통해(재귀함수) 계속 정렬해주면 된다
    quicksort(li, start, idx_pivot - 1)
    quicksort(li, idx_pivot + 1, end)


if __name__ == "__main__":
#     li = [2, 5, 4, 1, 8, 10, 5, 3, 6, 6, 5, 7, 9, 12, 11]

    #정렬된 리스트에서의 성능 평가를 위한 리스트
    li = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

    quicksort(li, 0, len(li)-1)

    print(li)
    print("call_of_partition : %d \n" % call_of_partition)

class Heap:
    # 개체들이 공유하는 메소드는 클래스 메소드로 만들어도 된다.
    def get_parent_idx(self, idx):
        return idx // 2

    def get_left_child_idx(self, idx):
        return idx * 2

    def get_right_child_idx(self, idx):
        return idx * 2 + 1

    # 중요함수- 보통은 유저 프로그래머가 직접 구현, 인터페이스만 제공
    # 우선순위에 따라 반환값이 달라진다.
    def get_prior(self, value1, value2):
        '''
        value1 이 우선순위가 높으면 -1 리턴
        value2 가 우선순위가 높으면 1 리턴
        두 우선순위가 같다면 0을 리턴
        '''
        # min_max == 1 ==> 최소 힙
        if self.min_max == 1:
            if value1 < value2:
                return -1
            elif value1 > value2:
                return 1
            else:
                return 0
        else:  # self.min_max == 2 ==> 최대 힙
            if value1 > value2:
                return -1
            elif value1 < value2:
                return 1
            else:
                return 0

    def __init__(self, s_min_max = 'min'):
        self.dynamic_arr = [None, ] # one based index, 다른 언어는 가변배열을 사용한다. C++은 백터 사용, 효율 좋게 짜는 것이 중요(가변배열이 수정시마다 매번 탐색, 복사, 삭제를 하면 메모리 낭비)
        self.num_of_data = 0 # 마지막 데이터의 index

        if s_min_max == 'max':
            self.min_max = 2
        else:
            self.min_max = 1

    def is_empty(self):
        if self.num_of_data == 0:
            return True

        return False

    def size(self): # ADT에 없는 함수이지만 테스트용으로 만듬
        return self.num_of_data

    # insert 메서드에서 사용
    # 부모 값과 비교해서, 우선순위가 부모 보다 높으면 True 낮으면 False
    def is_go_up(self, idx, data):
        if idx <= 1:
            return False

        parent_value = self.dynamic_arr[self.get_parent_idx(idx)]

        if self.get_prior(parent_value, data) == 1: # 부모 우선순위가 작다면
            return True
        else:
            return False

    def insert(self, data):
        if self.is_empty():
            self.dynamic_arr.append(data)
            self.num_of_data += 1
            return

        self.dynamic_arr.append(data)
        self.num_of_data += 1

        idx_data = self.num_of_data

        while self.is_go_up(idx_data, data):
            parent_idx = self.get_parent_idx(idx_data)
            self.dynamic_arr[idx_data] = self.dynamic_arr[parent_idx]

            idx_data = parent_idx

        self.dynamic_arr[idx_data] = data

    # 우선순위가 높은 자식 노드의 인덱스를 반환
    def which_is_prior_child(self, idx):
        left_idx = self.get_left_child_idx(idx)

        if left_idx > self.num_of_data:
            return None
        elif left_idx == self.num_of_data:
            return left_idx

        right_idx = self.get_right_child_idx(idx)

        left_value = self.dynamic_arr[left_idx]
        right_value = self.dynamic_arr[right_idx]

        if self.get_prior(left_value, right_value) == -1:
            return left_idx
        else:
            return right_idx


    def is_go_down(self, idx, data):
        child_idx = self.which_is_prior_child(idx)

        if not child_idx:
            return False

        child_value = self.dynamic_arr[child_idx]

        if self.get_prior(child_value, data) == -1:
            return True
        else:
            return False

    def delete(self):
        if self.is_empty():
            return None

        ret_data = self.dynamic_arr[1]
        last_data = self.dynamic_arr[self.num_of_data]
        self.num_of_data -= 1

        idx_data = 1

        while self.is_go_down(idx_data, last_data):
            child_idx = self.which_is_prior_child(idx_data)
            self.dynamic_arr[idx_data] = self.dynamic_arr[child_idx]
            idx_data = child_idx

        self.dynamic_arr[idx_data] = last_data
        self.dynamic_arr.pop()

        return ret_data




if __name__ == "__main__":
    heap = Heap("min")
    heap.insert(3)
    heap.insert(5)
    heap.insert(1)
    heap.insert(10)
    heap.insert(8)
    heap.insert(7)
    heap.insert(4)
    heap.insert(5)
    heap.insert(2)
    heap.insert(6)
    heap.insert(9)

    for i in range(1, heap.size()+1):
        print(heap.dynamic_arr[i], end = '  ')
        # 1  2  3  5  6  7  4  10  5  8  9  

    print("\n")

    for i in range(1, heap.size()+1):
        print(heap.delete(), end = '  ')       
        # 1  2  3  4  5  5  6  7  8  9  10   

class PriorityQueue(Heap):
    enqueue = Heap.insert
    dequeue = Heap.delete

if __name__ == "__main__":
    pq = PriorityQueue("min")
    pq.enqueue(3)
    pq.enqueue(7)
    pq.enqueue(2)
    pq.enqueue(1)
    pq.enqueue(9)
    pq.enqueue(5)
    pq.enqueue(8)
    pq.enqueue(10)
    pq.enqueue(5)
    pq.enqueue(6)
    pq.enqueue(4)

    for i in range(1, pq.size()+1):
        print(pq.dynamic_arr[i], end = '  ')
        # 1  2  3  5  4  5  8  10  7  9  6  


    print("\n")

    for i in range(1, pq.size()+1):
        print(pq.dequeue(), end = '  ')
        # 1  2  3  4  5  5  6  7  8  9  10