[Python] 알고리즘의 종류, 종류별 예제 _ 정렬 (4/7)

데이터를 특정한 기준에 따라 순서대로 나열 하는 것

선택정렬

idx순서대로 뒤에있는 array중 최소값을 맨앞으로 스왑

#선택정렬
array = [7,5,9,0,3,1,6,2,4,8]

for idx, v in enumerate(array):
    if idx <= len(array) - 2:
        last_idx = array.index(min(array[idx + 1 : len(array)]))
        array[idx], array[last_idx] = array[last_idx], array[idx]
    
print(array)

삽입정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적

#삽입정렬
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(0, 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

퀵정렬

기준데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

표준라이브러리로 채택되며 O(NlogN)을 보장함

계수정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

데이터의 개수가 N, 데이터 최대값이 K일 때 최악의 경우에도 O(N+K)를 보장

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
cnt = [0,0,0,0,0,0,0,0,0,0]

for i in range(0, len(array)):
    cnt[array[i]] += 1

result = []
for idx, v in enumerate(cnt):
    if v > 0:
        for _ in range(0, v):
            result.append(idx)

공간복잡도 시간복잡도 O(N+K)

데이터의 범위가 너무 크다면 비효율, 같은 데이터가 반복해서 나올때 효율적