Insertion Sort

main.c : 입력 값을 하드코딩한 버전

v1.main.c : 입력 값을 콘솔로 입력할 수 있도록 수정한 버전

insertion-sort.py : 해당 알고리즘을 파이썬으로 코딩한 버전 (역시 파이썬 짱 !!)

insertion sort
장점

1. 구현하기 쉽다.
2. 비교적 적은 데이터에서 손쉽게 사용할 수 있다
3. 주어진 메모리 내에서 정렬이 가능하다

단점

1. 정렬되어 있는 경우 값들이 다시 복사되는 문제점이 있다
2. selection-sort에 비해서 메모리 비교는 적지만, write 는 O(n²)의 복잡도를 가진다.
3. 결국 write에 고비용이 드는 EEPFROM, FlashMemory의 경우는 selection-sort쪽이 더 낳다. O(n)

insertion-sort using python

1. A = [ 5, 4, 3, 2, 1 ]
2. for i in range(1, len(A)):
   
   1. if i == 0:
      
      1. continue
   2. value = A[i]
   3. j = i - 1
   4. while j >= 0 and A[j] > value:
      
      1. A[j+1] = A[j]
      2. j -= 1
   5. A[j+1] = value
3. print A

write가 O(n2)을 가지지만, sorted-list 이므로, binary search가 가능하다