Radix Sort

yijin3018·2021년 11월 11일
0
  • 개념 : 낮은 자리수부터 비교 정렬.
  • 특징
    • 비교연산 x
    • stable
  • 장점
    • 정렬 속도 빠름.
  • 단점
    • 기수 테이블 크기만한 메모리 필요함. - 중간결과 저장 bucket공간 필요
  • 시간복잡도 : O(nK)O(nK) (K : 원소의 최대값)
  • 공간복잡도 : O(n+K)O(n+K)
arr = [4,2,5,6,1,3]

# Solution 1
a = [3,1,2,5,4,6]

def heap_sort(a):
    for i in range(1, len(a)):
        c = i
        while c!=0:
            r = (c-1) // 2
            if a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
            c = r
    for j in range(len(a)-1, -1, -1):
        a[0], a[j] = a[j], a[0]
        r = 0
        c = 1
        
        while c<j:
            c = 2 * r + 1
            if c < j-1 and a[c] < a[c+1]:
                c += 1
            if c< j and a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
            
            r=c
heap_sort(a)
print(a)

# Solution 2
a = [3,1,2,5,4,6]

def heapify(arr, index, heap_size):
    largest = index 
    left_index = 2 * index + 1 
    right_index = 2 * index + 2 
    if left_index < heap_size and arr[left_index] > arr[largest]: 
        largest = left_index 
    if right_index < heap_size and arr[right_index] > arr[largest]:
        largest = right_index 
    if largest != index:
        arr[largest], arr[index] = arr[index], arr[largest] 
        heapify(arr, largest, heap_size) 
                
def heap_sort(arr): 
    length = len(arr) 
    for i in range(length // 2 - 1, -1, -1):
        heapify(arr, i, length) 
    for i in range(length - 1, 0 , -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i) 
    return arr

heap_sort(a)
print(a)
profile
💻 For Computer Science..

0개의 댓글