파이썬에서 삽입 정렬이란 무엇입니까?

삽입 정렬은 배열을 정렬하는 간단한 방법입니다. 이 기술에서 배열은 정렬된 부분과 정렬되지 않은 부분으로 사실상 분할됩니다. 정렬되지 않은 부분의 요소가 선택되어 정렬된 부분의 올바른 위치에 배치됩니다.

• 배열 요소는 1에서 n까지 순회합니다.

• i 위치의 배열 요소가 이전 요소보다 크면 이동할 필요가 없습니다.

• 위치 i의 배열 요소가 이전 요소보다 작은 경우, 그보다 작은 선행 요소를 찾거나 배열의 가장 왼쪽 위치에 도달할 때까지 왼쪽으로 이동해야 합니다.

예

예제를 통해 위의 아이디어를 더 명확하게 이해할 수 있습니다. 다음 배열이 있다고 가정합니다 -

인덱스 1에서 배열 탐색을 시작해야 합니다(인덱스 0에는 선행 작업이 없기 때문에).

색인 1에서 -

6은 이전 것보다 크므로 아무 것도 수행할 필요가 없습니다.

색인 2에서 -

1은 이전 항목보다 작으므로 이전 항목보다 작은 이전 항목을 찾지 않거나 인덱스 0에 도달하지 않는 한 왼쪽으로 이동해야 합니다. 이 경우 인덱스 0에 도달합니다.

색인 3에서 -

색인 4에서 -

2보다 작은 선행 작업을 찾을 때까지 2를 왼쪽으로 이동합니다.

색인 5에서 -

5보다 작은 선행 작업을 찾을 때까지 5를 왼쪽으로 이동합니다.

따라서 정렬된 배열을 얻습니다.

삽입 정렬은 O(n^2) 시간 복잡도와 O(1) 공간 복잡도를 갖는 제자리 정렬 알고리즘입니다.

예시

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i] #get each element
      j = i-1
      while j >= 0 and key &lit; arr[j] : #keep shifting until reaching index 0 or getting an element smaller than key
         arr[j + 1] = arr[j]
         j=j-1
      arr[j + 1] = key

arr = [4,6,1,7,2,5]
insertionSort(arr)
for i in range(len(arr)):
   print (arr[i],end=" ")

출력

1 2 4 5 6 7