삽입정렬 및 계수정렬 파이썬

삽입정렬의 경우 시간복잡도가 중첩이 두번돌아 n제곱이지만 정렬이 거의 되어있다는 가정이면 퀵정렬보다빠른 O(N)의 속도를 가질수도 있다. 그러므로 데이터를 잘보고 정렬알고리즘을 선택할 필요가 있다.

 

# 삽입정렬은 선택정렬과 같은 시간 복잡도를 가졌지만 거의 정렬되어있는 상태라면 삽입정렬이 빠르다.
array = list(map(int, input().split()))

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

 

계수정렬

 

# 계수정렬 모든 원소의 값이 0보다 크커나 같다고 가정
array = list(map(int, input().split()))
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1    # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end= ' ')