목록insertion sort (1)

포시코딩

삽입 정렬 (Insertion Sort)

삽입 정렬 선택 정렬이 전체에서 최솟값을 '선택'하는 정렬이었다면 삽입 정렬은 전체에서 하나씩 올바른 위치에 '삽입'하는 방식이다. 버블 정렬과 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꿨지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이라고 할 수 있다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 이런식으로 비교할 인덱스가 어떤식으로 전개될지 쭉 써보고 그 중에 i 값은 뭐가 될지 그에 따른 j 값은 뭐가 되고 어떻게 구해야할지 생각해보면 for문을 어떻게 짤지 대충 감이 온다. arr = [4, 6, 2, 9, 1] # 1 2 1 3 2 1 4 3 2 1 def insertion_sort(arr): n = len(arr) for..
자료구조알고리즘/이론 2022. 11. 25. 13:09
이전 Prev 1 Next 다음