삽입 정렬을 위한 Python 프로그램

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

알고리즘

1. Iterate over the input elements by growing the sorted array at each iteration.
2. Compare the current element with the largest value available in the sorted array.
3. If the current element is greater, then it leaves the element in its place 
   and moves on to the next element else it finds its correct position in the 
   sorted array and moves it to that position in the array.
4. This is achieved by shifting all the elements towards the right, which are 
   larger than the current element, in the sorted array to one position ahead.

이제 알고리즘의 시각적 표현을 봅시다 -

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

예시

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에서의 구현에 대해 배웠습니다. 또는 그 이전.