이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.
문제 설명 − 배열이 주어졌으므로 이진 삽입 정렬의 개념을 사용하여 정렬해야 합니다.
여기에서는 이름에서 알 수 있듯이 삽입 정렬 알고리즘과 함께 이진 검색의 개념을 사용합니다.
이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -
예
# sort
def insertion_sort(arr):
for i in range(1, len(arr)):
temp = arr[i]
pos = binary_search(arr, temp, 0, i) + 1
for k in range(i, pos, -1):
arr[k] = arr[k - 1]
arr[pos] = temp
def binary_search(arr, key, start, end):
#key
if end - start <= 1:
if key < arr[start]:
return start - 1
else:
return start
mid = (start + end)//2
if arr[mid] < key:
return binary_search(arr, key, mid, end)
elif arr[mid] > key:
return binary_search(arr, key, start, mid)
else:
return mid
# main
arr = [1,5,3,4,8,6,3,4]
n = len(arr)
insertion_sort(arr)
print("Sorted array is:")
for i in range(n):
print(arr[i],end=" ") 출력
Sorted array is : 1 3 3 4 4 5 5 6 8
모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.
결론
이 기사에서는 이진 삽입 정렬을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.