#1. 삽입정렬

 

삽입정렬

 

정렬되지 않은 배열에서 값을 선택하여 적절한 위치에 삽입하는 방식으로 작동.

 

작은 규모의 배열에서 효율적인데, 비교 연산을 줄일 수 있습니다.

 

 

 

우선 insertion_sort 함수를 정의합니다.

for 문을 통해 'arr'의 각 원소를 순회하면서 정렬을 수행합니다.

 

key에는 현재 원소의 값을 '저장' 하고 j에는 현재 원소 이전 '인덱스'를 저장합니다.

 

while 문을 이용해서 이전 원소와 비교하며 key의 위치를 찾아갑니다.

j 변수가 0 이상이고 이전 원소가 key 보다 크면, 이전 원소를 현재 위치로 이동시키고 j 변수를 1 감소 시킵니다.

글만 보면 어려우니 한문장씩 코드에 대입하며 보아요

 

while문이 종료되면 key의 위치가 결정됩니다.

이전 원소 중 key보다 작거나 같은 값의 다음 인덱스에 key를 삽입합니다.