정렬 알고리즘 -삽입 정렬 - insertion sort

삽입 정렬은 한 번에 한 항목씩 최종 정렬된 배열을 구축하는 간단한 정렬 알고리즘입니다. 이 알고리즘은 입력 배열을 반복하고 각 반복마다 배열에서 요소를 하나씩 제거하고 배열의 정렬된 부분에서 해당 요소가 속하는 위치를 찾아서 삽입합니다. 알고리즘은 전체 배열이 정렬될 때까지 이 과정을 반복합니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

 

이 구현에서 insertion_sort 함수는 입력 목록 배열을 가져와서 삽입 정렬 알고리즘을 사용하여 제자리에서 정렬합니다. 이 함수는 for 루프를 사용하여 두 번째 요소(i=1)부터 마지막 요소까지 입력 목록을 반복합니다. 각 요소에 대해 이 함수는 요소를 키 변수로 저장한 다음 while 루프를 사용하여 정렬된 하위 배열에서 키 요소를 왼쪽에 삽입할 올바른 위치를 찾습니다. 동안 루프는 키 요소의 올바른 위치를 찾을 때까지 더 큰 요소를 오른쪽으로 한 위치씩 이동합니다. 마지막으로 정렬된 하위 배열의 올바른 위치에 키 요소가 삽입됩니다.

삽입 정렬의 시간 복잡도는 O(n^2)이며, 여기서 n은 입력 목록의 길이입니다. 그러나 입력 목록이 이미 정렬된 경우 최상의 경우 시간 복잡도는 O(n)이며, 입력 목록을 제자리에서 정렬하기 때문에 공간 복잡도는 O(1)입니다.

 

 

삽입 정렬은 입력 크기가 작거나 입력이 이미 부분적으로 정렬되어 있는 경우에 자주 사용되는 간단하고 효율적인 정렬 알고리즘입니다. 삽입 정렬의 일반적인 사용 사례는 다음과 같습니다

• 작은 배열 또는 목록 정렬: 삽입 정렬은 시간 복잡도가 O(n^2)이므로 입력 크기가 큰 경우 병합 정렬이나 퀵 정렬과 같은 다른 정렬 알고리즘보다 효율성이 떨어집니다. 그러나 입력 크기가 작은 경우 삽입 정렬은 매우 효율적일 수 있으며, 단순하고 오버헤드가 적기 때문에 다른 정렬 알고리즘보다 성능이 뛰어날 수도 있습니다.
•  부분 정렬된 배열 또는 목록 정렬: 입력 배열이나 목록이 이미 부분적으로 정렬된 경우 삽입 정렬은 이 사실을 활용하여 다른 알고리즘보다 더 효율적으로 정렬을 수행할 수 있습니다. 이 경우 삽입 정렬의 시간 복잡도는 O(n^2)보다 O(n)에 가까워질 수 있습니다.
•  온라인 정렬: 삽입 정렬은 온라인 알고리즘으로, 한 번에 한 요소씩 입력을 받으면서 목록을 정렬할 수 있습니다. 따라서 전체 목록을 미리 알 수 없거나 목록이 계속 업데이트되는 경우에 유용합니다.
•  알고리즘 설계 및 분석 교육: 삽입 정렬은 컴퓨터 과학 입문 과정에서 기본 알고리즘 설계 및 분석 기법을 설명하기 위한 교육 도구로 자주 사용되는 간단한 알고리즘입니다.