Programa Python para Stooge Sort

La clasificación Stooge es un algoritmo de clasificación recursivo. Se define como a continuación (para clasificación en orden ascendente).

Step 1 : If value at index 0 is greater than
         value at last index, swap them.
Step 2:  Recursively,
       a) Stooge sort the initial 2/3rd of the array.
       b) Stooge sort the last 2/3rd of the array.
       c) Stooge sort the initial 2/3rd again to confirm.

# Python program to implement stooge sort
 
def stoogesort(arr, l, h):
 if l >= h:
  return
 
 # If first element is smaller
 # than last,swap them
 if arr[l]>arr[h]:
  t = arr[l]
  arr[l] = arr[h]
  arr[h] = t
 
 # If there are more than 2 elements in
 # the array
 if h-l+1 > 2:
  t = (int)((h-l+1)/3)
 
  # Recursively sort first 2/3 elements
  stoogesort(arr, l, (h-t))
 
  # Recursively sort last 2/3 elements
  stoogesort(arr, l+t, (h))
 
  # Recursively sort first 2/3 elements
  # again to confirm
  stoogesort(arr, l, (h-t))
 
 
# driver
arr = [2, 4, 5, 3, 1]
n = len(arr)
 
stoogesort(arr, 0, n-1)
 
for i in range(0, n):
 print(arr[i], end = ' ')
 
# Code Contributed by Mohit Gupta_OMG <(0_o)>

Producción:

1 2 3 4 5 

Complejidad del tiempo :
la complejidad del tiempo de ejecución de la clasificación de títeres se puede escribir como
T(n) = 3T(3n/2) + O(1)
La solución de la recurrencia anterior es O(n(log3/log1.5)) = O( n ^2.709 ), por lo que es más lento incluso que el tipo de burbuja (n ² ).
Espacio Auxiliar : O(n)

¡ Consulte el artículo completo sobre Stooge Sort para obtener más detalles!