• unserted list에서 하나의 record를 뽑아서 이를 insert하면서 sorting하며 sorted list를 만드는 것

• 처음에 27은 이미 sorting된 부분임
• 4는 unsorted part이다.
• 4를 집어서 27앞으로 보내고 그 다음 21을 택한다.
• 21을 27 앞으로 보내고 그 다음 38을 택한다.
• 38은 그대로 두고 1을 택한다.
• 1은 4앞으로 보내고 12를 택한다
• 12는 21앞으로 보낸다.

• Key가 1이고 j=5라고 할 때
  • i는 하나씩 줄어가면서 비교한다.
  • A[i]와 key를 비교하면서 A[i]가 크면 copy하고 그렇지 않으면 stop한다.
    • i=4인 경우, 38과 1을 비교하고 38이 1보다 크므로 38을 copy한다.
    • i=3인 경우, 27과 1을 비교하고 key가 더 작으니까 27을 copy한다.
    • i=2인 경우, 21과 1을 비교하고 key가 더 작으니까 21을 copy한다.
    • i=1인 경우 4와 1을 비교하고 key가 더 작으니까 4를 copy한다.
    • i=0인 경우는 array의 바깥으로 벗어났다는 것을 의미한다.

pseudocode

Insertion-Sort(A);
	for j<-2 to length(A)
		do key <- A[j]
			> Insert A[j] into the sorted sequence A[1..j-1].
			i <- j-1;
			while i > 0 and A[i] > key
				do A[i+1] <- A[i];
					i <- i-1;
			A[i+1} <- key;

• 알고리즘을 디자인하는 과정
• 특별한 디자인 패러다임.
  • j는 2부터 시작하고, length(A)=n이다.
  • 배열 A는 이미 sort 상태에 있는 것을 자리를 잡아서 집어넣는 것이다.
  • i는 j를 하나씩 감소한 값이다.
  • i가 인덱스를 벗어나지 않고, A[i]가 key보다 크면, 값을 copy하고 i값을 감소한다.