[알고_이론] 삽입정렬 (insertion sort _ by python )

삽입 정렬이 뭔가요?

 

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

 

예시 

 

 

6(Key 4) 에 대한 삽입 정렬을 진행 하는 경우

삽입 정렬의 시간복잡도

-Best Case [ O(n) ]

이미 정렬이 되어 있는 경우, 2번째 자리부터 문자열의 길이인 N까지만 이동을 하는 동안 교환 없이 비교만 이루어 지기 때문에 

n-1 번의 비교가 이루어 진다.

 

그렇기 때문에 시간 복잡도는 O(n) 이라고 할 수 있다.

 

# Best Case

# Key index = 2
arr = [ 1, 2, 3, 4, 5 ]
# 2 뒤에는 자신보다 작은 수(1) 만 있기 때문에 순서 변경 X

# Key index = 3

arr = [ 1, 2, 3, 4, 5 ]
# 3 뒤에는 자신보다 작은 수(1,2) 만 있기 때문에 순서 변경 X

​

-Worst Case [ O(n2) ]

 

우리가 지향하는 오름차순과 정반대인 내림차순으로 되어 있는 경우, key 뒤에 있는 모든 값들과의 비교가 필요하다

이것을 수식으로 변경하면  1 + 2 + 3 + 4 .. + (n+1)  ==    n(n-1)/ 2   ==  O(n2) 이라 할 수 있다.

# Worst Case

# Key index = 2 
arr = [ 8, 7, 6, 5, 4 ]
# 7 뒤에는 자신보다 큰 수(8)가 있기 때문에 순서 변경 O
arr = [ 7, 8, 6, 5, 4 ]

# Key index = 3

arr = [ 7, 8, 6, 5, 4 ]
# 3 뒤에는 자신보다 큰 수 ( 7, 8) 가 있기 때문에 순서 변경 O

arr = [ 6, 7, 8, 5, 4 ]

삽입정렬 _ 파이썬코드

import random

def insertionSort(arr):
	for i in range(1, len(arr)): # 2번째 자리부터 비교를 시작한다.
    	j = i -1 
        while j > 0 and arr[j-1] > arr[j]: # 카드가 더 없고, 자신보다 더 작은 수가 있으면
       		arr[j-1], arr[j] = arr[j], arr[j-1] # 루프를 돌면서 변경해준다.
    return arr # 

arr = random.sample(range(100), 10)
print(arr)
print(insertionSort(arr))