Algorithm - 버블, 카운팅 정렬 [python]

알고리즘?

문제를 해결하는 절차/ 정확, 작업량, 단순, 최적 중요

---

시간 복잡도

빅-오 표기법을 사용함

버블 정렬(Bubble sort)

첫 번째 원소부터 인접한 원소끼리 계속 자리를 바꾸며 맨 마지막 자리까지 이동한다.
/
시간 복잡도: O(n^2)

def bubble(a):
    for i in range(len(a)-1, 0, -1):
        for k in range(0, i):
            if a[k] > a[k+1]:
                a[k], a[k+1] = a[k+1], a[k]
    return a
print(bubble([55, 7, 78, 12, 42]))

카운팅 정렬(Counting sort)

각 항목의 발생 횟수를 기록
시간 복잡도: O(n+k)

def ccc(array, max):
    counting = [0] * (max+1)
    new = [0] * (max+1)
    
    for i in array:
        counting[i] += 1
        
    for i in range(1, max):
        counting[i] += counting[i-1]
        
    for i in range(len(array)-1, -1, -1):
        new[counting[array[i]]-1] = array[i]
        counting[array[i]] -= 1
        
        
    
        
    return new
print(ccc([0,4,1,3,1,2,4,1], 4))

왜 안되징,,