O(N^2) 정렬

제로베이스 데이터 취업 스쿨 2주차 스터디노트 5호

타겟

Selection / Bubble / Insertion

코드

# selection
def selection(seq):
    for pivot in range(len(seq) - 1): # 아래 제외 때문에 -1
        min_idx = pivot
        for idx in range(pivot + 1, len(seq)): # min으로 임시 설정된 index 제외
            if seq[idx] < seq[min_idx]:
                min_idx = idx
        seq[pivot], seq[min_idx] = seq[min_idx], seq[pivot]
    return seq

# bubble
def bubble(seq):
    for pivot in range(len(seq) - 1, 0, -1): # 내부의 반복문이 가장 큰 값을 오른쪽으로 끌고옴
        for idx in range(pivot): # pivot 기준 오른쪽 정렬 완료 상태이므로 추가 작업 불필요
            if seq[idx] > seq[idx + 1]:
                seq[idx + 1], seq[idx] = seq[idx], seq[idx + 1]
    return seq

# insertion
def insertion(seq):
    for pivot in range(1, len(seq)):
        for idx in range(pivot, 0, -1): # 이전 반복으로 인접 수 비교가 아닌 삽입이 됨
            if seq[idx - 1] > seq[idx]:
                seq[idx - 1], seq[idx] = seq[idx], seq[idx - 1]
    return seq

공통

• 공간복잡도 $O(1)$
• $O(NlogN)$ 정렬을 주로 쓴다.
• $O(N^2)$은 주로 학습용이다.

Selection sort

• 교환 횟수를 최소화하고 싶을 때 쓴다.
• 불안정 정렬이며, 정렬이 되어있어도 $O(N^2)$이다.
  따라서 쓸 이유가 딱히 없다.

Bubble sort & Insertion sort

• 안정 정렬

그 외

• bubble과 insertion은 최선의 경우엔 O(N)이다.
  하지만 알고리즘은 최선의 경우를 생각하지 않는 경향이 있다.