[Python] 정렬 / 삽입 정렬(Insertion sort)

삽입 정렬

삽입정렬(Insertion sort)이란, 리스트의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입하는 방법입니다.


배열이 길어질수록 효율이 떨어지지만,선택 정렬이나 거품 정렬에 비교하여 빠르며, 안정적이고 in-place 알고리즘입니다.

삽입 정렬

def insertion_sort(li):
    length = len(li)

    for i in range(1, length):
                                    # j는 1번째 부터 시작하여 그 앞의 값들과 비교하여 자신의 자리를 찾습니다.
        for j in range(i, 0, -1):   # 자신보다 큰 값들과 자리를 바꾸며 자신보다 작은 값 뒤까지 반복합니다.
            if li[j] < li[j - 1]:
                li[j], li[j - 1] = li[j - 1], li[j]

        #print(li)     # 단계별 출력
    return li

 

0번째 원소만으로는 정렬할 수 없으므로

j는 1번째 부터 시작하여 정렬된 앞의 값들과 비교하며 자신의 자리를 찾습니다.
자신의 자리로 삽입되기 위해 원소들을 한칸씩 뒤로 이동시키며 이동합니다.

• 정렬 과정
  

  

주어진 리스트가 [5, 4, 3, 7, 6, 2] 라고 한다면, 단계별로 출력한 결과입니다.

0번째 : [4, 5, 3, 7, 6, 2]
1번째 : [3, 4, 5, 7, 6, 2]
2번째 : [3, 4, 5, 7, 6, 2]
3번째 : [3, 4, 5, 6, 7, 2]
4번째 : [2, 3, 4, 5, 6, 7]
정렬 끝