[알고리즘] 삽입 정렬 정리

삽입 정렬(Insertion sort)은 List의 두번째 인덱스 부터 시작하여 Index - 1로 순회하여 정렬 하는 방식이다.

즉 두번째 인덱스와 첫번째 인덱스를 비교,교체하고, 세번째 인덱스와 두번째, 첫번째 인덱스 순으로 비교, 교체를 하게 된다.

시간복잡도는 최선의 경우 O(n)

최악의 경우O(n^2)

 

예시:

[10, 68, 51, 81, 47] 정렬되지 않은 List

 

먼저 두번째 인덱스를 기준으로 해서 인덱스 - 1로 순회를 한다.

두번째 인덱스 값 68과 인덱스 - 1인 첫번째 인덱스 값 10과 비교, 10이 더 작으니 교체 없이 다음 과정으로

[10, 68, 51, 81, 47]

과정 1 [10, 68, 51, 81, 47]

 

세번째 인덱스 값 51과 두번째 인덱스 값 68과 비교, 51이 더 작으니 교체

두번째 인덱스 값 51과 첫번째 인덱스 값 10 비교, 교체 없이 다음 과정으로 

[10, 68, 51, 81, 47]

과정 1 [10, 68, 51, 81, 47]

과정 2 [10, 51, 68, 81, 47]

 

네번째 인덱스 값 81은 3,2,1 번째 인덱스 값보다 크므로 교체 없이 다음 과정으로

[10, 51, 68, 81, 47]

과정 1 [10, 68, 51, 81, 47]

과정 2 [10, 51, 68, 81, 47]

과정 3 [10, 51, 68, 81, 47]

 

마지막 인덱스 값 47과 인덱스 - 1 씩 비교하여 교체하면 마무리 된다.

[10, 51, 68, 81, 47]

과정 1 [10, 68, 51, 81, 47]

과정 2 [10, 51, 68, 81, 47]

과정 3 [10, 51, 68, 81, 47]

과정 4 [10, 51, 68, 47, 81]

과정 5 [10, 51, 47 68, 81]

과정 6 [10, 47, 51, 68, 81]

 

 

전체 과정:

[10, 68, 51, 81, 47] 

[10, 51, 68, 81, 47]
[10, 51, 68, 81, 47]

[10, 51, 68, 47, 81]

[10, 51, 47 68, 81]

[10, 47, 51 68, 81]

python 코드

def insertion(data):
    for index in range(len(data_list) - 1):   
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2-1]:
                data[index2-1], data[index2] = data[index2], data[index2-1]
            else:
                break
    return data