[Python] 코딩 도장 - Insertion Sort

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: Insertion Sort] - Lv.2

위 그림은 {5,2,4,6,1,3} 이라는 배열을 소트하는 방법을 보여준다.

배열의 두번째 인덱스부터 시작하여 시작한 인덱스(검정색 블록) 좌측의 항목 중 자신이 들어가야 할 위치를 판단(소트되도록)하여 이동 한다.

좌측의 배열 요소들은 본인보다 좌측에 값이 삽입되어 들어올 경우 한칸씩 우측으로 이동한다.

단, 삽입되어 들어오는 요소(그림에서 검정색 블록)가 있던 인덱스(원래의 위치)까지만 이동한다.

마지막 인덱스까지 위 과정을 반복한다.

이와 같은 기능을 하는 소트 프로그램을 작성하시오.

출처: https://codingdojang.com/scode/443?answer_mode=hide

---

[풀이]

def Insertion_Sort(a):
    for k in range(1,len(a)+1):
        if k==1:
            print(k, ":", a)
            continue

        idx = [a.index(i) for i in sorted(a[:k])] + [a.index(i) for i in a[k:]]
        a = [a[i] for i in idx]
        print(k, ":", a)

a = [5, 2, 4, 6, 1, 3]
Insertion_Sort(a)

1 : [5, 2, 4, 6, 1, 3]
2 : [2, 5, 4, 6, 1, 3]
3 : [2, 4, 5, 6, 1, 3]
4 : [2, 4, 5, 6, 1, 3]
5 : [1, 2, 4, 5, 6, 3]
6 : [1, 2, 3, 4, 5, 6]

이 프로그램은 두 번째 인덱스부터 좌측의 모든 값들을 sort하고 뒤의 값은 그대로 출력된다.

그 후 인덱스를 세 번째, 네 번째로 이동하는 방식을 반복한다.

그래서 기존 배열의 앞에 2개의 값을 sort시 인덱스와 나머지 원래 인덱스를 합쳐 인덱스 순서로 배열을 재생성하였다.

이를 앞의 2개의 값에서 3개, 4개로 증가시켜 마지막까지 반복하였다.

코드 상으로는 index()가 주이며 sorted()를 사용한게 조금 걸리긴 한다.

---

[추천 풀이]

t0 = [5,2,4,6,1,3]
for i in range( 1, len(t0) ):
    for j in range( i ):
        while t0[i] < t0[j]:
            t0[i], t0[j] = t0[j], t0[i]
            
print(t0)

[1, 2, 3, 4, 5, 6]

우선 원래 풀이로 이렇게 올라왔는데 결과는 잘 정렬되었다.

이를 과정별로 살펴보자.

t0 = [5,2,4,6,1,3]
for i in range( 1, len(t0) ):
    for j in range( i ):
        while t0[i] < t0[j]:
            t0[i], t0[j] = t0[j], t0[i]
            
    print(t0)

[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6]

과정별로 보았을 때 (여기선 i 루프 별) 의도한 과정 순서대로 잘 나타난다.

어떻게 정렬이 되는지 자세히 알아보자.

t0 = [5,2,4,6,1,3]
for i in range( 1, len(t0) ):
    for j in range( i ):
        while t0[i] < t0[j]:
            t0[i], t0[j] = t0[j], t0[i]
            
        print(t0)

[2, 5, 4, 6, 1, 3]
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 4, 5, 6, 2, 3]
[1, 2, 5, 6, 4, 3]
[1, 2, 4, 6, 5, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 5, 6, 4]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 5, 6]

while 문에도 나와 있지만 결국 i번째 인덱스의 값이 i번째 인덱스 앞에 값보다 작다면 계속 교환을 하는 형태이다.

나는 sorted()를 사용해서 조금 걸렸는데 이런 방식으로 푸는게 더 좋아보이긴 한다.