매일 매일 새로운 복잡한 소재를 공부해야하는 불쌍한 알고리즘 수강생들에게 익숙한 소재를 선사한다.

바로 삽입 정렬이다. 삽입 정렬은 대부분 알고 있겠지만, 모르는 사람들을 위해 예시를 하나 들어보자.

배열 arr이 [4, 2, 3, 1]이고, 이것을 정렬하고자 한다.

[4, ~~2, 3, 1~~] //4가 삽입되면서 첫 번째 자리를 지킨다.

[2, 4, ~~3, 1~~] //2가 삽입되면서, 4를 밀어내고 첫 번째 자리로 이동한다.

[2, 3, 4, 1] //3이 삽입되면서 4를 밀어내고 두 번째 자리로 이동한다.

[1, 2, 3, 4] //1이 삽입되면서 4, 3, 2를 각각 밀어내고 첫째 자리로 간다.

총 교환(밀어내기)수: 1+1+3 = 5

배열이 주어질 때 그 배열을 삽입 정렬할때의 교환(밀어내기)의 수의 총합을 구하여라.

삽입 정렬 심층분석 timer 1s memory 256MB

삽입 정렬 심층분석 1s 256MB