정렬 방법론.
1. heapify()함수를 호출해서 힙으로 만든다.
힙 구조로 만드는 과정.
ex)
6 2 8 1 3 9 4 5 10 7 이라는 리스트가 있다고 하자. 이걸 이진 트리로 나타내면.
가 되고 이걸 top down히프로 변환하자. 변환방법은
맨위의 6 2 8 을 보면 가장 큰 수인 8이 맨 위에 있지 않다. 그러므로 6과 8을 교환한다. (부모가 자식 둘보다 커야 한다.) 그다음에는 2 1 3부분의 3과 2를 교환하고, 이런식으로 하나씩 간다. 그러면
이런식으로 된다.
특징.
1. 우선순의 큐의 일종인 힙을 사용한다.
2. 제자리 정렬 알고리즘.
3. 퀵정렬보다 오래걸림.
시간복잡도 : O(NlogN)
# -*- encoding: cp949 -*-
import time
import random
N = 10000
def swap(a,i,j):
a[i],a[j] = a[j],a[i]
def CheckSort(a,n):
Sorted = True
for i in range(n):
if a[i] > a[i+1]:
Sorted = False
if not Sorted:
break
if Sorted: print '정렬 완료.'
else: print '정렬 오류 발생.'
def heapify(a,h,m):
v = a[h]
j = 2*h
while j <= m:
if j < m and a[j] < a[j+1]:
j += 1
if v >= a[j]: break
else: a[j/2] = a[j]
j *= 2
a[j/2] = v
def HeapSort(a,n):
for i in range(n/2,0,-1):
heapify(a,i,n)
for i in range(n-1,0,-1):
swap(a,1,i+1)
heapify(a,1,i)
def main():
a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
a[0] = -1
start_time = time.time()
HeapSort(a,N)
print '(랜덤)힙 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터 #리커전이 너무 많이 일어나서 랜덤한 데이터밖에 정렬이 안된다.
a[0] = -1
start_time = time.time()
HeapSort(a,N)
print '(최고)힙 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
a[0] = -1
start_time = time.time()
HeapSort(a,N)
print '(최악)힙 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
if __name__=='__main__':
main()
나중에 참고하면 좋을것 같음.