이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.
문제 설명 − 배열이 주어졌으므로 순환 정렬 개념을 사용하여 정렬해야 합니다.
인플레이스(in-place) 알고리즘이며 순환의 형성에 의해 스와핑이 발생합니다.
이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -
예시
def cycleSort(array):
writes = 0
# cycles to be rotated
for cycleStart in range(0, len(array) - 1):
item = array[cycleStart]
#position to place the item
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# if item exits, it is not a cycle
if pos == cycleStart:
continue
# Otherwise, place the item
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
# rotation continued
while pos != cycleStart:
# Find a position to place the item
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# place the item
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return writes
# main
arr = [1,5,3,4,8,6,3,4,5]
n = len(arr)
cycleSort(arr)
print("Sorted array is : ")
for i in range(0, n) :
print(arr[i], end = " ") 출력
Sorted array is : 1 3 3 4 4 5 5 6 8
모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.
결론
이 기사에서는 순환 정렬을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.