[알고리즘] 삽입 정렬 Insertion Sort

삽입 정렬(Insertion Sort)

• 삽입 정렬은 정렬이 안된 부분의 숫자를 하나씩 정렬된 부분의 적절한 위치를 찾아 끼워 넣는 알고리즘

 

 

동작 원리

1. 리스트의 두 번째 요소부터 시작한다.
2. 현재 요소를 앞 요소들과 비교하여 올바른 위치를 찾고, 그 위치에 삽입한다.
3. 이 과정을 리스트의 끝까지 반복하여 정렬한다.

 

 

단계별 구현

1. 리스트의 두 번째 요소부터 끝까지 순회.
2. 현재 요소를 current_value로 설정하고, 현재 위치의 이전 위치를 position으로 설정한다.
3. current_value가 이전 요소보다 작으면 이전 요소를 한 칸씩 뒤로 이동한다.
4. current_value가 올바른 위치에 도달하면 삽입한다.

 

 

Python 파이썬 코드:

def insertionSort(lst: list) -> list:

    # 두 번째 요소부터 시작하여 리스트의 끝까지 순회
    for current_index in range(1, len(lst)):
        current_value = lst[current_index]  # 현재 정렬할 요소
        position = current_index - 1 # current_value와 비교할 앞 요소의 인덱스

        # current_value보다 큰 요소들은 한 칸씩 뒤로 이동
        while position >= 0 and lst[position] > current_value:
            lst[position + 1] = lst[position]
            position -= 1

        # current_value를 올바른 위치에 삽입
        lst[position + 1] = current_value

    return lst

def insertionSort(lst: list) -> list:

    # 두 번째 요소부터 시작하여 리스트의 끝까지 순회

    for current_index in range(1, len(lst)):

        current_value = lst[current_index]  # 현재 정렬할 요소

        position = current_index - 1 # current_value와 비교할 앞 요소의 인덱스

        # current_value보다 큰 요소들은 한 칸씩 뒤로 이동

        while position >= 0 and lst[position] > current_value:

            lst[position + 1] = lst[position]

            position -= 1

        # current_value를 올바른 위치에 삽입

        lst[position + 1] = current_value

    return lst

 

 

장단점

장점:

• 간단하고 직관적: 구현이 매우 간단하고, 이해하기 쉽다.
• 안정적: 동일한 값을 가지는 요소들의 상대적인 순서가 유지된다.
• 제자리 정렬: 추가적인 메모리 공간이 거의 필요하지 않다.

 

단점:

• 비효율적: 시간 복잡도가 O(n^2)로, 큰 데이터셋에는 비효율적이다.