삽입 정렬

https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4

https://m.blog.naver.com/ndb796/221226806398

4. 삽입 정렬(Insertion Sort)

 

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법이다.

검사하면서 비교에 따라 필요할 때만 위치를 바꾼다.

 

#include <iostream>
using namespace std;

int main(void)
{
  int i, j, tmp;
  int arr[10]={1,10,5,8,7,6,4,3,2,9};
  for(i=0; i<9; i++)
  {
    j=i;
    while(j>=0 && arr[j]<arr[j+1])
    {
      tmp=arr[j];
      arr[j]=arr[j+1];
      arr[j+1]=tmp;
      j--;
    }
  }

  for(i=0; i<10; i++)
  {
    cout << arr[i] << ' ';
  }
  return 0;
}

j는 검사자라고 생각하자. whlie에서 arr[j]<arr[j+1]에 따라 두 개의 값을 비교하고 두 번째 값이 크면 스와핑을 진행한다.

이때 j 값이 주어지고 while을 빠져나올때마다 j는 커진다. 따라서 검사하는 범위도 점점 커지는 것이다. 

이에 따라 j--는 i로 인해 커지는 j값을 while문 안에서 다시 줄여줌으로써 처음부분까지 검사를 진행하도록 한다.