삽입 정렬이란 ?
삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.처음 Key 값은 두 번째 자료부터 시작한다.
출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
삽입 정렬의 수행시간
앞 장에서 다시 복습한 내용과 같이 삽입 정렬은 알고리즘이 수행된다. 삽입 정렬이 일반 버블 정렬과 선택 정렬과 다른 것은 데이터가 하나부터 점차 늘어나며 정렬된다는 것이다.
이미 정렬된 배열을 바탕으로 그 다음 수를 그 배열에 삽입하는 알고리즘이기 때문에 이미 정렬된 배열에 그 다음 수가 들어갈 자리가 없이 그대로 정렬되어 있는 위치에 존재한다면 굳이 연산을 수행하지 않는다. 따라서 최상의 경우(모든 숫자가 정렬되어 있는 경우) 버블 정렬의 고도화와 마찬가지로 Θ(n)의 수행시간을 갖게 된다.
평균 최악의 경우도 버블 정렬의 고도화와 마찬가지로 Θ(n2)의 수행시간을 갖는다.
상한(n2)을 넘지 않는 선에서 Θ(n)도 포함하는 알고리즘이기 때문에
T(n) = O(n2)으로도 정의할 수 있다.
삽입 정렬 구현
삽입 정렬의 알고리즘을 코드로 구현한 것이다. 버블 정렬의 고도화와 마찬가지로 10개의 데이터를 입력했을 때 45라는 상한 숫자를 넘지 않는 선에서 비슷한 범위에 횟수들이 카운트가 되었다.
삽입 정렬의 과정
알고리즘을 글로 읽는 것보다 직접 나의 코드에 연산이 수행되는 부분을 print하여 과정을 지켜보는 것이 더 공부가 될 것 같아 앞 장에 코드와 같이 정렬이 수행 될 때마다 그 과정을 print했다. 왼쪽부터 이미 정렬된 배열에 오른쪽에 있는 수가 삽입 되는 것을 볼 수 있었다.
추가로 삽입 정렬이 수행될 때 이미 존재하던 배열이 한 칸 씩 뒤로 밀리는 과정이 궁금하여 그 부분에도 printf를 사용해서 더 세부적이게 과정을 지켜봤다. 코드와 실행 화면을 비교하며 이해하니 더 쉬운 이해를 할 수 있었다. 한 칸 옆으로 복사하며 원본의 자리를 그 왼쪽 배열의 값으로 채우고 마지막 원본의 값은 새로 삽입될 데이터로 채우며 정렬되어 가는 과정임을 확실하게 이해할 수 있었다.
