[python] 알고리즘 - 삽입 정렬(Insertion Sort)

삽입 정렬(Insrtion Sort)

출처: https://visualgo.net/en

 

 

삽입 정렬 역시 이중 루프로 구현할 수 있다. 가장 바깥 루프는 배열의 데이터를 순차적으로 선택하는 역할이며 안쪽 루프는 실질적으로 데이터를 비교하고 자리를 교체하는 역할을 수행한다.

 

1회 루틴 과정 -> 바깥 포 문은 배열의 인덱스를 오름차순으로 선택해 나간다. 이때 바깥 포문이 다음 데이터로 넘어가기 전에 안쪽 포 문은 현재 선택한 데이터를 배열 속에서 역방향으로 비교한다. 만약 이전 값이 현재 선택한 데이터 보다 큰 경우 두 데이터의 인덱스를 교체한다. 이를 반복한다. 위 이미지를 참고하면 쉽게 이해할 수 있다.

 

 

#Insertion Sort
def Insertion_Sort(array):
    for a in range(1, len(array)):
        for b in range(a, 0, -1):
            if array[b] < array[b-1]:
                   array[b], array[b-1] = array[b-1], array[b]
            else:
                   break
    return array


#Test Code
import random
array = random.sample(range(100), 10)

print(array)
print(Insertion_Sort(array))