알고리즘 #1 - 정렬 문제 #1 - Insertion Sort #1

이제와서 왠 알고리즘 !? ^^

나름의 이유로 알고리즘을 차분히 조금은 깊게 살펴볼 이유가 있어서 정리를 해보고자 한다.

 

우선 알고리즘에서 가장 대표적인 문제 유형은 바로 정렬(sort)이다.

크기가 다른 여러 개의 입력값이 있을 때, 이를 크기 순서대로 줄을 세워야 하는 문제이다.

 

<made by ChatGPT>

 

정렬 문제(Sorting Problem)를 해결할 수 있는 알고리즘(Algorithm)은 상당히 다양한데,

그 중에서 가장 첫번째로 언급되는 것이 바로 '삽입 정렬(Insertion Sort)'이다.

 

삽입 정렬을 한 번에 확인하기 위한 가장 좋은 예시는

위키피디아에서 보여주는 에니메이션이다.

<출처: https://en.wikipedia.org/wiki/Insertion_sort>

 

찬찬히 잘 살펴보면 어떻게 하겠다라는 것인지 충분히 이해할 수 있겠지만

그래도 좀 더 설명을 해보자면 다음과 같다.

 

<출처: https://www.whatwant.com>

 

6번째까지 정렬이 된 상태에서 (1, 3, 5, 6, 7, 8), 7번째 '2' 순서가 되었을 때를 설명해보려고 한다.

일단, 자기 자신의 앞에 있는 '8'과 비교했더니 나(2)보다 큰 값이기에 '8'을 한 칸 앞으로 옮긴다.

그 다음에는 하나 더 앞에 있는 '7'과 비교를 하고 옮기고 ... 그렇게 진행하다가

'1'을 만나게 되는데, 이번에는 '2'보다 작은 값이기에 자기 자신(2)이 '1' 뒤에 위치하면 된다.

 

'Pseudo Code'는 다음과 같다.

 

 for j = 2 to A.length

     key = A[j]

     i = j - 1

     while i > 0 and A[i] > key

         A[i+1] = A[i]

         i = i - 1

     A[i+1] = key

 

 

2번째 입력값부터 시작해서 마지막 입력까지 수행을 해야 하는 것이고

기준이 되는 값을 일단 'key'에 저장해놓고,

key랑 비교를 시작할 위치는 key보다 하나 앞선 값이다.

이제 앞에 있는 값들과 비교를 해보고 비교한 값이 크면 비교한 값을 뒤로 한 칸 옮기고

같거나 작으면 비교를 멈추고 거기에 key값을 넣어주면 된다.

 

Python으로 작성해본 코드는 다음과 같다.

Pseudo code와 거의 동일하다.

 

def insertion_sort(arr):

    for i in range(1, len(arr)):

        key = arr[i]

        j = i - 1

        while j >= 0 and key < arr[j]:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key

 

    return arr

numbers = [6, 5, 3, 1, 8, 7, 2, 4]

sorted_numbers = insertion_sort(numbers)

print(sorted_numbers)

 

 

뭐 당연히 결과는 잘 나온다.

 

 

자~ 이제 시작이다.

살펴봐야할 많은 것들이 있다.

 

과연 이 알고리즘은 얼마의 시간이 걸릴 것이며, 얼마의 메모리가 필요하고,

Best Case일 때와 Worst Case일 때 어떻게 되는지를 살펴봐야 한다.

거기에다가 하나 더 알아봐야 할 것은 입력값들의 순서가 유지되는지에 대해서도 알아봐야 한다.

 

하지만, 벌써부터 지칠 수 있으니

다음 기회로.... ^^ (절대 귀찮아서 미루는 것이 아니다! 절대로! 절대로?)