알고리즘(삽입 정렬)

삽입 정렬

삽입 정렬은 하나의 값을 기준으로 잡고 그 기준 값이 앞의 값보다 클 때 까지 교환해주는 것이 삽입 정렬이다.

예를들어 [5,3,4,2,1]이 있다고 하면
1번째 턴에서는 [3,5,4,2,1]
2번째 턴에서는 [3,4,5,2,1]
3번째 턴에서는 [3,4,2,5,1] => [3,2,4,5,1] => [2,3,4,5,1]
4번째 턴에서는 [2,3,4,1,5] => [2,3,1,4,5] => [2,1,3,4,5] => [1,2,3,4,5]

이런 순서로 정렬이 되는것이 선택 정렬이다.

이를 코드로 표현한다면

for index in range(데이터 길이 -1):
	for index2 in range(index +1, 0 , -1):
    	if 앞데이터 < 뒤데이터:
        	swap(앞, 뒤)

이런 형태가 될 것이다.

위의 코드에서 5개의 데이터에서 4개의 기준으로 비교한 것으로 보아 기준의 설정을 데이터 길이 -1로 하면 됨을 알게되었다.

다음은 기준으로 설정된 값이 바로 앞의 값보다 클 때까지 비교하면 되는데 일단 기준을 받아서 그 기준의 앞의 값을 비교하고 작으면(if) 두 값을 교환해주고 크거나 같다면(else) 더이상의 비교가 필요 없기 때문에 멈춰주면 될것이다(break). 이를 마지막으로 코드로 작성한다면

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