입력값이 정렬되어 있는 경우, Dictionary Data Structure를 구현하는데 유용하다. 대표적으로는 Hasing, Lookup Table과 같은 방법을 사용 할 수 있다.
삽입 정렬은, 기본적으로 정렬된 집합의 엔트리를 점차 늘려가는 방식이다. 삽입 정렬의 최악의 경우 Ο(n^2)의 복잡도를 가진다. 그렇다면 평균 수행 시간은 어떻게 되는가? n개의 엔트리를 가지는 배열에서, i 위치에 있는 엔트리가 자기 자신의 위치를 찾는 연산 횟수를 생각해보자. 먼저, 전체 n 개의 엔트리이므로, 이 값이 특정 위치에 존재할 확률은 1/n이다. 그리고, 이 위치에서 소모된 연산 수는 SIGMA(FROM j = 1 TO n - 1)(j)이다.
여기서 생각해봐야 할 것은 i위치까지 왔을 때 결정 할 수 있는 엔트리의 적정 위치이다. i 위치에 도달했다면, i + 1의 위치의 값과 현재 자신의 값을 비교함으로써, 자신이 그대로 있어야 하는지, 아니면 i + 1 위치의 엔트리 값과 바꿔야 하는지를 결정 할 수 있다. 따라서, i 위치에서 소모되는 연산 횟수를 더 정확하게 정의한다면 다음과 같다.
(1 / i)(SIGMA(FROM j = 1 TO i - 1)j + (i - 1))
그리고, 이것이 전체 n 회만큼 루프를 돌거나 재귀적으로 호출되어야 하므로, 이들의 전체 합이 평균 수행 시간이 된다.
구체적으로 예를 들어보면, 다음과 같은 시퀀스의 입력이 있다고 하자.
22, 37, 15, 19, 12
이 경우, 삽입 정렬은 가장 왼쪽의 첫 레코드부터 정렬을 시작한다. 키 값이 22인 엔트리가 하나이므로, 이것은 이 자체로 정렬된 상태이다. 다음 단계에서는, 37을 보고 정렬된 시퀀스와 비교한다. 키 값 37은 이미 정렬된 시퀀스의 엔트리보다 큰 값이므로 정렬된 시퀀스에 위치 변경 없이 그대로 포함시킨다. 이로써 2개의 정렬된 시퀀스를 얻게된다. 다음 단계에서, 15는 이미 정렬된 시퀀스의 엔트리보다 더 작은 값을 가지므로, 15는 적절한 위치로 이동해야 한다. 이때, 이동 방법에는 2가지가 있다. 첫번째 방법은 15와 37의 자리를 바꾼 뒤에, 다시 15를 정렬된 왼쪽의 시퀀스 엔트리 키 값과 비교하는 방식이다. 여기서 정렬된 시퀀스의 엔트리 값이 현재 비교하고 있는 키 값보다 작다면 스왑은 계속해서 일어난다. 이러한 방식을 풀 스왑(Full Swap)이라 한다. 두번째 방법은 하프 스왑(Half Swap)이다. 15가 왼쪽 37보다 작다면 즉시 스왑하지 않고 정렬된 시퀀스의 키 값들을 계속 따라간다. 여전히 15가 22보다 작기 때문에 15의 위치는 계속 이동하며, 적절한 자신의 위치를 찾을 때까지 비교만 계속한다. 최종적으로 삽입 위치가 결정되면, 삽입 위치의 레코드를 포함하여 정렬된 시퀀스 엔트리의 위치를 차례대로 이동한 후에 해당 위치에 이 값을 삽입한다.
한번에 앞자리의 값과 비교하는 모델에서는 최악의 경우 (n^2) / 2보다 나은 성능을 보일 수 없으며, 평균 수행 시간은 (n^2) / 4 보다 더 향상 될 수 없다. 실제 컴퓨터 모델에서는 임의의 위치의 엔트리 값에 접근 할 수 있기 때문에, 이것보다 훨씬 더 나은 결과를 보여주는 알고리즘을 작성 할 수 있다.
삽입 정렬은 이미 정렬된 데이터에 대해 최선의 효율을 보인다. 정렬된 상태에서 K번째 엔트리를 집어내어 왼쪽 것과 비교하면 집어낸 것이 더 크기 때문에, 더 이상 정렬된 시퀀스 그룹과 비교 할 필요가 없다. 단계의 수가 N인데, 단계마다 단 한번의 비교만 하기 때문에 이 경우에 효율은 Ο(N)이 된다.
삽입 정렬은, 기본적으로 정렬된 집합의 엔트리를 점차 늘려가는 방식이다. 삽입 정렬의 최악의 경우 Ο(n^2)의 복잡도를 가진다. 그렇다면 평균 수행 시간은 어떻게 되는가? n개의 엔트리를 가지는 배열에서, i 위치에 있는 엔트리가 자기 자신의 위치를 찾는 연산 횟수를 생각해보자. 먼저, 전체 n 개의 엔트리이므로, 이 값이 특정 위치에 존재할 확률은 1/n이다. 그리고, 이 위치에서 소모된 연산 수는 SIGMA(FROM j = 1 TO n - 1)(j)이다.
여기서 생각해봐야 할 것은 i위치까지 왔을 때 결정 할 수 있는 엔트리의 적정 위치이다. i 위치에 도달했다면, i + 1의 위치의 값과 현재 자신의 값을 비교함으로써, 자신이 그대로 있어야 하는지, 아니면 i + 1 위치의 엔트리 값과 바꿔야 하는지를 결정 할 수 있다. 따라서, i 위치에서 소모되는 연산 횟수를 더 정확하게 정의한다면 다음과 같다.
(1 / i)(SIGMA(FROM j = 1 TO i - 1)j + (i - 1))
그리고, 이것이 전체 n 회만큼 루프를 돌거나 재귀적으로 호출되어야 하므로, 이들의 전체 합이 평균 수행 시간이 된다.
구체적으로 예를 들어보면, 다음과 같은 시퀀스의 입력이 있다고 하자.
22, 37, 15, 19, 12
이 경우, 삽입 정렬은 가장 왼쪽의 첫 레코드부터 정렬을 시작한다. 키 값이 22인 엔트리가 하나이므로, 이것은 이 자체로 정렬된 상태이다. 다음 단계에서는, 37을 보고 정렬된 시퀀스와 비교한다. 키 값 37은 이미 정렬된 시퀀스의 엔트리보다 큰 값이므로 정렬된 시퀀스에 위치 변경 없이 그대로 포함시킨다. 이로써 2개의 정렬된 시퀀스를 얻게된다. 다음 단계에서, 15는 이미 정렬된 시퀀스의 엔트리보다 더 작은 값을 가지므로, 15는 적절한 위치로 이동해야 한다. 이때, 이동 방법에는 2가지가 있다. 첫번째 방법은 15와 37의 자리를 바꾼 뒤에, 다시 15를 정렬된 왼쪽의 시퀀스 엔트리 키 값과 비교하는 방식이다. 여기서 정렬된 시퀀스의 엔트리 값이 현재 비교하고 있는 키 값보다 작다면 스왑은 계속해서 일어난다. 이러한 방식을 풀 스왑(Full Swap)이라 한다. 두번째 방법은 하프 스왑(Half Swap)이다. 15가 왼쪽 37보다 작다면 즉시 스왑하지 않고 정렬된 시퀀스의 키 값들을 계속 따라간다. 여전히 15가 22보다 작기 때문에 15의 위치는 계속 이동하며, 적절한 자신의 위치를 찾을 때까지 비교만 계속한다. 최종적으로 삽입 위치가 결정되면, 삽입 위치의 레코드를 포함하여 정렬된 시퀀스 엔트리의 위치를 차례대로 이동한 후에 해당 위치에 이 값을 삽입한다.
한번에 앞자리의 값과 비교하는 모델에서는 최악의 경우 (n^2) / 2보다 나은 성능을 보일 수 없으며, 평균 수행 시간은 (n^2) / 4 보다 더 향상 될 수 없다. 실제 컴퓨터 모델에서는 임의의 위치의 엔트리 값에 접근 할 수 있기 때문에, 이것보다 훨씬 더 나은 결과를 보여주는 알고리즘을 작성 할 수 있다.
삽입 정렬은 이미 정렬된 데이터에 대해 최선의 효율을 보인다. 정렬된 상태에서 K번째 엔트리를 집어내어 왼쪽 것과 비교하면 집어낸 것이 더 크기 때문에, 더 이상 정렬된 시퀀스 그룹과 비교 할 필요가 없다. 단계의 수가 N인데, 단계마다 단 한번의 비교만 하기 때문에 이 경우에 효율은 Ο(N)이 된다.