[알고리즘][삽입정렬][InsertionSort][정렬][파이썬][Python]-정리 및 코드

Insertion Sort(삽입 정렬)

 

삽입 정렬은 버블 정렬, 선택 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 선택 정렬을 살펴보기 전에 이전 포스팅에서 설명한 버블 정렬과 선택 정렬에 대해 먼저 이해하시면 선택 정렬을 이해하는데 도움이 될 겁니다.

 

 

아이디어

삽입 정렬의 아이디어는 데이터를 하나씩 확인하면서 자기 자리를 찾아 해당 위치에 삽입하는 것입니다. 데이터의 앞에서부터 순서대로 진행하며 자신의 앞에 있는 데이터와 비교하고 자신보다 작으면 스왑을, 크거나 같으면 다음 루프를 진행합니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름 차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 알고리즘과 코드를 살펴보겠습니다.

 

알고리즘

삽입 정렬의 알고리즘은 다음과 같습니다. 정렬 되지 않은 무작위의 숫자가 리스트에 저장되어 있고 오름차순으로 정렬을 한다고 가정합니다.

 

예 : [ 3, 2, 4, 5, 1 ] ( 정렬 되지 않은 리스트)

 

먼저 두번째 위치에서 시작합니다. 두 번째 위치에 있는 값은 2이며 그 앞의 값과 비교합니다. 2는 그 앞의 값인 3보다 작으므로 2와 3의 위치를 바꿔 줍니다.

결과 1. [ 2, 3, 4, 5, 1 ] 

 

리스트의 맨 앞까지 왔으므로 한 사이클이 완료되었습니다. 이제 그다음 사이클을 진행합니다.

 

그다음 위치로 이동합니다.  세 번째 위치에 있는 값은 4이며 그 앞의 값과 비교합니다. 4는 그 앞의 값인 3보다 크므로 그대로 유지됩니다.

결과 2. [ 2, 3, 4, 5, 1 ] 

 

그 다음 위치로 이동합니다. 네 번째 위치에 있는 값은 5이며 그 앞의 값과 비교합니다. 5는 그 앞의 값인 4보다 크므로 그대로 유지됩니다.

결과 3. [ 2, 3, 4, 5, 1 ] 

 

그 다음 위치로 이동합니다. 다섯 번째 위치에 있는 값은 1이며 그 앞의 값과 비교합니다. 1은 그 앞의 값인 5보다 작으므로 1과 5의 위치를 바꿔줍니다.

결과 4. [ 2, 3, 4, 1, 5 ] 

 

1과 그 앞의 값과 비교합니다. 1은 그 앞의 값인 4보다 작으므로 1과 4의 위치를 바꿔줍니다.

결과 5. [ 2, 3, 1, 4, 5 ] 

 

1과 그 앞의 값과 비교합니다. 1은 그 앞의 값인 3보다 작으므로 1과 3의 위치를 바꿔줍니다.

결과 6. [ 2, 1, 3, 4, 5 ] 

 

1과 그 앞의 값과 비교합니다. 1은 그 앞의 값인 2보다 작으므로 1과 2의 위치를 바꿔줍니다.

결과 6. [ 1, 2, 3, 4, 5 ] 

 

여기까지 모든 사이클이 돌았습니다. 전체 사이클을 다 수행한 결과 전체 데이터가 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

시간 복잡도 Big(O)

삽입 정렬은 아직 정렬되지 않은 값을 이미 정렬된 배열 사이에 삽입하는 과정을 반복합니다. N-1번이 사이클이 반복되고 각 사이클당 최대 N-1번의 스왑(Swap)이 발생할 수 있습니다. 즉 전체 데이터를 정렬하는 데는 최대 약 O(N^2)의 시간 복잡도를 갖습니다. 삽입 정렬 역시 최대 O(N^2)의 시간 복잡도를 갖지만 평균적으로 버블 정렬과 선택 정렬에 비해 빠르게 정렬됩니다.

 

영상으로 이해하기

이해가 안 가시는 분들을 위해 삽입 정렬을 눈으로 쉽게 이해할 수 있는 영상을 첨부하였습니다. 영상을 보면서 데이터가 이동하는 흐름을 살펴보면 알고리즘을 이해하는데 도움이 될 것이라 생각합니다.

 

소스코드

#Python

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

def Insertion_sort(li):       for i in range(1, len(li)):         print(li)         for j in range(i,0, -1):             if li[j]<li[j-1]:                 temp=li[j]                 li[j]=li[j-1]                 li[j-1]=temp             else:                 break if __name__=="__main__":     list_a=[ 10-i for i in range(10)]     Insertion_sort(list_a)     print(list_a)

 

중간중간 print()를 추가하여 데이터가 스왑(Swap)하는 과정을 눈으로 확인할 수 있도록 작성하였습니다.

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.