/* 본 게시물은 ' 뇌를 자극하는 알고리즘 | with 박성현 ' 의 내용을 토대로 작성되었습니다. */
1. 삽입 정렬
삽입 정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 예시로 뒤섞여 있는 트럼프 카드를 순서대로 정리하는 모습을 생각해보면 이해하기 쉽다. 카드를 한 장씩 뽑앙 카드의 값에 따라 적절한 곳에 끼워 넣는 것을 반복하다 보면 결국에는 모든 카드가 순서대로 정리되는 것 처럼, 데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하다 보면 정렬된 데이터 집합을 얻을 수 있다.
삽입 정렬 과정은 다음과 같다. (정렬 기준은 오름차순으로 가정한다.)
- 인덱스가 1인 값부터 정렬을 시작한다. 인덱스가 1인 값을 임시 변수에 저장하고, 임시 변수와 인덱스가 0 인 값과 비교한다.
- 만약 인덱스가 0인 값이 크다면, 인덱스 1인 값에 인덱스가 0인 값을 넣고 임시 변수의 값을 인덱스 0인 자리에 삽입한다. 반대로, 인덱스가 0인 값이 작다면, 임시 변수 값이 들어갈 자리를 찾은 것이다.
- 삽입할 자리를 찾았다면, 루프를 탈출해 삽입할 자리에 임시 변수 값을 넣는다.
- 그 다음으로 인덱스가 2인 값을 정렬을 시작한다. 1~3 번을 데이터 사이즈 - 1 번 반복한다.
이를 일반화 시켜보자.
- 인덱스값이 i 인 데이터를 정렬한다고 가정해보자. 데이터[i] 값을 임시 변수에 저장한다. 임시 변수와 배열[i-1]과 비교한다.
- 만약 배열[i-1] 값이 임시 변수보다 크다면, 배열[i] 값에 배열[i-1] 값을 넣고, 배열[i-2]와 비교한다.
- 3번의 과정을 반복하다보면, 결국 임시 변수 값이 배열[i-j]보다 커질때 가 있다. (커질 때가 없으면 정렬 대상의 최솟값이다.) 임시변수가 들어갈 인덱스 값인 j+1 을 찾은 것이다!
- 임시 변수를 배열[j+1]에 삽입한다.
- 1~4번을 배열 사이즈 - 1 번 반복한다.
삽입 정렬 예시
fun insertSort(arr: Array<Int>) : Array<Int>{
var temp: Int
var j: Int
//n-1 번 실행 (카드 뽑기 횟수)
for (i in 1 until arr.size){
//1. 데이터 정렬 대상 선택 (카드 선택)
temp = arr[i]
j = i-1
// 삽입할 위치를 찾으면서 이전 값들을 땡겨옴
while (j >= 0 && arr[j] > temp){
arr[j+1] = arr[j]
j--
}
// 삽입할 위치에 값 삽입
arr[j+1] = temp
}
return arr
}
삽입 정렬 성능
첫 번째 정렬의 대상 범위가 2개 일 때 비교 1번, 대상 범위가 1개 증가하여 3개 일 때 비교 2번, ...마지막으로 대상 범위가 배열의 크기일 때 비교는 배열의 크기 - 1 이 된다.
여기서 알 수 있듯이, 삽입 정렬의 '최대' 비교 횟수는 1+2+3+...+n-1 = n(n-1)/2 이다.
그렇다면 버블 정렬/ 선택 정렬이랑 비교 횟수가 같다고 생각할 수 있다.
하지만 버블 정렬/ 선택 정렬에서는 반드시 n(n-1)/2 만큼의 비교를 하지만, 삽입 정렬은 데이터 집합이 정렬되어 있는 경우에는 한번의 비교를 수행한다.
예시로 이해하면, [1,2,3,4] 라는 정렬된 배열일 때 삽입 정렬의 비교 횟수는 1+1+1+1 =4가 될 것이다.
따라서 최선일 때나 최악일때나 성능이 똑같은 버블 정렬/ 선택 정렬 보다 평균적으로 삽입 정렬이 더 나은 성능을 보인다. 심지어, 구현의 난이도도 비슷하기 때문에 비교적 크기가 작은 데이터 집합을 정렬하는 루틴을 작성할 때는 버블 정렬 대신 삽입 정렬을 사용한 것이 더 효율적이다.
실행 결과
데이터 개수 10만개 기준으로 버블 정렬/ 선택 정렬/ 삽입 정렬 로 데이터를 정렬한 시간은 위 결과와 같다.
각 알고리즘 마다 시간 차이가 생각보다 많이 나서 놀랐다..
결론
'구현의 난이도도 비슷하기 때문에 비교적 크기가 작은 데이터 집합을 정렬하는 루틴을 작성할 때는 버블 정렬 대신 삽입 정렬을 사용한다'
