삽입 정렬(Insertion Sort)이란
- 필요할 때만 각각의 원소를 적절한 위치에 배치하는 정렬 알고리즘
- 반복문이 두번 중첩된 구조로 구현되므로 시간복잡도는 O(N^2). 따라서, 버블 정렬, 선택 정렬과 같은 시간복잡도를 가지므로 비교적 비효율적인 알고리즘일 수 있다.
- 정렬이 대부분 되어 있는 경우에서는 빠르고 효율적인 알고리즘이 된다.
코드로 표현하기
- 배열에 저장된 모든 원소를 인덱스 순서대로 모두 조회한다.
- 내부 while문에서는 현재 인덱스부터 첫 인덱스까지 조회한다.
- 현재 원소값(arr[j])보다 작은 값이 뒷쪽(arr[j+1])에 있다면 두 원소 위치를 바꾼다.(temp)
- 정렬이 한번 완료되고 나면 현 위치 앞쪽에는 항상 정렬된 값들만 존재해야한다.
#오름차순 정렬 예제
arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] #임의의 원소 배열
for i in range(len(arr)-1):
j = i
while j >= 0 and arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
j -=1
#결과 출력
for a in arr:
print(a, end=' ')
#내림차순 정렬 예제
arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] #임의의 원소 배열
for i in range(len(arr)-1):
j = i
while j >= 0 and arr[j] < arr[j+1]:
temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
j -=1
#결과 출력
for a in arr:
print(a, end=' ')