[알고리즘 공부] 3. Insertion Sort (삽입 정렬)

Insertion Sort

Selection Sort(선택 정렬) 와 비슷한 느낌으로 진행되는 Insertion Sort(삽입 정렬) 입니다.

하나씩 가져와서 앞의 원소들과 확인 후 알맞는 자리에 넣는 형식의 정렬 형태입니다.

버블 정렬, 선택 정렬에 비해 조금 귀찮아보이지만 사실 구현으로 들어가면 크게 다르지 않습니다. 

구현이 똑같이 간단하다는 것은? 네 그렇습니다. 똑같이 시간 복잡도도 크게 다르지 않다는 뜻입니다. ㅜㅜ

마찬가지로 시간 복잡도 또한 O(n^2)입니다.  

원리 또한 마찬가지로 간단하므로 바로 파이썬 구현으로 넘어가겠습니다. 

---

input = [14,54,5,2,1,36,324,34,213,6,7,4]

def InsertionSort(input):
    
    length = len(input)
    for x in range(1, length):
    	# 앞에서 부터 하나씩 구별
        for y in range(x, 0, -1):
        	# 선택한 원소가 앞의 원소들 보다 작다면 한칸씩 앞으로 전진
            if input[y-1] > input[y]:
                input[y-1], input[y] = input[y], input[y-1]
                
    return input

print(InsertionSort(input))