[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 13

* 수업은 JS 기반이지만 Python으로 구현

Section 13

삽입 정렬: 소개

삽입 정렬은 점차적으로 반 이상을 정렬하는 방식이다. 한 번에 하나의 항목을 올바른 위치에 삽입해 배열의 정렬된 부분을 점진적으로 구축한다. 거의 정렬이 되어 있다면 활용하기 좋고, 역순으로 되어있다면 활용하기 좋지 않다. 또한 온라인 알고리즘이라는, 새로운 데이터가 들어올 때마다 작동하며 새로운 데이터를 수신하므로 전체 배열을 한 번에 정렬할 필요가 없다. 정렬된 부분을 유지하고 적절한 위치에 새 항목을 삽입하는 것은 라이브, 스트리밍 방식으로 들어온 데이터를 즉시 입력해야 하는 상황에 편리하다.

삽입 정렬: 구현

• 배열의 두 번째 요소로 시작한다.
• 고른 요소를 앞의 요소들과 비교하여 필요하다면 바꾼다.
• 다음 요소 또한 정렬된 부분을 거치며 반복하며 잘못된 순서가 있다면 바꾼다.
• 배열을 정렬할 때 까지 반복한 후 배열을 반환한다.

# Insertion Sort
def Insertion(arr):
    
    # 배열의 두 번째 요소부터 마지막 요소까지 선택한다.
    for i in range(1, len(arr)):

        # 바꾸고 싶은 요소를 Ins에 배정하여
        # 루프 내 다른 요소와 비교한다.
        Ins = arr[i]

        # j 루프는 i-1번째부터 -1까지 하나씩 줄어든다.
        # -1까지 수행해야하는 이유는
        # j[j+1]요소에 입력값을 넣으므로
        # j[-1+1]의 상황인 j[0]의 상황까지 고려해야 하기 때문이다
        for j in range(i-1, -2, -1):

            # 잘 수행되는지 확인하는 부분
            print(i, j)

            # 만약 비교값이 기준값보다 크다면 자리를 바꾸어라
            if Ins < arr[j]:
                # 잘 수행되는지 확인하는 부분
                print(arr[j+1], arr[j], Ins)
                arr[j+1] = arr[j]
                print(arr)
            else:
                break

        # j 루프가 내부 조건에 따라 끝났거나 혹은 수행 조건에 따라 끝난 경우
        # Ins 값을 넣을 곳이 필요하다
        arr[j+1] = Ins

        # 잘 수행되는지 확인하는 부분
        print(arr)

    return arr
    
Insertion([2, 1, 9, 76, 4])
Insertion([33, 14, 223, 54, 21, 9, 0])

삽입 정렬: 빅오 복잡도

• 시간복잡도
  • Best: O(n)
  • Average: O(n^2)
  • Worst: O(n^2)
• 공간복잡도
  • O(1)