[C/C++][algorithm] 삽입정렬

삽입정렬 : 아직 정렬하지 않은 부분의 첫 번째 요소를, 정렬된 열의 알맞은 위치에 삽입

정렬되지 않은 부분의 첫 번째 요소를 바로 옆 요소와 비교해 가면서 이동 

 

6 4 1 7 3 9 

 

4 6 1 7 3 9  

4 1 6 7 3 9 

1 4 6 7 3 9  

 

1 4 6 7 3 9  

 

1 4 6 7 3 9  

1 4 6 3 7 9 

1 4 3 6 7 9

1 3 4 6 7 9 

 

1 3 4 6 7 9

 

구현

#include <stdio.h>

int main() {
int n, data[100];
  scanf("%d", &n);
  for(int i =0; i<n; i++){
    scanf("%d", &data[i]);
  }
  
  for(int i =0; i<n; i++){
    
    for(int j=i ; j > 0 ; j--){
      if(data[j-1] >data[j] ){
        int temp;
        temp = data[j-1];
        data[j-1] = data[j];
        data[j] = temp;
      } else break;
    }
  }
  
  for(int i = 0; i<n ; i++){
    printf("%d", data[i]);
  }
  return 0;
}