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.
Java
// Java program to implement stooge sort
import java.io.*;
public class stooge
{
// Function to implement stooge sort
static void stoogesort(int arr[], int l, int h)
{
if (l >= h)
return;
// If first element is smaller
// than last,swap them
if (arr[l] > arr[h])
{
int 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)
{
int t = (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 Code
public static void main(String args[])
{
int arr[] = {2, 4, 5, 3, 1};
int n = arr.length;
stoogesort(arr, 0, n-1);
for (int i=0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// 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 2 ).
Espacio Auxiliar : O(n)
¡ Consulte el artículo completo sobre Stooge Sort para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA