삽입 정렬 : insert sort

삽입 정렬은 정렬이 필요한 경우에만 알맞은 위치에 삽입하며 정렬한다.

시간복잡도는 O(N^2) 으로 버블 정렬,선택정렬과 동일하지만 일반적으로 두개의 정렬보다 더 빠르다.

 

진행 과정을 살펴보며 이해하자.

 

 정렬 과정 

 

 알고리즘 

 

1. 앞의 회색은 정렬된 배열이고 빨간색 수는 정렬 할 수이다.

2. 빨간색수를 정렬된 배열 맨뒤부터 값을 비교하며 대상 인덱스의 숫자보다 크면 앞으로 이동

3. 2번 과정을 반복하다가 더이상 이동이 없을시 정렬이 완료된것.

 

 코드 

 

#include<iostream>
 
using namespace std;
 
int main() {
   int arr[10] = { 1,10,5,8,7,6,2,4,3,9 };
   int idx, temp;
 
   cout << "정렬전 :";
   for (int i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl << "정렬후 : ";
 
//삽입정렬 알고리즘
 
   for (int i = 0; i < 9; i++) {
      int j = i;
      while (arr[j] > arr[j + 1]) {
         temp = arr[j];
         arr[j] = arr[j + 1];
         arr[j + 1] = temp;
         j--;
 
      }
      
   }
 
   for (int i = 0; i < 10; i++)
      cout << arr[i] << " ";
}

 

모든 글의 내용은 나동빈님 블로그를 참고 하였습니다.

https://blog.naver.com/ndb796/221228342808