삽입 정렬 (Insertion sort)

삽입 정렬이란?(오름차순일때) 자기보다 앞에 있는 값 들을 하나씩 순회하면서, 자기보다 큰 값이 나오거나 or 시작인덱스가 나오면 한번에 그 지점으로 삽입하는 방식이다.  

 

자기가 최대한 앞으로 갈 수 있을 만한곳을 찾아서 한번에 그 지점으로 들어가 버린다.

 

자기 앞의 값 이랑 비교하여 바로바로 바꾸는 버블정렬이랑 비교된다.

"그렇게 매번 하나씩 비교하고, 하나씩 바꾸고 어느 세월에 다 해? 그냥 그 앞에 거랑 싹 다 비교해서 한번에 배치해!"

라고 하는 것이 삽입 정렬의 전략이라고 할 수 있다.

 

다음은 [ 3, 7, 9, 4 ,1, 6 ]의 값에서 4가 삽입정렬 되는 차례의 과정이다.

여기서 숫자가 나타내는 것은 값이고, 가장 왼쪽 값인 3의 인덱스는 0이다.

 

 

 

 

이러한 과정을 모든 값에 대해 앞에서 부터 차례대로(시작 인덱스는 비교할 값이 없으니 패스) 수행하여 정렬 하는게 바로 삽입정렬이다.

 

나무위키에서의 삽입정렬 정의

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

 

코드

for index in range(데이터길이 - 1):

    for index2 in range(index+1,0,-1):

        if data[index2] < data[index2-1]:

            swap(data[index2], data[index2-1])

        else:

            break