[Python] 알고리즘-삽입정렬 (Insertion Sort)
기본 정렬 알고리즘
삽입 정렬 (Insertion Sort)
리스트의 값을 하나씩 살펴보며 적절한 위치에 삽입한다
-
정렬 순서
-
첫 번째 숫자를 삽입한 것이라 하고 두 번째 숫자부터 확인한다
-
현재 선택한 숫자 바로 앞부터 처음까지 왼쪽으로 이동하면서 가리킨 숫자가 선택한 숫자보다 클 시 가리킨 숫자를 뒤로 옮긴다
-
현재 선택한 숫자보다 가리킨 숫자보다 작을 시 멈추고 해당 자리에 삽입한다
-
-
예시
순서 리스트 진행 상황 0 [ 3, 6, 5, 7, 2 ] 초기값 1 [ 3, [6], 5, 7, 2 ] 3 삽입, 6 확인 2 [ 3, 6, [5], 7, 2 ] 6 삽입, 5 확인 3 [ 3, 5, 6, [7], 2 ] 5 삽입, 7 확인 4 [ 3, 5, 6, 7, [2]] 7 삽입, 2 확인 5 [ 2, 3, 5, 6, 7 ] 2 삽입, 끝
- 코드
def insert_sort(x):
for i in range(1, len(x)):
j = i - 1
key = x[i]
while x[j] > key and j >= 0:
x[j+1] = x[j]
j = j - 1
x[j+1] = key
return x
-
시간 복잡도 비교
기본 정렬 알고리즘 최적 평균 최악 선택 정렬 N^2 N^2 N^2 버블 정렬 N^2 N^2 N^2 삽입 정렬 N N^2 N^2
Author And Source
이 문제에 관하여([Python] 알고리즘-삽입정렬 (Insertion Sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/Python-알고리즘-삽입정렬-Insertion-Sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)