[정렬] 삽입정렬

안녕하세요. playground입니다~

이번에는 정렬 중 삽입정렬에 대해 포스팅하겠습니다.

 

 

 

 

삽입정렬

 

주어진 원소들을 하나씩 뽑고 나열된 원소들이 항상 정렬된 형태 를 가지도록

뽑은 원소를 바른 위치에 삽입 하여 나열하는 정렬.

 

역시나 글로 쓰면 너무나 감도 안 잡히고 헷갈리네요.

아래 자세히 알아보도록 하겠습니다.

 

 

 

 

 

삽입정렬의 원리

 

1. 위와 같은 원소가 있을 때 30을 꺼내서 배치합니다.

 

2. 30 뒤에 있는 50이라는 원소를 꺼낼건데요. 이 때 위치는 30보다 크므로 30의 뒤에 배치해줍니다.

 

3. 그 다음 입구에서 가까운 39를 뽑으려 하는데 이건 30과 50의 사이에 있으니 배치해줍니다.

 

이와 같은 방법으로 원소를 뽑아서 바른 위치에 삽입하다보면 아래와 같이 정렬이 됩니다.

 

이걸 바로 삽입정렬이라합니다.

그런데 뽑은 원소를 어떻게 바른 위치에 삽입할 수 있을까요?

컴퓨터는 나열된 원소를 하나씩 비교해가면서 위치를 찾아 정렬하는데 아래에 설명하도록 하겠습니다.

 

 

 

 

 

 

 

 

삽입정렬의 풀이

 

1. 위 배열에서 왼쪽부터 하나씩 뽑는다. 먼저 30을 뽑고 나열된 원소는 없으니 그대로 둔다.

 

 

 

 

 

2. 두 번째 원소인 50을 뽑고 나열된 원소와 비교해준다.

   현재 나열된 건 30이 있고 30보다 크므로 그대로 둔다.

 

 

 

 

 

3. 다음 원소인 7을 뽑아 나열된 원소 30과 50을 비교해준다.

   먼저 50과 비교해 7이 작으므로 교환, 그 다음 30과 비교해 작으므로 또 교환해주고 더 이상 비교할 나열된 원소가 없으므로 넘어간다.

 

 

 

 

 

4. 39원소를 뽑아 나열된 원소 7, 30, 50과 비교하는데 제일 처음으로 바로 옆에 있는 50과 비교해준다.

   39가 작으니 교환해주고 그 다음 30과 비교하는데 39가 더 크니 이대로 종료되고 넘어간다.

 

 

 

 

 

5. 같은 방법으로 진행하다가 마지막 원소인 85를 뽑고 나열된 원소들과 비교.

   제일 옆에 있는 99와 비교해 85가 작으므로 교환, 88과 비교해 교환하다가 77보다는 크니까 그대로 두고 정렬완료가 된다.

 

 

 

 

 

삽입정렬의 알고리즘

 

 

InsertionSort(int _iArr[], int _n) {      for(int i = 0; i < _n; ++i)             // 맨 왼쪽부터 시작      {           for(int j = i; j > 0; --j)            // 현재 i부터(j에 대입) 오른쪽으로 --하면서 비교해준다.           {                if( _iArr[j] > _iArr[j-1] )   // 현재 뽑은 j의 원소값이 j의 왼쪽보다 크면 교환할 필요가 없고 j포문 나가준다.                     break;                              int iTemp = _iArr[j];        // 그렇지 않다면 나열된 값이 작은것이므로 교환.                _iArr[j] = _iArr[j-1];                _iArr[j-1] = iTemp;            }       } }

 

 

 

 

 

 

 

삽입정렬의 성능

 

 

이중 루프로 구성되며 바깥 루프는 입력크기인 n과 비례합니다.

안쪽 루프는 조건에 따라 최소로는 상수, 최대로는 n에 비례해 

최선일 경우는  O(n) , 최악은 O(

) 이다.

 

 

 

 

 

 

 

삽입정렬에 대해 포스팅을 했는데요~ 도움이 되셨으면 좋겠습니다.

감사합니다~