Algorithm/이것이 코딩테스트다
[Python][이코테] 삽입 정렬
애기 개발자
2022. 8. 31. 22:58
반응형
삽입 정렬
삽입 정렬은 말 그대로 '삽입' 하여 정렬하는 것이다.
예를 들어 0~9까지 숫자를 오름차순 하고 싶은데 앞의 '선택 정렬'은 가장 작은 숫자를 '찾아서' 순서대로 맞춘다.
하지만 삽입 정렬은 일부러 찾는 것이 아닌 앞 인덱스와 비교하여 현재 인덱스 값 보다 앞 인덱스 값이 크면 '선택'하여 앞으로 보내는 것이다.
삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.
삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.
선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)
중요한 점이 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
7 5 9 0 3 1 6 2 4 8 일 때
1.
5는 7보다 작으므로 5와 7 교체
5 7 9 0 3 1 6 2 4 8
2.
9는 7보다 크니 유지
3.
0은 9보다 작으므로 0과 9를 교체
5 7 0 9 3 1 6 2 4 8
이후 다시 0은 7보다 작으므로 교체 5 0 7 9 3 1 6 2 4 8
-> 0은 5보다 작으므로 교체 0 5 7 9 3 1 6 2 4 8
(반복)
이런 식으로 운영된다.
삽입 정렬의 시간복잡도는 코드로 보듯이 단순 생각하면 $O(N^2)$이다. 하지만 만약 처음부터 모든 값이 정렬되어 있다고 가정한다면 최선의 경우 O(N)의 시간 복잡도를 갖는다.
따라서 거의 정렬된 상태로 입력이 주어지는 문제는 다른 정렬 알고리즘보다 삽입 정렬 알고리즘이 효율이 좋다.
반응형