정렬을 멈추고 순서만 확인하기: 파이썬에서 빠른 O(n) 방법 5가지

Source: Dev.to

sort() 를 사용해 순서를 확인하는 것의 문제점

흔히 저지르는 실수(저도 한 적 있음):

def is_sorted_bad(lst):
    return lst == sorted(lst)

Python의 Timsort는 **O(n log n)**이며 전체 리스트를 복사합니다.
백만 개 요소라면 대략 2천만 번의 연산과 추가 메모리가 필요합니다—그저 예/아니오 답을 얻기 위해서라니! 😩

순서 종류

• 비감소 (중복 허용)

 lst[i + 1]:
            return False
    return True

all() + range

def is_sorted(lst):
    return all(lst[i] = y for x, y in zip(lst, lst[1:]))

경계 상황

• 빈 리스트 또는 원소가 하나뿐인 리스트 → 항상 True
• 서로 다른 타입 혼합 → TypeError ( try/except 로 감싸기)
• None 값 → 직접 처리 필요

방법 비교

NumPy & Pandas 단축키

# NumPy
np.all(arr[:-1] <= arr[1:])

# Pandas
series.is_monotonic_increasing

어쨌든 정렬된 리스트가 필요할 때

이미 정렬된 리스트가 필요하다면 그냥 .sort() 를 호출하세요—이미 정렬된 데이터에 대해 Timsort는 O(n) 로 동작합니다!

가장 많이 사용하는 방법은 무엇인가요? 아래에 댓글을 남겨 주세요 👇

원본 기사