알고리즘 공부

를! 해보았습니다

먼저, python을 이용한 merge_sort의 구현입니다.

def mergeSort(nlist):
    comparisons = 0
    #절반을 쪼개기 
    if len(nlist)>1:
        mid = len(nlist)//2
        lefthalf = nlist[:mid]
        righthalf = nlist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=j=k=0       
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                nlist[k]=lefthalf[i]
                i=i+1
            else:
                nlist[k]=righthalf[j]
                j=j+1
            k=k+1
            comparisons += 1
        #왼쪽 리스트
        while i < len(lefthalf):
            nlist[k]=lefthalf[i]
            i=i+1
            k=k+1
            comparisons += 1
        #오른쪽 리스트
        while j < len(righthalf):
            nlist[k]=righthalf[j]
            j=j+1
            k=k+1
            comparisons += 1
        return  comparisons

comparison은 mergesort의 정렬이 이루어 질때마다, 세려고 하였으나 제대로 이루어지지 않은거 같습니다.

두번째로는 python을 이용한 heap_sort의 구현입니다.

def heapify(arr, n, i):
    comparisons = 0
    largest = i  
    l = 2 * i + 1     
    r = 2 * i + 2
    #왼쪽노드
    if l < n and arr[i] < arr[l]:
        largest = l
    #오른쪽노드
    if r < n and arr[largest] < arr[r]:
        largest = r
    #초기 부모 노드가 담은 변수가 달라지면
    if largest != i:
        comparisons += 1
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)
    return comparisons

def heapSort(arr):
    comparisons = 0
    n = len(arr)
    for i in range(n, -1, -1):
        a = heapify(arr, n, i)
        comparisons = comparisons + a
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] 
        a = heapify(arr, i, 0)
        comparisons = comparisons + a
    return comparisons

이번 역시, comparison은 제대로 작동하지는 않는거 같습니다.

세번째는 insertion_sort의 구현입니다.

def insertion_sort(a):
    #비교대상 index 1부터 반복하여 비교 삽입
    for j in range(1,len(a)):
        key = a[j]
        i = j - 1
        comparisons = 0
        #배열 부분집합의 인덱스값 비교
        while (i >= 0 and a[i] > key):
            a[i+1] = a[i]
            i = i - 1
            comparisons += 1
        a[i+1] = key
    return comparisons

3개의 알고리즘 모두 정상적으로 작동하나, comparison은 좀 더 공부해볼 예정입니다.