알고리즘) 정렬(2/4) - 삽입정렬(insertion)

삽입 정렬은 한 요소를 앞의 요소들과 비교해서 나보다 큰 요소가 있다면 그 요소 앞에 해당 요소를 배치하는 것입니다.

그래서 이 알고리즘을 고안하는데 필요한 것은

1. 한 요소를 특정할 수 있는 부분

2. 해당 요소 앞까지 확인할 수 있는 부분

3. 큰 수를 발견했을때, 위치를 바꿔주는 부분

def insertionSort(data):
    for i in range(len(data)):
        for j in range(i):
            if data[j]<data[i]:
                continue
            else :
                data[j], data[i] = data[i], data[j]
    return data

 데이터에 적용해주면 

잘 됩니다

 

삽입 정렬의 경우에도

for 문을 2번 돌리기 때문에 O(n^2)의 속도를 갖습니다.