学習アルゴリズム

乙!やってみた

まず,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

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

今回はやはり、比較的普通に仕事ができないようです.
3つ目は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つのアルゴリズムは正常に動作するが,さらに比較を検討する.