Insertion Sort ( 삽입 정렬 ) python으로 구현하기

- Insertion Sort 설명 

: 왼쪽 원소들과 비교해서 정렬한다

Insertion Sort하는 과정

< 순서 >
1) index =1 부터 시작함 
2) 해당 key와 왼쪽 원소를 비교한다.
3)
If  A[key-1]>A[key]이면 exchange 한다 
    본래의 key값을 왼쪽 원소들과 역순으로 비교한다 
    왼쪽 수가 더 크면 exchange하는 걸 반복한다 
    key+1해준다 
Else A[key-1]<A[key]이면 exchange하지 않는다
                                                   key+1해준다

 

- python code