[Python] 힙정렬(Heap Sorting)

 

수행코드

import numpy as np


def make_heap (a,b, descending=False):   #최대힙
    for j in range(1,b+1):
        print("\t j =", j)
        c=j 
        while c!=0:
            r=(c-1)//2
            
            #if a[r]<a[c]:   #최대힙
            #if a[r]>a[c]:   #최소힙
            comp = a[r]<a[c]
            if( (descending==False and comp==True ) or ( descending==True and comp==False  )):
                a[r],a[c]=a[c],a[r]
                print("\t\t r=", r, " c=", c, "switched")
            else:
                print("\t\t r=", r, " c=", c)
            c=r
    
def heap_sort( a, descending=True ):
    for i in range(len(a)-1,0,-1):
        print("i=", i)
        make_heap(a,i, descending )
        a[0],a[i]=a[i],a[0]
        print(">>>Partial: ", a)
    return a
#########################

random = False;
if( random == False ):
    arr=[40,70,60,30,10,50,90,80,20]
else:
    arr =[]
    for i in range(10):
        num1 = np.random.randint(100);
        arr.append(num1)

result = heap_sort( arr, descending = False )
print(":::::::::: RESULT: ", result)

 

 

수행코드 결과

PS D:\PythonCode> python .\HeapSorting.py
i= 8
         j = 1
                 r= 0  c= 1 switched
         j = 2
                 r= 0  c= 2
         j = 3
                 r= 1  c= 3
                 r= 0  c= 1
         j = 4
                 r= 1  c= 4
                 r= 0  c= 1
         j = 5
                 r= 2  c= 5
                 r= 0  c= 2
         j = 6
                 r= 2  c= 6 switched
                 r= 0  c= 2 switched
         j = 7
                 r= 3  c= 7 switched
                 r= 1  c= 3 switched
                 r= 0  c= 1
         j = 8
                 r= 3  c= 8
                 r= 1  c= 3
                 r= 0  c= 1
>>>Partial:  [20, 80, 70, 40, 10, 50, 60, 30, 90]
i= 7
         j = 1
                 r= 0  c= 1 switched
         j = 2
                 r= 0  c= 2
         j = 3
                 r= 1  c= 3 switched
                 r= 0  c= 1
         j = 4
                 r= 1  c= 4
                 r= 0  c= 1
         j = 5
                 r= 2  c= 5
                 r= 0  c= 2
         j = 6
                 r= 2  c= 6
                 r= 0  c= 2
         j = 7
                 r= 3  c= 7 switched
                 r= 1  c= 3
                 r= 0  c= 1
>>>Partial:  [20, 40, 70, 30, 10, 50, 60, 80, 90]
i= 6
         j = 1
                 r= 0  c= 1 switched
         j = 2
                 r= 0  c= 2 switched
         j = 3
                 r= 1  c= 3 switched
                 r= 0  c= 1
         j = 4
                 r= 1  c= 4
                 r= 0  c= 1
         j = 5
                 r= 2  c= 5 switched
                 r= 0  c= 2
         j = 6
                 r= 2  c= 6 switched
                 r= 0  c= 2
>>>Partial:  [50, 30, 60, 20, 10, 40, 70, 80, 90]
i= 5
         j = 1
                 r= 0  c= 1
         j = 2
                 r= 0  c= 2 switched
         j = 3
                 r= 1  c= 3
                 r= 0  c= 1
         j = 4
                 r= 1  c= 4
                 r= 0  c= 1
         j = 5
                 r= 2  c= 5
                 r= 0  c= 2
>>>Partial:  [40, 30, 50, 20, 10, 60, 70, 80, 90]
i= 4
         j = 1
                 r= 0  c= 1
         j = 2
                 r= 0  c= 2 switched
         j = 3
                 r= 1  c= 3
                 r= 0  c= 1
         j = 4
                 r= 1  c= 4
                 r= 0  c= 1
>>>Partial:  [10, 30, 40, 20, 50, 60, 70, 80, 90]
i= 3
         j = 1
                 r= 0  c= 1 switched
         j = 2
                 r= 0  c= 2 switched
         j = 3
                 r= 1  c= 3 switched
                 r= 0  c= 1
>>>Partial:  [10, 20, 30, 40, 50, 60, 70, 80, 90]
i= 2
         j = 1
                 r= 0  c= 1 switched
         j = 2
                 r= 0  c= 2 switched
>>>Partial:  [20, 10, 30, 40, 50, 60, 70, 80, 90]
i= 1
         j = 1
                 r= 0  c= 1
>>>Partial:  [10, 20, 30, 40, 50, 60, 70, 80, 90]
:::::::::: RESULT:  [10, 20, 30, 40, 50, 60, 70, 80, 90]

 

 

 

수행코드 분석