Stooge Sort를 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 배열이 주어졌으므로 stooge 정렬을 사용하여 정렬해야 합니다.

알고리즘

1. Check if value at index 0 is greater than value at last index,then swap them.
2. sort the initial 2/3rd of the array.
3. sort the last 2/3rd of the array.
4. sort the initial 2/3rd again to confirm.

이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -

예시

def stoogesort(arr, l, h):
   if l >= h:
      return
   # swap
   if arr[l]>arr[h]:
      t = arr[l]
      arr[l] = arr[h]
      arr[h] = t
   # more than 2 elements
   if h-l+1 > 2:
      t = (int)((h-l+1)/3)
      # sort first 2/3 elements
      stoogesort(arr, l, (h-t))
      # sort last 2/3 elements
      stoogesort(arr, l+t, (h))
      # sort first 2/3 elements again
      stoogesort(arr, l, (h-t))
# main
arr = [1,4,2,3,6,5,8,7]
n = len(arr)
stoogesort(arr, 0, n-1)
print ("Sorted sequence is:")
for i in range(0, n):
   print(arr[i], end = " ")

출력

Sorted sequence is:
1 2 3 4 5 6 7 8

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론 -

이 기사에서는 Stooge Sort를 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.