[알고리즘] 삽입정렬의 개념 및 예시 정리

삽입정렬

시간복잡도는 n제곱으로 느린 편이지만 구현하기 쉽다.

코테에서 굳이 많이 사용하진 않지만 코딩인터뷰 관련하여 정렬에 대해 질문 대비하여 알아놓으면 좋다.

---

예시 설명 )

5개의 배열이 있고 오름차순으로 정렬을 할려고 한다. 

정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입정렬의 핵심이다.

 

1. 우선 1 인덱스의 값 52의 이전 인덱스 범위를 바라본다

23

52

32

12

45

52 와 23 을 비교할때 52가 크기 때문에 변함이 없고 다음으로 넘어간다.

 

2. 2 인덱스인 32 가 기준이 되고 그 이전 범위 포함하여 0 - 2 인덱스를 비교한다.  

23

52

32

12

45

 

32는 52보다 작기 때문에 52를 2 인덱스로 옮겨가고 32가 1 인덱스 자리로 넘어가게 된다.

(23은 32보다 작기때문에 옮겨갈 필요가 없다)

 

3. 인덱스 3 인 12가 기준이 되고 그 이전 범위 포함하여 0 - 3 인덱스를 비교한다.

23

32

53

12

45

23, 32, 53 중에 12가 가장 작기 때문에 23, 32, 53 각각 오른쪽 한칸씩 이동하게 된다. 

그렇게 되면 12가 가장 맨 왼쪽으로 가게 되고 4번째 표에서 위치를 확인할 수 있다.

 

4. 인덱스 4 인 45가 기준이 되고 이전 범위 포함하여 0 - 4 인덱스를 비교한다. 

12

23

32

53

45

45는 53가 비교하였을때 작고 32와 비교하였을때는 크기 때문에 그 사이로 들어가면 된다. 

그렇게 되면 53이 마지막 인덱스 자리인 4로 옮겨지고 45 값이 인덱스 3으로 옮겨진다. 

(32 보다 큰 값인걸 알기 때문에 그 이하로는 비교할 필요가 없다.)

 

 

12

23

32

45

53

위와 같이 최종적으로 오름차순 된 배열을 확인할 수 있고 위와같은 정렬 방법을 삽입정렬이라고 한다. 

 

n제곱의 시간 복잡도를 가지고 있지만 이진탐색등과 같은 탐색 알고리즘을 사용하여 logN 으로 변경이 가능하다. 

최악의 상황 : N 번째의 인덱스 앞 부분을 비교할 때 0번째 인덱스까지 비교하는 상황까지 가게 된다면 n제곱의 시간 복잡도.

위 최악의 상황을 대처할려면 비교하여 정렬된 앞부분의 인덱스 범위에서 중간 값들과 비교하여 진행하게 되면 전체에 대해 비교하지 않아도 된다.(앞의 인덱스 값들이 정렬이 되어 있어서 탐색 알고리즘 사용 가능)

 

아래 강의 들으며 정리한 내용입니다.