이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.
문제 설명 − 배열이 주어졌으므로 반복 방식을 사용하여 빠른 정렬 개념을 사용하여 정렬해야 합니다.
여기서는 먼저 배열을 분할하고 별도의 파티션을 정렬하여 정렬된 배열을 얻습니다.
이제 아래 구현에서 솔루션을 살펴보겠습니다-
예
# iterative way
def partition(arr,l,h):
i = ( l - 1 )
x = arr[h]
for j in range(l , h):
if arr[j] <= x:
# increment
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[h] = arr[h],arr[i+1]
return (i+1)
# sort
def quickSortIterative(arr,l,h):
# Creation of a stack
size = h - l + 1
stack = [0] * (size)
# initialization
top = -1
# push initial values
top = top + 1
stack[top] = l
top = top + 1
stack[top] = h
# pop from stack
while top >= 0:
# Pop
h = stack[top]
top = top - 1
l = stack[top]
top = top - 1
# Set pivot element at its correct position
p = partition( arr, l, h )
# elements on the left
if p-1 > l:
top = top + 1
stack[top] = l
top = top + 1
stack[top] = p - 1
# elements on the right
if p+1 < h:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = h
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSortIterative(arr, 0, n-1)
print ("Sorted array is:")
for i in range(n):
print (arr[i],end=" ") 출력
Sorted array is 2 3 4 5 5 6 7 8
모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.
결론
이 기사에서는 반복적 빠른 정렬을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.