Straight Insertion sort ( 단순 삽입 정렬 )/ C,C++

 

 

 

단순 삽입 정렬은 요약하자면

 

 

정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 정렬 알고리즘입니다.

 

 

 

 

아래와 같은 배열을 예로 들어보겠습니다.

 

6

3

2

1

5

9

10

 

 

 

 

단순 삽입 정렬은 2번째 요소부터 시작합니다. 2번째 요소인 3을 알맞은 위치에 배치하면

 

6

3

2

1

5

9

10

 

 

바로 앞 숫자인 6과 자리가 바꾸어집니다.

 

3

6

2

1

5

9

10

 

 

 

 

 

 

 

 

다음으로 3번째 요소인 2를 알맞은 위치에 배치하면

 

3

6

2

1

5

9

10

 

앞자리에 위치하던 3과 6이 뒤로 밀리고 2가 앞으로 오게됩니다.

2

3

6

1

5

9

10

 

 

 

이후에도 이와 같은 작업을 4번째 요소, 5번째 요소, ... , N - 1 번째 요소까지 반복하여

정렬을 마치게 됩니다.

 

 

 

 

 

 

이를 코드로 구현하려면 윗 문장의 '이와 같은 작업을 N - 1 번 반복한다' 를 코드로 짜야합니다. 

 

 

 

 

N - 1 번 반복한다는 for문으로 쉽게 구현할 수 있겠지만

 

'이와 같은 작업', 즉 알맞은 위치에 요소를 삽입하는 작업은 어떻게 구현할까요?

 

 

 

 

 

이와 같은 작업을 조금 더 자세히 설명하겠습니다.

 

 

 

 

 정렬되지 않은 부분의 첫 번째 요소를 선택한 뒤, ( 4 선택 ) 

 

2

6

8

4

5

9

10

 

선택한 요소보다 앞쪽에 위치한 요소가 크면 그 값을 선택한 요소의 위치에 대입하고 

 

 

8이 4 보다 크므로 네번째 자리에 8 대입

2

6

8

8

5

9

10

 

 

그 앞쪽의 요소들과도 같은 작업을 반복하다,

 

 

 

6이 4보다 크므로 세번째 자리에  6 대입

2

6

6

8

5

9

10

 

 

선택한 값보다 작은 요소를 찾은 경우 반복을 중단하고 값을 배열에 대입합니다.

 

 

2는 4보다 작으므로 2번쨰 자리에 선택한 요소 대입

2

4

6

8

5

9

10

 

 

혹은 배열 맨 앞에 도달한 경우, 선택 요소를 배열 맨 앞에 대입하면 됩니다.

 

 

 

즉, 정렬되지 않은 부분의 첫 요소 위치를 저장해두고, 반복제어 변수(j)에 그 위치를 저장해둔 뒤에

 

1.  배열의 맨 앞에 도착하거나

2.  선택한 요소값보다 작은 값을 가진 요소가 나타날때까지

 

j값을 1 씩 줄여가며 반복문을 실행하면 됩니다.

 

 

구현 코드(C++)

 

 

• 요약

단순 삽입 정렬은 코드가 단순합니다. 하지만 O(n^2)의 시간복잡도로 효율적이지 못합니다.

그러니 정렬할 데이터가 (매우)적을때 쓸만한 정렬 알고리즘입니다.

 

장점 : 코드가 단순하여 정렬할 데이터가 적을때 쓰기 좋음

단점 : 시간복잡도가 O(n^2)으로 데이터량이 많아지면 매우 비효율적