1. 설명
삽입 정렬은 무작위로 된 데이터에서 이미 정렬되어 있는 데이터의 값과 비교하여 무작위로 된 데이터를 이미 정렬되어 있는 데이터의 적절한 위치에 삽입해서 정렬하는 알고리즘입니다.
사진 출처: https://github.com/GimunLee
-
무작위로 된 데이터에서 첫 번째 인덱스의 값은 정렬되어 있다고 가정합니다.
-
두 번째 인덱스의 값과 첫 번째 인덱스의 값을 비교합니다.
1) 두 번째 인덱스의 값이 첫 번째 인덱스의 값보다 클 때, 첫 번째 인덱스의 오른쪽에 삽입하고 정렬해 줍니다.
2) 두 번째 인덱스의 값이 첫 번째 인덱스의 값보다 작을 때, 첫 번째 인덱스의 왼쪽에 삽입하고 정렬해 줍니다. -
세 번째 인덱스의 값과 두 번째 인덱스의 값을 비교합니다.
1) 세 번째 인덱스의 값이 두 번째 인덱스의 값보다 클 때, 두 번째 인덱스의 오른쪽에 삽입하고 정렬해 줍니다.
2) 세 번째 인덱스의 값이 두 번째 인덱스의 값보다 작을 때, 두 번째 인덱스의 왼쪽에 삽입하고 정렬해 줍니다. 이어서 위의 두 번째 과정(두 번째 인덱스의 값과 첫 번째 인덱스의 값 비교)을 실행해 줍니다. -
위의 과정을 반복하여 줍니다.
해당 알고리즘은 선택 정렬보다 구현은 어려울 수 있습니다. 그러나 시간 복잡도(O(n^2), O(n)) 측면에서 상대적으로 효율적일 수 있습니다. 대표적으로 무작위로 된 데이터가 정렬되어 있을 때가 있습니다.
2. 코드
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break