Yet another sorting algorithm

Computer Science Level pending
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def floor(n):
    """Compute the floor function of n"""
    return int(n)


def stoogy(A, i, j):
    """Sort A[i...j]"""
    if A[i] > A[j]:
        A[i] , A[j] = A[j] , A[i] #Swap A[i] and A[j]
    if i + 1 >= j:
        return
    m = floor( (j - i + 1) / 3)
    stoogy(A, i, j - m)
    stoogy(A, i+m, j)
    stoogy(A, i, j - m)


def sort(A):
    """Sort the list A[0..n]"""
    stoogy(A, 0, len(A) - 1)

The tight asymptotic bound of (\(\Theta\) - notation) of the sorting algorithm above(sort(A)) can be expressed as \(\Theta(n^{\alpha})\)( \(\alpha \in \mathbb{R} \) ). Find \(\alpha\).

Details and Assumptions

  • \(n\) is the size of the array to be sorted.
×

Problem Loading...

Note Loading...

Set Loading...