[TIL_알고리즘] 삽입 정렬 Insertion Sort

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

0 1 2 3 4

[5,1,7,10,2]

 

1회전시

정렬된 5(인덱스0) 키로 선정된 1(인덱스1)을 비교 [5,1] -> [1,5]

2회전시

정렬된 5(인덱스1)이 키로 선정된 7(인덱스2)를 비교 [1,5,7] -> [1,5,7]

3회전시

정렬된 7(인덱스2)이 키로 선정된 10(인덱스3)를 비교 [1,5,7,10] -> [1,5,7,10]

4회전시

정렬된 10(인덱스3)이 키로 선정된 2(인덱스)를 비교 [1,5,7,10,2] -> [1,5,7,2,10] -> [1,5,2,7,10] -> [1,2,5,7,10]

정렬 완료

 

best case: O(n)

worst case: O(n2)

평균적인 시간 복잡도: O(n2)

 

data = [1,5,7,10,2]

 

howmany=len(data)

count=0

for pivot in range(1,howmany): #pivot=1 #0번은 정렬된 나라, 1번 기준이 되는 키값을 pivot으로 설정

  count+=1

  key=data[pivot] #key=5 ; 기준이 되는 1번 키값

  now=pivot-1 #정렬된나라 0번 

  while now>=0 and data[now]>key: #정렬된 나라를 기준으로 키값을 이동할 때 더이상 이동할 곳이 없기전까지(이동가능한 곳까지), 정렬된 나라가 키값보다 클경우만 실행(둘다 만족시)

    data[now+1]=data[now]

    now-=1

  data[now+1]=key

  print("%d회전후: %s" %(count,data))

print(data)

 

1회전후: [1, 5, 7, 10, 2]

2회전후: [1, 5, 7, 10, 2]

3회전후: [1, 5, 7, 10, 2]

4회전후: [1, 2, 5, 7, 10]

[1, 2, 5, 7, 10]