삽입 정렬

삽입 정렬(Insertion Sort)

⁠- 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에삽입해 나가는 알고리즘이다.     

- 데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하다 보면 정렬된 데이터 집합을 얻을 수 있다.

 

정렬방향을 오름차순이라고 가정한다.

 

1.  데이터 집합에서 정렬 대상이 되는 요소들을 선택한다.

    알고리즘 반복 횟수가 늘어날수록 정렬되는 데이터의 범위가 1씩 늘어난다.

    정렬대상의 최대 범위는 "데이터 집합의 크기 -1 이다."

 

2. 정렬대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인하고, 그렇지 않다면

   이 요소를 정렬 대상에서 뽑아내고, 이 요소가 위치할 곳을 찾는다.

  

3. 뽑아 든 요소의 위치를 찾았으면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로

    이동하고 새로 생긴 빈자리에 채워넣는다.

 

4.  데이터가 정렬될 때까지 이 과정을 모두 반복한다.

 

** 삽입 정렬은 버블 정렬보다 더 나은 성능을 보인다.

    정렬이 많은 데이터를 사용할 때는 삽입 정렬을 추천함.

 

​