Software, Computer Science/Data Structure & Algorithm
-
Insertion Sort(삽입정렬)Software, Computer Science/Data Structure & Algorithm 2014. 3. 6. 02:16
현재 보고 있는 Textbook에서 많은 정렬 알고리즘 중에 가장 처음 나오고 가장 쉬운 정렬 알고리즘이다 그러나 O(n^2)의 복잡도를 가져서 적은 양의 데이터를 정렬할때 유용하다. 또한 이미 정렬되어 있는 경우 매우 빠르게 동작한다. 간략하게 그림을 통한 예제를 살펴보면, (이미지 출처 : http://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC) 위의 그림의 설명을 구체적으로 풀어 쓰면, 1) 임의의 수 5개가 있는 수열에서 먼저 두번째 원소를 key값으로 정의한다. 2) 그 key값을 적절한 키의 왼쪽 값들과 비교했을때 왼쪽 값이 key 값 보다 크고, index값이 처음이 아닐때 왼쪽의 값들을 오른쪽으로 한칸씩 이동 한다 3) 왼쪽 ..