이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.
문제 설명 − 배열이 주어졌으므로 퀵정렬 개념을 사용하여 정렬해야 합니다.
여기서는 먼저 배열을 분할하고 별도의 파티션을 정렬하여 정렬된 배열을 얻습니다.
이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -
예
# divide function
def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high] # pivot element
for j in range(low , high):
# If current element is smaller
if arr[j] <= pivot:
# increment
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# sort
def quickSort(arr,low,high):
if low < high:
# index
pi = partition(arr,low,high)
# sort the partitions
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSort(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
모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.
결론
이 기사에서는 QuickSort용 Python 프로그램을 만드는 방법에 대해 배웠습니다.