Se utiliza un algoritmo de clasificación para reorganizar una array dada o enumerar elementos de acuerdo con un operador de comparación en los elementos. El operador de comparación se utiliza para decidir el nuevo orden del elemento en la estructura de datos respectiva . Pero a continuación se muestran algunos de los algoritmos de clasificación más lentos:
Stooge Sort: Una clasificación Stooge es unalgoritmo de clasificación recursivo . Divide recursivamente y ordena la array en partes. A continuación se muestran los pasos de Stooge Sort:
- Si el valor en el índice 0 es mayor que el valor en el último índice, cámbielos.
- Si el número de elementos en la array es mayor que dos:
- Llame recursivamente a la función stoogesort para los 2/3 elementos iniciales de la array.
- Llame recursivamente a la función stoogesort para los últimos 2/3 elementos de la array.
- Llame recursivamente a la función stoogesort para los 2/3 elementos iniciales nuevamente para confirmar que la array resultante está ordenada o no.
- Imprime la array ordenada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the stooge sort
#include <iostream>
using namespace std;
// Function to implement stooge sort
void stoogesort(int arr[], int l, int h)
{
// Base Case
if (l >= h)
return;
// If first element is smaller than
// last element, 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 the first
// 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the last
// 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the first
// 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 5, 3, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
stoogesort(arr, 0, N - 1);
// Display the sorted array
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
return 0;
}
Java
// Java program for the
// stooge sort
class GFG{
// Function to implement
// stooge sort
static void stoogesort(int arr[],
int l, int h)
{
// Base Case
if (l >= h)
return;
// If first element is smaller
// than last element, swap them
if (arr[l] > arr[h])
{
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
// If there are more than
// 2 elements in the array
if (h - l + 1 > 2)
{
int t = (h - l + 1) / 3;
// Recursively sort the
// first 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the
// last 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the
// first 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {2, 4, 5, 3, 1};
int N = arr.length;
// Function Call
stoogesort(arr, 0, N - 1);
// Display the sorted array
for (int i = 0; i < N; i++)
{
System.out.print(arr[i] + " ");
}
}
}
// This code is contributed by Chitranayal
Python3
# Python3 program for the stooge sort # Function to implement stooge sort def stoogesort(arr, l, h): # Base Case if (l >= h): return # If first element is smaller than # last element, swap them if (arr[l] > arr[h]): temp = arr[l] arr[l] = arr[h] arr[h] = temp # If there are more than 2 elements # in the array if (h - l + 1 > 2): t = (h - l + 1) // 3 # Recursively sort the first # 2/3 elements stoogesort(arr, l, h - t) # Recursively sort the last # 2/3 elements stoogesort(arr, l + t, h) # Recursively sort the first # 2/3 elements again stoogesort(arr, l, h - t) # Driver Code arr = [ 2, 4, 5, 3, 1 ] N = len(arr) # Function Call stoogesort(arr, 0, N - 1) # Display the sorted array for i in range(N): print(arr[i], end = " ") # This code is contributed by code_hunt
C#
// C# program for the
// stooge sort
using System;
class GFG{
// Function to implement
// stooge sort
static void stoogesort(int []arr,
int l, int h)
{
// Base Case
if (l >= h)
return;
// If first element is smaller
// than last element, swap them
if (arr[l] > arr[h])
{
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
// If there are more than
// 2 elements in the array
if (h - l + 1 > 2)
{
int t = (h - l + 1) / 3;
// Recursively sort the
// first 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the
// last 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the
// first 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {2, 4, 5, 3, 1};
int N = arr.Length;
// Function Call
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 Princi Singh
Javascript
<script>
// Javascript program for the
// stooge sort
// Function to implement
// stooge sort
function stoogesort(arr, l, h)
{
// Base Case
if (l >= h)
return;
// If first element is smaller
// than last element, swap them
if (arr[l] > arr[h])
{
let temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
// If there are more than
// 2 elements in the array
if (h - l + 1 > 2)
{
let t = Math.floor((h - l + 1) / 3);
// Recursively sort the
// first 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the
// last 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the
// first 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
let arr = [ 2, 4, 5, 3, 1 ];
let N = arr.length;
// Function Call
stoogesort(arr, 0, N - 1);
// Display the sorted array
for (let i = 0; i < N; i++)
{
document.write(arr[i] + " ");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 2 3 4 5
Complejidad Temporal: O(N 2.709 ). Por lo tanto, es más lento incluso que el Bubble Sort que tiene una complejidad de tiempo de O(N 2 ).
Clasificación lenta: La clasificación lenta es un ejemplo de Multiply And Surrender, una broma irónica de divide y vencerás . La ordenación lenta almacena el elemento máximo de la array en la última posición dividiendo recursivamente la array por la mitad y comparando cada uno de ellos. Luego llama recursivamente a la array sin el elemento máximo anterior y almacena el nuevo elemento máximo en la nueva última posición. A continuación se muestran los pasos de ordenación lenta:
- Encuentre el máximo de la array y colóquelo al final de la array por
- Llame recursivamente a la función slowsort para el máximo de los primeros N/2 elementos .
- Llame recursivamente a la función slowsort para el máximo de los N/2 elementos restantes .
- Encuentra el mayor de esos dos máximos y guárdalo al final.
- Llame recursivamente a la función slowsort para toda la array, excepto para el máximo.
- Imprime la array ordenada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement Slow sort
#include <bits/stdc++.h>
using namespace std;
// Function for swap two numbers using
// pointers
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// Function that implements Slow Sort
void slowSort(int A[], int i, int j)
{
// Base Case
if (i >= j)
return;
// Middle value
int m = (i + j) / 2;
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1, j);
// Swap if first element
// is lower than second
if (A[j] < A[m]) {
swap(&A[j], &A[m]);
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1);
}
// Function to print the array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = { 6, 8, 9, 4, 12, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
slowSort(arr, 0, N - 1);
// Display the sorted array
printArray(arr, N);
return 0;
}
Java
// Java program to implement Slow sort
import java.util.*;
class GFG
{
// Function that implements Slow Sort
static void slowSort(int A[], int i, int j)
{
// Base Case
if (i >= j)
return;
// Middle value
int m = (i + j) / 2;
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1, j);
// Swap if first element
// is lower than second
if (A[j] < A[m])
{
int temp = A[j];
A[j] = A[m];
A[m] = temp;
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1);
}
// Function to print the array
static void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i]+ " ");
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 6, 8, 9, 4, 12, 1 };
int N = arr.length;
// Function call
slowSort(arr, 0, N - 1);
// Display the sorted array
printArray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to implement Slow sort # Function that implements Slow Sort def slowSort(A, i, j): # Base Case if (i >= j): return; # Middle value m = (i + j) // 2; # Recursively call with left half slowSort(A, i, m); # Recursively call with right half slowSort(A, m + 1, j); # Swap if first element # is lower than second if (A[j] < A[m]): temp = A[j]; A[j] = A[m]; A[m] = temp; # Recursively call with whole # array except maximum element slowSort(A, i, j - 1); # Function to print the array def printArray(arr, size): i = 0; for i in range(size): print(arr[i], end=" "); print(); # Driver Code if __name__ == '__main__': arr = [6, 8, 9, 4, 12, 1]; N = len(arr); # Function call slowSort(arr, 0, N - 1); # Display the sorted array printArray(arr, N); # This code contributed by gauravrajput1
C#
// C# program to implement Slow sort
using System;
class GFG
{
// Function that implements Slow Sort
static void slowSort(int []A, int i, int j)
{
// Base Case
if (i >= j)
return;
// Middle value
int m = (i + j) / 2;
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1, j);
// Swap if first element
// is lower than second
if (A[j] < A[m])
{
int temp = A[j];
A[j] = A[m];
A[m] = temp;
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1);
}
// Function to print the array
static void printArray(int []arr, int size)
{
int i;
for (i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 6, 8, 9, 4, 12, 1 };
int N = arr.Length;
// Function call
slowSort(arr, 0, N - 1);
// Display the sorted array
printArray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
//Javascript program to implement Slow sort
// Function that implements Slow Sort
function slowSort(A, i,j)
{
// Base Case
if (i >= j)
return;
// Middle value
var m = parseInt((i + j) / 2);
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1, j);
// Swap if first element
// is lower than second
if (A[j] < A[m]) {
//swapp(A[j], A[m]);
var t = A[j];
A[j]=A[m];
A[m]=t;
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1);
}
// Function to print the array
function printArray(arr, size)
{
var i;
for (i = 0; i < size; i++)
document.write( arr[i] + " ");
document.write("<br>");
}
var arr = [ 6, 8, 9, 4, 12, 1 ];
var N = arr.length;
// Function call
slowSort(arr, 0, N - 1);
// Display the sorted array
printArray(arr, N);
//This code is contributed by SoumikMondal
</script>
Producción:
1 4 6 8 9 12
Complejidad del tiempo:
- Caso base: O(N ((log N)/(2+e)) donde, e > 0
- Caso promedio: O(N (log(N)/2) )
Incluso el mejor de los casos es peor que el tipo Bubble. Es menos eficiente que el tipo Stooge.
Sleep Sort: A continuación se muestran los pasos de Stooge sort:
- Cree subprocesos diferentes para cada uno de los elementos en la array de entrada y luego cada subproceso duerme durante un período de tiempo que es proporcional al valor del elemento de la array correspondiente.
- El subproceso que tiene la menor cantidad de tiempo de inactividad se despierta primero y se imprime el número y luego el segundo elemento menos y así sucesivamente.
- El elemento más grande se despierta después de mucho tiempo y luego el último elemento se imprime. Por lo tanto, la salida es ordenada.
Todo este proceso de subprocesos múltiples ocurre en segundo plano y en el núcleo del sistema operativo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement Sleep sort
#ifdef _WIN32
// sleep() function for windows machine
#include <Windows.h>
#else
// sleep() function for linux machine
#include <unistd.h>
#endif
#include <iostream>
#include <thread>
#include <vector>
using namespace std;
// Array for storing the sorted values
vector<int> A;
// Function for print the array
void printArray(vector<int> arr, int size)
{
int i;
for (i = 0; i < size; i++) {
cout << arr[i] << " ";
}
}
// The instruction set for a thread
void add(int x)
{
// Temporarily suspend execution
// of each thread for x amount
// of seconds
sleep(x);
// Every thead will wake up after
// a particular time and push the
// value in sorted array
A.push_back(x);
}
// Function for Sleep sort
void sleepSort(int arr[], int N)
{
vector<thread> threads;
for (int i = 0; i < N; i++) {
// New threads were launched by
// using function pointer as
// callable
threads.push_back(
thread(add, arr[i]));
}
// Waiting for each thread
// to finish execution
for (auto& th : threads) {
th.join();
}
// Display the sorted array
cout << "Array after sorting: ";
printArray(A, A.size());
}
// Driver Code
int main()
{
int arr[] = { 8, 9, 1, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// sleep_sort function call
sleepSort(arr, N);
return 0;
}
// To run compile using -pthread
// { 1, 3, 4, 8, 9}
Producción:
Array after sorting 1 3 4 8 9
Complejidad de tiempo: O (max (entrada) + N) donde, entrada = valor del elemento de array
La complejidad temporal de otros algoritmos depende de la cantidad de datos, pero para la clasificación de suspensión, depende de la cantidad de datos. Este algoritmo no funcionará para números negativos ya que un subproceso no puede dormir durante un período de tiempo negativo.
Bogo Sort: existen dos versiones de este algoritmo: una enumera todas las permutaciones hasta que llega a una ordenada, y una versión aleatoria que permuta aleatoriamente su entrada.
Ejemplo 1:
C++
// C++ program to implement Bogo Sort
// using permutation
#include <bits/stdc++.h>
using namespace std;
// Function to sort array using bogosort
void bogosort(int arr[], int N)
{
// Run the loop until
// array is not sorted
while (!is_sorted(arr, arr + N)) {
// All possible permutations
next_permutation(arr, arr + N);
}
}
// Driver Code
int main()
{
int arr[] = { 8, 9, 1, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
bogosort(arr, N);
// Display the sorted array
cout << "Array after sorting ";
for (int i = 0; i < N; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Producción:
Array after sorting 1 3 4 8 9
Complejidad del tiempo:
- Caso base: O(N)
- Caso Promedio: O(N!)
- Peor caso: O(N!)
Ejemplo 2:
C++
// C++ program to implement Bogo Sort
// using random shuffle
#include <bits/stdc++.h>
using namespace std;
// Function to check if array is
// sorted or not
bool isSorted(int a[], int N)
{
while (--N > 1) {
// Break condition for
// unsorted array
if (a[N] < a[N - 1])
return false;
}
return true;
}
// Function to generate permutation
// of the array
void shuffle(int a[], int N)
{
for (int i = 0; i < N; i++)
swap(a[i], a[rand() % N]);
}
// Function to sort array using
// Bogo sort
void bogosort(int a[], int N)
{
// If array is not sorted
// then shuffle array again
while (!isSorted(a, N)) {
shuffle(a, N);
}
}
// Function to print the array
void printArray(int a[], int N)
{
for (int i = 0; i < N; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
// Driver Code
int main()
{
int a[] = { 3, 2, 5, 1, 0, 4 };
int N = sizeof a / sizeof a[0];
// Function Call
bogosort(a, N);
printf("Array after sorting:");
printArray(a, N);
return 0;
}
Python3
# Python program to implement Bogo Sort
# using random shuffle
import random
# Function to check if array is
# sorted or not
def isSorted(a,N):
while(N > 1):
N = N - 1
# Break condition for
# unsorted array
if (a[N] < a[N - 1]):
return False
return True
# To generate permutation
# of the array
def shuffle(a, N):
for i in range (0, N):
r = random.randint(0,N-1)
a[i], a[r] = a[r], a[i]
# Function to sort array using
# Bogo sort
def bogosort(a, N):
# If array is not sorted
# then shuffle array again
while (not isSorted(a, N)):
shuffle(a, N)
# Function to print the array
def printArray(a, N):
for i in range(N):
print(a[i], end=" ")
print()
# Driver code to test above
a = [3, 2, 5, 1, 0, 4]
N=len(a)
# Function Call
bogosort(a,N)
print("Array after sorting:",end="")
printArray(a, N)
# This code is contributed by Pushpesh Raj.
Producción:
Array after sorting:0 1 2 3 4 5
Complejidad del tiempo:
- Caso base: O(N)
- Caso Promedio: O(N*N!)
- Peor caso: O(∞)
Claramente, en la peor de las situaciones, la ordenación de Bogo usando la reproducción aleatoria requiere una cantidad infinita de tiempo para ordenar una array, y podemos decir que este es el algoritmo de ordenación más lento. Pero lo que pasa con Bogo Sort es que viola algunas reglas en el Análisis de Complejidad . Una de las reglas es que realmente tienes que progresar hacia una meta. Obviamente, no puede perder el tiempo, por ejemplo, poniendo bucles de retardo. El algoritmo de clasificación lenta o clasificación de títeres en realidad nunca da un paso en falso. Una vez que intercambie dos Nodes, los Nodes estarán en el orden correcto entre sí y su orden no se invertirá.
Publicación traducida automáticamente
Artículo escrito por scorchingeagle y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA