[알고리즘] 삽입정렬 (insertion sort)

삽입정렬이란?

• 두번째 인덱스부터 시작한다
• key값 앞에 있는 데이터(front)부터 비교해서 key < front 이면, front값을 뒤 인덱스로 복사
• key보다 작은 데이터를 만날때까지 반복, 작은 데이터를 만나면 바로 뒤에 key값을 이동

• 예 : data_list = [9, 3, 2, 5]
  • 1번째 실행 : key=9, [9,3,2,5]
  • 2번째 실행 : key=3, front=9, 자리바꿈 [3,9,2,5]
  • 3번째 실행 : key=2, front=9, 자리바꿈  /  key=2, front=3, 자리바꿈 [2,3,9,5]
  • 4번째 실행 : key=5, front=9, 자리바꿈 3보다 5가 크므로 끝 [2,3,5,9]

 

알고리즘 구현

def insertion_sort(data):
	for index in range(len(data) - 1):
    	for index2 in range(index + 1, 0, -1):
        	if data[index2] < data[index2 - 1]:
            	data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
            	break
    return data