Python 프로그램의 삽입 정렬

이 기사에서 우리는 Python 3.x에서 삽입 정렬의 구현에 대해 배울 것입니다. 또는 그 이전.

알고리즘

• 각 반복에서 정렬된 배열을 늘려 입력 요소를 반복합니다.

• 현재 요소를 정렬된 배열에서 사용할 수 있는 가장 큰 값과 비교합니다.

• 현재 요소가 더 크면 해당 요소를 제자리에 두고 다음 요소로 이동합니다. 그렇지 않으면 정렬된 배열에서 올바른 위치를 찾아 배열의 해당 위치로 이동합니다.

• 이것은 정렬된 배열에서 현재 요소보다 큰 모든 요소를 ​​오른쪽으로 한 위치 앞으로 이동함으로써 달성됩니다.

이제 알고리즘의 시각적 표현을 살펴보겠습니다.

이제 구현을 살펴보겠습니다.

예

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i]
      # Move elements of arr[0..i-1], that are greater
      than key,
      # to one position ahead of their current position
      j = i-1
      while j >=0 and key < arr[j] :
         arr[j+1] = arr[j]
         j -= 1
      arr[j+1] = key
# main
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
   print (arr[i])

출력

The sorted array is:
a
i
l
o
r
t
t
u

시간 복잡성: O(n*2)

보조 공간: O(1)

모든 변수는 아래 그림과 같이 전역 프레임에 선언됩니다. -

결론

이 기사에서 우리는 삽입 정렬과 Python 3.x에서의 구현에 대해 배웠습니다. 또는 그 이전.