삽입 정렬

https://unsplash.com/photos/Z2P3cQGNpsA

삽입 정렬에 대해 알아보자.

 

 

 

 

 

---

얻어갈 지식

• 삽입 정렬

 

 

 

 

 

삽입 정렬

 

작은 데이터 셋에 효율적이다.

삽입 정렬은 간단한 정렬 알고리즘이다.

어레이는 정렬된 부분과 정렬되지 않은 부분으로 나뉜다.

정렬되지 않은 어레이의 값이 선택되고 정렬된 어레이의 올바른 위치에 배치된다.

 

 

삽입 정렬 예시

• [ 12, 11, 13, 5, 6 ]이 있을 때
  
  
• 첫 번째 패스
  • 0 번째 값과 1 번째 값 비교
  • 12는 11보다 크므로 자리 바꿈
  • [ 11, 12, 13, 5, 6 ]
• 두 번째 패스
  • 1 번째 값과 2 번째 값 비교
  • 12는 13보다 작으므로 그대로 유지
  • [ 11, 12, 13, 5, 6 ]
    
    
• 세 번째 패스
  • 2 번째 값과 3 번째 값 비교
  • 13은 5보다 크므로 자리 스왑
  • 12는 5보다 크므로 자리 스왑
  • 11은 5보다 크므로 자리 스왑
  • [ 5, 11, 12, 13, 6 ]
    
    
• 네 번째 패스
  • 3 번째 값과 4 번째 값 비교
  • 13은 6보다 크므로 자리 스왑
  • 12는 6보다 크므로 자리 스왑
  • 11은 6보다 크므로 자리 스왑
  • 5는 6보다 작으므로 그대로 유지
  • [ 5, 6, 11, 12, 13 ]

 

 

코드로 작성

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

		while j >= 0 and key < arr[j]:
			arr[j+1] = arr[j]
			j -= 1
		arr[j+1] = key

 

 

시간 복잡도와 보조 공간

• 삽입 정렬의 시간 복잡도 O(N^2)
• 보조 공간 O(1)
• 요소가 역순으로 정렬된 경우 최대 시간이 걸린다.

 

 

 

 

 

---

https://www.geeksforgeeks.org/insertion-sort/

Insertion Sort - GeeksforGeeks