Python 삽입 정렬

이번 포스팅에서는 Python 삽입 정렬 알고리즘에 대해 알아봅니다.

성능 측면에서 삽입 정렬은 최고의 정렬 알고리즘이 아닙니다. 그러나 선택 정렬과 버블 정렬보다 조금 더 효율적입니다.

삽입 정렬 알고리즘을 쉽게 이해하기 위해 예제부터 시작하겠습니다.

Python 삽입 정렬

예
배열 [14,5,18,6,21]이 있다고 가정해 보겠습니다.

이 배열에 두 부분이 있다고 가정합니다. 첫 번째 부분은 정렬되고 다른 부분은 정렬되지 않습니다.

Python 삽입 정렬

배열의 정렬된 부분은 주황색 선의 왼쪽에 있고 정렬되지 않은 부분은 오른쪽에 있습니다.

이제 우리가 해야 할 일은 정렬되지 않은 부분에서 각 요소를 하나씩 선택하여 정렬된 배열의 적절한 위치에 추가하는 것입니다.

Python 삽입 정렬

14는 정렬된 부분의 유일한 요소이므로 이미 정렬되어 있습니다.

이제 정렬되지 않은 부분에서 첫 번째 요소를 선택하여 정렬된 부분에 추가합니다.

Python 삽입 정렬

5는 14보다 작으므로 14는 한 자리 오른쪽으로 이동해야 합니다.

다시 정렬되지 않은 부분에서 첫 번째 요소를 선택하여 정렬된 부분에 추가합니다.

Python 삽입 정렬

18은 14보다 크므로 이동할 필요가 없습니다.

같은 것을 반복

Python 삽입 정렬

6은 5보다 크고 14보다 작습니다.

따라서 14와 18을 한 자리씩 오른쪽으로 이동해야 합니다.

마침내

Python 삽입 정렬

21이 18보다 크면 이동할 필요가 없습니다. 완료.

연산
n개의 요소를 포함하는 'Arr[]' 배열이 있습니다.

1단계:   i = 1로 설정

2단계:  설정값 = Arr[i]

위치 설정 = i

3단계:   위치 > 0이고 Arr[위치-1]>값인 경우

Arr[위치] = Arr[위치-1]

위치 = 위치 -1

[조건이 거짓이 될 때까지 이 단계를 반복]

4단계:  Arr[위치] = 값

5단계:  (n-1)번 동안 2단계로 이동합니다.

Python의 삽입 정렬 프로그램

Arr = [5,14,18,6,21]

n= len(Arr)

i = 1

while (i<=n-1):

  value = Arr[i]

  position = i

 

  while (position>0 and Arr[position-1]>value):

    Arr[position] = Arr[position-1]

    position = position -1

 

  i = i+1

  Arr[position] = value

 

 

for i in Arr:

  print i,

산출

5 6 14 18 21