Insertion Sort

yijin3018·2021년 11월 11일
0
  • 개념 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
  • 특징
    • 현재 선택된 데이터의 앞 부분은 이미 정렬됨.
  • 장점
    • 안정한 정렬 방법
    • 레코드 수 적으면 간단해서 유리
    • 대부분 이미 정렬되어있으면 효율적일수도 있다.
  • 단점
    • 비교적 많은 레코드의 이동을 포함
    • 레코드 수 많고 크면 부적합
  • 시간복잡도 : O(n)O(n) (이동 없이 한 번의 비교만 이뤄지는 최선의 경우) / O(n2)O(n^2) (역순일 경우)
  • 공간복잡도 : O(1)O(1)

선택정렬과 삽입 정렬의 유사한 점과 차이점
유사점 : k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점
차이점 : 선택정렬은 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입정렬은 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다.

arr = [4,2,5,6,1,3]

# Solution 1
for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
        else:  # 추가된 부분
            break
    print(arr)

#[2, 4, 5, 6, 1, 3]
#[2, 4, 5, 6, 1, 3]
#[2, 4, 5, 6, 1, 3]
#[1, 2, 4, 5, 6, 3]
#[1, 2, 3, 4, 5, 6]

# Solution 2
for i in range(1, len(arr)):
    j = i
    while j>0 and arr[j-1] > arr[j]:
        arr[j-1], arr[j] = arr[j], arr[j-1]
        j -= 1
    print(arr)
profile
💻 For Computer Science..

0개의 댓글