[Algorithm][Python] 삽입정렬 (insertion sort)

삽입정렬 (insertion sort)

1. 삽입 정렬 (insertion sort) 란?

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B) 부터 비교해서 key 값이 더 작으면, B 값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복,그리고 큰 데이터를 만난 위치 바로뒤에 key 값을 이동.

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

for index in range(10, 1, -1):
	prtnt (index)

## 10, 9, 8, 7, 6, 5, 4, 3, 2

range() 함수의 경우

range(start, stop ,step) 인자가 있다.

2. 어떻게 코드로 만들까…?

1. 기준이 되는 숫자를 정한다. 이 숫자는 list 에서 첫번째 요소부터 끝까지 간다.
2. 기준이 되는 숫자와 비교할 숫자를 정한다. 이 숫자는 기준이 되는 숫자의 앞쪽에 있는 요소들이다.
3. 숫자를 비교해서 앞쪽 숫자가 더 크면, 배열의 순서를 바꾼다.
4. 마지막까지 바꾼다. 바꿀요소가 없으면 안쪽에서 break 해서 loop 을 탈출한다.

3. 알고리즘 구현

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