Question

Implement the following pseudocode in Python

Consider the following pseudocode for a sorting algorithm:

STOOGESORT(A[0 ... n - 1])
if (n = 2) and A[0] > A[1]
swap A[0] and A[1]
else if n > 2
m = ceiling(2n/3)
STOOGESORT(A[0 ... m - 1])
STOOGESORT(A[n - m ... n - 1])
STOOGESORT(A[0 ... m - 1])

Answer 1

CODE -

import math
def STOOGESORT(A):
n = len(A)
# Swapping the elements if length of list is 2 and first element is greater than second element.
if n == 2 and A[0]>A[1]:
temp = A[0]
A[0] = A[1]
A[1] = temp
# If length of list is greater than 2
elif n>2:
m = math.ceil(2 * n / 3)
# Recursively sorting the first 2/3 elements
A[0 : m] = STOOGESORT(A[0 : m])
# Recursively sorting the last 2/3 elements
A[n-m : ] = STOOGESORT(A[n-m : ])
# Recursively sorting the first 2/3 elements to confirm
A[0 : m] = STOOGESORT(A[0 : m])
return A

SCREENSHOT -

If you have any doubt regarding the solution, then do comment.
Do upvote.