Loop Invariant

알고리즘과 관련된 문제를 풀고 있는데...

기억하면 좋을만한 내용이 있어서 정리해본다.

Loop Invariant

• 루프안에서 원하는 속성이 유지되는지 확인해보는 방법
• 3가지를 통해서 속성이 유지되는지 확인해 볼 수 있다.
• Initialization : 루프를 돌기전 true 상태이다.
• Maintenance : 루프를 반복 후에도 true 상태이다.
• Termination : 루프는 종료될 수 있다.

이렇게 정리할 수 있는데... 이것을 InsertionSort에서 확인해본다면...?

for(int i = 1; i < A.length; i++){
//insertion sort code

여기에서 //insertion sort code 들어가는 것은

• sorting에서 시작되는 subarray는 정렬되어 있다.(i = 0, 정렬되어 있다)
• 루프를 돌고 나서는 subarray는 정렬되어 있는 상태이다.
• i = length -1 이 되면 종료된다.

이렇게 정리가 된다.

관련 url : https://www.hackerrank.com/challenges/correctness-invariant

끝.