삽입 정렬.

배열 구조를 어떻게 사용할 수 있는지 이해하는 가장 좋은 방법은 실제 알고리즘을 검토하는 것입니다.

• 삽입 정렬(insertion sort) 은 배열의 값을 정렬하는 알고리즘으로, 순서를 정할 수 있는 모든 유형의 값에서 작동합니다.
  • 정수, 문자열, 심지어 유통기한에 따라 저장된 창고 안 커피까지 삽입 정렬로 정렬할 수 있습니다.

삽입 정렬은 배열의 일부를 정렬하고, 이 정렬된 범위를 전체 배열이 정렬될 때까지 확장합니다.

• 알고리즘은 정렬되지 않은 배열의 각 원소를 반복하면서 정렬된 부분의 올바른 위치로 이동합니다.

i의 반복을 시작하는 시점에 i-1 이하의 위치에 있는 원소는 모두 정렬되 있습니다.

• 알고리즘은 이제 인덱스 i에 있는 원소를 선택하고, 정렬된 접두사에서 이 원소의 올바른 위치를 찾아 나머지 원소를 뒤로 이동시켜서 선택한 원소가 들어갈 공간을 만든 수 삽입합니다.
  • 그러면 정렬된 접두사가 하나 더 커지면서 0에서 i까지 모든 상자가 정렬된 상태가 됩니다.
    • 처음에는 첫 번째 원소를 초기 정렬된 접두사로 선언하고 i = 1부터 반복을 시작할 수 있습니다.

커피 컬렉션을 신선도순으로 정렬하고 싶다고 합시다.

무엇보다 프리미엄 커피가 창고 깊숙이 박혀 있다 상해버리는 비극은 바람직하지 않습니다.

• 따라서 유통기한이 제일 짧게 남은 커피를 가장 앞쪽에 넣어서 쉽게 접근할 수 있게 해야합니다.

우선 커피백 하나를 정렬된 부분으로 선언하고, 이를 기준으로 정렬 범위를 설정함으로써 커피 정렬을 시작합니다.

• 그 다음에는 가장 앞쪽에서 두 번째 백부터 날짜를 비교해 정렬된 부분의 백보다 더 앞에 넣어야 할지를 판단합니다.
  • 위치를 바꿀 필요가 있는 경우엔 순서를 바꾸고, 그렇지 않은 경우엔 자리를 유지합니다.
    • 이제 자신 있게 맨 앞의 두 백이 정렬됐다고 말할 수 있습니다.

이렇게 부분적으로 정렬하는 과정을 마지막 백까지 진행하면서 위치를 바꾸는 작업을 반복하면, 커피 컬렉션을 완벽하게 정리할 수 있습니다.

아래 코드와 같이 중첩된 루프를 이용해 삽입 정렬을 구현할 수 있습니다.

InsertionSort(array: A):
    Integer: N = length(A)
    Integer: i = 1
    WHILE i < N: // 1
        Type: current = A[i]
        Integer: j = i - 1
            WHILE j >= 0 AND A[j] > current: // 2
                A[j + 1] = A[j]
                j = j - 1
            A[j + 1] = current
            i = i +1

• 바깥쪽 루프는 최초의 정렬되지 않은 원소인 인덱스 i가 1인 원소부터 시작하고 정렬되지 않은 범위에 있는 각 값을 반복합니다(1)
  • 안쪽 루프는 인덱스 j를 사용해 정렬된 접두사의 원소를 맨 뒤에서부터 하나씩 반복합니다(2)
    • 반복 각 단계에서 현재 값과 정렬된 접두사 안에 있는 인덱스 j의 값을 비교해 확인합니다.
    • j에 있는 원소가 더 크면 두 값의 순서가 잘못됐으므로 교환해야 합니다.
    • 현재 값을 별도의 변수인 current에 저장했기 때문에 이전 상자에서 데이터를 직접 복사합니다.
      • 즉, i번째와 j번째의 값을 완전히 교환할 필요가 없습니다.
      • 내부 루프는 현재 값을 배열의 맨 앞에 밀어넣거나 현재 값보다 이전 값이 더 작을 때까지만(이 경우가 바로 현재 값이 정렬된 접두사의 올바른 위치에 있음을 나타냅니다.) 계속 진행합니다.
        • 이제 내부 루프의 끝에서 현재 값을 올바른 위치에 쓰기만 하면 됩니다.
        • 바깥쪽 루프는 다음 정렬되지 않은 값으로 진행합니다.

아래 그림은 알고리즘이 어떻게 동작하는지 시각화해 보여줍니다.

• 각 줄은 반복 시작 시 배열의 상태를 보여줍니다.
  • 빨간색 상자는 현재 위치에 있는 원소를 나타내며, 화살표는 현재 위치의 원소를 삽입하면서 발생하는 이동을 나타냅니다.

삽입 정렬은 그렇게 효율적이지 않습니다.

• 배열에 원소를 삽입할 때, 상당 부분을 이동해야 할 수도 있습니다.
• 최악의 경우(worst-case), 알고리즘의 비용은 시퀀스 원소 수의 제곱에 비례합니다.
  • 즉, 최악의 경우 리스트의 모든 원소마다 앞의 모든 원소를 이동해야합니다.
    • 배열의 크기를 2배로 늘리면, 최악의 경우 비용이 4배 증가합니다.

그럼에도 불구하고 삽입 정렬은 배열이 어떻게 작동하는지 중요한 통찰을 제공합니다.

이 간단한 알고리즘은 인덱스를 사용해 원소레 직접 접근할 수 있어야 하며, 새 원소를 삽입할 때 값을 교환할 수 있어야 하며, 모든 원소를 반복(iteration)할 수 있어야 한다는 배열의 여러 특성을 보여줍니다.