삽입 정렬

1. 삽입 정렬이란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘이다.

삽입 정렬은 두 번째부터 시작하고, 키를 기준으로 앞의 데이터가 큰지 작은지 비교하여 자신의 위치를 정한다.

 

2.  과 정

정렬하려는 수 : [ 5, 4, 2, 1, 7 ]

① 1번째 단계] key : 4

∴ 결과 : [ 4, 5, 2, 1, 7 ]

② 2번째 단계] key : 2

∴ 결과 : [ 4, 2, 5, 1, 7 ] → [ 2, 4, 5, 1, 7 ]

③ 3번째 단계] key : 1

∴ 결과 : [ 2, 4, 1, 5, 7 ] → [ 2, 1, 4, 5, 7 ] → [ 1, 2, 4, 5, 7 ]

④ 4번째 단계] key : 7

key가 7인 경우에 이미 정렬이 끝났기 때문에 종료된다.

∴ 결과 : [ 1, 2, 4, 5, 7 ]

 

3. 파이썬 코드

사용자로부터 입력받은 n개의 수를 오름차순으로 삽입 정렬 코드이다.

def insert(E):
    for i in range(1, len(E)):
        key = E[i]
        j = i-1

        while(j>=0 and key<E[j]):
            if E[j] > key:
                E.insert(j, key)
                del E[j+2]
            j = j-1

        print("key : ", key)

def main():
    lst = map(int, input("숫자 입력 : ").split())
    E =[]
    for e in lst:
        E.append(e)

    result = insert(E)
    print(result)

if __name__ == '__main__':
    main()

 

4. 실행 결과