삽입정렬

삽입정렬

• 2번째 자료부터 자기 바로 왼쪽 부터 index가 0이 될때까지 비교하는 방법.
• [2,5,3,4,1]
• • 첫번째로 5(2번째 자료)가 선택되어 진다.
  • <- 왼쪽방향인 2와 비교 후 자리를 정렬 (5가 더 큼으로 변함 없음)
  • ===========1회전 종료=============
  • 두번 째, 3 (3번째 자료)가 선택된다.
  • <-옆인 5와 비교, 자리를 바꾼다. (2,3,5,4,1)
  • <-옆인 2와 비교, 자리를 안바꾼다.
  • ===========2회전 종료=============
  • 세번 째, 4가 선택된다.
  • <-옆인 5와 비교 해서 자리를 바꾼다 (2,3,4,5,1)
  • 자리가 안바뀐다
  • ==========3회전 종료==============
  • 4번째 1이 선택되어진다.
  • <-5와 비교, 자리를 바꾼다
  • <-4와 비교, 자리를 바꾼다
  • <-3 , <-2 .. 비교
  • 최종 [1,2,3,4,5]
  • ===========4회전 종료============

for(int i=1; i<n; i++){

    

    int key = list[i];

    for(j= i-1; j>=0 && list[j] > key ; j-- ){

        list[j+1] = list[j]; 

    }

    list[j+1] = key;

}