🧪삽입정렬 알고리즘 연습

이전 포스팅에 코드상 문제가 있어서 다시 포스팅을 한다.

삽입 정렬은 앞과 뒤를 비교하여 작은 값을 좌측으로 삽입시키는 방식이다. 그래서 i는 두 번째 for문의 범위의 기준을 정하는 범위이기에 1부터 시작을 한다. 그리고 j의 값은 i-1인 좌측 앞부분의 값을 가지고와 역순으로 진행을 한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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

    print(f"[{i}]")

    for j in range(i-1, 0, -1):  # 왜 역순인지 이해가 안감..

        # print(j)

        print(f"{array[j]} < {array[j-1]}")

        if array[j] < array[j-1]:  # i번째랑 바꾸면 기준인 i의 값과 혼동이 된다.

            array[j-1], array[j] = array[j], array[j-1]

        else:

            break

        print(array)

# print(array)

 

[1] # 첫 번째 배열에서의 범위가 0과 0이기에 문자열을 읽을 수 없다.

------------------------------------
[2]  
5 < 7
[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

------------------------------------
[3]
9 < 7 # false이기 때문에 교체가 이루어지지 않는다.

------------------------------------
[4]
0 < 9
[5, 7, 0, 9, 3, 1, 6, 2, 4, 8]
0 < 7
[5, 0, 7, 9, 3, 1, 6, 2, 4, 8]
0 < 5
[0, 5, 7, 9, 3, 1, 6, 2, 4, 8]

------------------------------------
[5]
3 < 9
[0, 5, 7, 3, 9, 1, 6, 2, 4, 8]
3 < 7
[0, 5, 3, 7, 9, 1, 6, 2, 4, 8]
3 < 5
[0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
3 < 0

------------------------------------
[6]
1 < 9
[0, 3, 5, 7, 1, 9, 6, 2, 4, 8]
1 < 7
[0, 3, 5, 1, 7, 9, 6, 2, 4, 8]
1 < 5
[0, 3, 1, 5, 7, 9, 6, 2, 4, 8]
1 < 3
[0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
1 < 0

------------------------------------
[7]
6 < 9
[0, 1, 3, 5, 7, 6, 9, 2, 4, 8]
6 < 7
[0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
6 < 5

------------------------------------
[8]
2 < 9
[0, 1, 3, 5, 6, 7, 2, 9, 4, 8]
2 < 7
[0, 1, 3, 5, 6, 2, 7, 9, 4, 8]
2 < 6
[0, 1, 3, 5, 2, 6, 7, 9, 4, 8]
2 < 5
[0, 1, 3, 2, 5, 6, 7, 9, 4, 8]
2 < 3
[0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
2 < 1

------------------------------------
[9]
4 < 9
[0, 1, 2, 3, 5, 6, 7, 4, 9, 8]
4 < 7
[0, 1, 2, 3, 5, 6, 4, 7, 9, 8]
4 < 6
[0, 1, 2, 3, 5, 4, 6, 7, 9, 8]
4 < 5
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
4 < 3

첫 번째 for문 기준으로 인자를 전달 받았을 때의 모습

첫 번째 for문의 시작은 1이다. 결국 인자 7을 제외하고 idx 1부터 시작이다. 하지만 두 번째 for문에서 시작은 i -1부터 시작을 한다. 결국 시작과 끝은 0과 0이기에 if문에 해당 되지 않아 아무 값을 반환하지 않는다. 다음 번째로 돌렸을 때의 모습은 아래와 같다.

그렇게 첫 번째 for문을 기준으로 좌측과 계속해서 비교를 하고 비교시 해당 if문 조건에 충족을하면 서로 swap을 하게 된다. 그렇게 첫 번째 for문의 범위가 넓어지면 두번째 for문에서 모든 값들을 비교하면서 하나 하나 조건에 맞는지 분석하는 것이다.

오름차순이 아닌 내림 차순으로도 만들어보기

N = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for std in range(1, len(N)):  # 5(2)

    for j in range(std, 0, -1):  # 역순으로 감소(차감)하면서

        print(j, end=" ")

        if N[j] < N[j-1]:  # 앞과 뒤를 살피면서 왼쪽으로 당겨야한다.

            N[j], N[j-1] = N[j-1], N[j]

    print(N)

 

1 [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
2 1 [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
3 2 1 [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
4 3 2 1 [0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
5 4 3 2 1 [0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
6 5 4 3 2 1 [0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
7 6 5 4 3 2 1 [0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
8 7 6 5 4 3 2 1 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
9 8 7 6 5 4 3 2 1 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

삽입정렬과 선택정렬의 차이는 선택정렬은 전체적인 범위를 모두 훑어 보면서 가장 큰 값을 찾고 그 값을 맨 뒤(오른쪽)으로 밀려가면서 재 정렬을 한다. 하지만 삽입정렬은 하나의 기준을 정해서 역으로(기준으로 index 0까지) 살펴보면서 값들을 좌측으로 당겨가며 재정렬을 한다.

위의 방식도 있지만 정 방향으로 값을 훑어보는 방식도 있다.

 

N = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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

    std = i  # 5

    for j in range(len(N)):

        if N[std] < N[j]:

            N[std], N[j] = N[j], N[std]

    print(N)