Tipo de títere

Stooge Sort es un algoritmo de clasificación recursivo. No es un algoritmo de clasificación muy eficiente pero interesante. Generalmente divide la array en dos partes superpuestas (2/3 cada una). Después de eso, realiza la clasificación en los primeros 2/3 partes y luego realiza la clasificación en los últimos 2/3 partes. Y luego, la clasificación se realiza en las primeras 2/3 partes para garantizar que la array esté ordenada.

La idea clave es que ordenar la parte superpuesta dos veces intercambia los elementos entre las otras dos secciones en consecuencia.

Acercarse:

Paso 1: si el valor en el índice 0 es mayor que el valor en el último índice, cámbielos.
Paso 2: recursivamente, 

• Stooge ordena los 2/3 iniciales de la array.
• Stooge ordena los últimos 2/3 de la array.
• Stooge ordena los 2/3 iniciales nuevamente para confirmar.

NOTA: Siempre tome el límite de ((2/3)*N) para seleccionar elementos.  

Ilustración:  

Consideremos un ejemplo: arr[] = { 2, 4, 5, 3, 1}

• Paso 1: inicialmente, se comparan los elementos primero y último y, si el último es mayor que el primero, se intercambian.

1

4

5

3

2

• Paso 2: ahora, ordene recursivamente los 2/3 iniciales de los elementos como se muestra a continuación:

1

4

5

3

2

1

3

4

5

2

• Paso 3: luego, ordene recursivamente los últimos 2/3 de los elementos, como se muestra a continuación:

1

3

4

5

2

1

2

3

4

5

• Paso 4: nuevamente, ordene los 2/3 iniciales de los elementos para confirmar que los datos finales estén ordenados.
  • Array resultante:

1	2	3	4	5

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement stooge sort
#include <iostream>
using namespace std;
  
// Function to implement stooge sort
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])
        swap(arr[l], arr[h]);
  
    // 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
int main()
{
    int arr[] = { 2, 4, 5, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Calling Stooge Sort function to sort
    // the array
    stoogesort(arr, 0, n - 1);
  
    // Display the sorted array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
  
    return 0;
}

// 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)>

# 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))
   
  
# deriver 
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)>

// C# program to implement stooge sort
using System;
  
class GFG {
      
    // 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()
    {
        int[] arr = { 2, 4, 5, 3, 1 };
        int n = arr.Length;
  
        // Calling Stooge Sort function
        // to sort the array
        stoogesort(arr, 0, n - 1);
  
        // Display the sorted array
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
  
// This code is contributed by Sam007.

<script>
    // Javascript program to implement stooge sort
      
    // Function to implement stooge sort
    function stoogesort(arr, l, h)
    {
        if (l >= h)
            return;
    
        // If first element is smaller
        // than last, swap them
        if (arr[l] > arr[h]) {
            let 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) {
            let t = parseInt((h - l + 1) / 3, 10);
    
            // 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);
        }
    }
      
    let arr = [ 2, 4, 5, 3, 1 ];
    let n = arr.length;
  
    // Calling Stooge Sort function
    // to sort the array
    stoogesort(arr, 0, n - 1);
  
    // Display the sorted array
    for (let i = 0; i < n; i++)
      document.write(arr[i] + " ");
      
</script>

1 2 3 4 5 

La complejidad del tiempo de ejecución de la clasificación de títeres se puede escribir como
T(n) = 3T(3n/2) + ?(1)

La solución de la recurrencia anterior es O(n ^{(log3/log1.5)} ) = O(n ^2.709 ), por lo tanto, es más lenta que incluso la ordenación de burbujas (n^2).

Echa un vistazo al curso de autoaprendizaje de DSA

Este artículo es una contribución de DANISH KALEEM . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.