삽입정렬 복습(Insertion Sort)

오늘은 삽입정렬에 대해 또 알아보았습니다. 삽입정렬은 O(N^2)의 정렬 알고리즘 중에서도 가장 효율적인 알고리즘입니다. 특히 정렬이 되어있을때 가장 효과적입니다.

 

삽입정렬의 핵심은 '삽입을 하고자하는 원소 앞에 배열이 이미 정렬되어진 상태라고 가정' 하는 겁니다. 그러고 삽입하고자 하는 원소를 그 정렬된 배열 앞으로 삽입합니다. 

 

예를 들어보겠습니다. 

 

5 3 4 2 1 

 

이라는 배열이 존재합니다. 첫번째 원소를 선택합니다. 5는 첫번째 원소이기 때문에 이미 정렬이 되어있습니다. 

그럼 두번째 원소 3을 보겠습니다. 3이 들어갈 수 있는 두 곳이 있습니다. 

 

_5_ 3 4 2 1

 

여기서 3은 5보다 작이 때문에 앞 쪽 공간에 삽입됩니다. 

 

3 5 4 2 1

 

다음원소인 4의 들어갈 장소를 모색합니다. 

 

_3_5_4 21 1

 

다음과 같습니다. 4는 3보단 크고 5보단 작기 때문에 그 사이에 삽입됩니다.

 

3 4 5 2 1

 

다음 원소 2의 들어갈 장소를 모색합니다. 

 

_3_4_5_ 2 1

 

2는 3보다 작기 때문에 3의 앞쪽에 삽입합니다. 

 

2 3 4 5 1

 

마지막 원소인 1의 들어갈 장소를 모색합니다.

 

_2_3_4_5_ 1

 

1은 2보다 작기 때문에 2의 앞쪽에 삽입합니다.

 

1 2 3 4 5

 

 

정렬이 끝났습니다. 

 

삽입정렬은 '이미 앞쪽이 정렬되어 있다 가정' 과 '넣을 수 있는 곳에 삽입' 이 효율적인 알고리즘이 되게 합니다. 만약 정렬되어져 있는 상황이라면 거의 가장 효율적인 알고리즘이 될 수 있습니다. 물론 정렬이 역으로 되어있다면 이때는 버블 정렬과 비슷한 효율을 냅니다.(계속 정렬을 해주어야하기 때문이죠.)

 

 

 

그럼 구현을 C와 파이썬으로 해보겠습니다

파이썬 삽입정렬

 

c 삽입정렬

 

오늘도 수고 많으셨습니다.