La clasificación de Stalin (también ‘ clasificación de dictador ‘ y ‘ clasificación de triunfo ‘) es un algoritmo de ‘clasificación’ sin sentido en el que cada elemento que no está en el orden correcto simplemente se elimina de la lista.
Este algoritmo de clasificación es una variación menos destructiva de la clasificación de Stalin, que en realidad clasificará la lista: en este caso, los elementos que no están en orden se mueven al comienzo de la lista en el orden en que aparecieron en la lista original. Luego se repite el proceso hasta que se ordena la lista.
Ejemplos:
Entrada: arr[] = {2, 1, 4, 3, 6, 5, 8, 7, 10, 9}
Salida: 1 2 3 4 5 6 7 8 9 10
Explicación:
Los elementos que se movieron al inicio de la lista está marcada en negrita:
[2, 1, 4, 3, 6, 5, 8, 7, 10, 9]
[ 1, 3, 5, 7, 9 2, 4, 6, 8, 10]
[ 2, 4, 6, 8 , 1, 3, 5, 7, 9, 10]
[ 1, 3, 5, 7, 2, 4, 6, 8, 9, 10]
[ 2, 4, 6, 1, 3, 5, 7, 8, 9, 10]
[ 1, 3, 5, 2, 4, 6, 7, 8, 9, 10]
[ 2, 4, 1, 3, 5, 6, 7, 8, 9, 10]
[ 1, 3, 2, 4, 5, 6, 7, 8, 9, 10]
[ 2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Entrada: [9, 10, 7, 8, 5, 6, 3, 4, 1, 2]
Salida: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explicación:
[9 , 10, 7, 8, 5, 6, 3, 4, 1, 2]
[ 7, 8, 5, 6, 3, 4, 1, 2 , 9, 10]
[ 5, 6, 3, 4, 1 , 2 , 7, 8, 9, 10]
[ 3, 4, 1, 2 , 5, 6, 7, 8, 9, 10]
[ 1, 2 , 3, 4, 5, 6, 7, 8, 9 , 10]
Enfoque: la idea es empujar los elementos al comienzo de la array siempre que sea menor que el elemento anterior. Repita este paso hasta que no haya ningún elemento que no esté en el orden correcto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to sort the
// array by using the variation
// of the Stalin sort
#include<bits/stdc++.h>
using namespace std;
// Function to sort the array
void variationStalinsort(vector<int> arr)
{
int j = 0;
while(true)
{
int moved = 0;
for(int i = 0;
i < (arr.size() - 1 - j); i++)
{
if (arr[i] > arr[i + 1])
{
vector<int>::iterator index;
int temp;
index = arr.begin() + i + 1;
temp = arr[i + 1];
arr.erase(index);
arr.insert(arr.begin() + moved, temp);
moved++;
}
}
j++;
if (moved == 0)
{
break;
}
}
for(int i = 0; i < arr.size(); i++)
{
cout << arr[i] << ", ";
}
}
// Driver Code
int main()
{
vector<int> arr = { 2, 1, 4, 3, 6,
5, 8, 7, 10, 9 };
// Function call
variationStalinsort(arr);
}
// This code is contributed by avanitrachhadiya2155
Java
// Java implementation to sort the
// array by using the variation
// of the Stalin sort
import java.util.*;
class GFG
{
// Function to sort the array
static void variationStalinsort(Vector<Integer> arr)
{
int j = 0;
while(true)
{
int moved = 0;
for(int i = 0;
i < (arr.size() - 1 - j); i++)
{
if (arr.get(i) > arr.get(i+1))
{
//Iterator<Integer> index = arr.iterator();
int index;
int temp;
index = arr.get(i);
temp = arr.get(i + 1);
arr.removeElement(index);
arr.add( i, temp);
arr.removeElement(temp);
arr.add(i+1, index);
moved++;
}
}
j++;
if (moved == 0)
{
break;
}
}
System.out.print(arr);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 1, 4, 3, 6,
5, 8, 7, 10, 9 };
Vector<Integer> arr1 = new Vector<>();
for(int i = 0; i < arr.length; i++)
arr1.add(arr[i]);
// Function call
variationStalinsort(arr1);
}
}
// This code is contributed by aashish1995
Python3
# Python3 implementation to sort # the array by using the variation # of the Stalin sort # Function to sort the array def variationStalinsort(arr): j = 0 while True: moved = 0 for i in range(len(arr) - 1 - j): if arr[i] > arr[i + 1]: arr.insert(moved, arr.pop(i + 1)) moved += 1 j += 1 if moved == 0: break return arr # Driver Code if __name__ == "__main__": arr = [2, 1, 4, 3, 6, 5, 8, 7, 10, 9] # Function Call print(variationStalinsort(arr))
C#
// C# implementation to sort the
// array by using the variation
// of the Stalin sort
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to sort the array
static void variationStalinsort(List<int> arr)
{
int j = 0;
while(true)
{
int moved = 0;
for(int i = 0;
i < (arr.Count - 1 - j); i++)
{
if (arr[i] > arr[i+1])
{
//Iterator<Integer> index = arr.iterator();
int index;
int temp;
index = arr[i];
temp = arr[i + 1];
arr.Remove(index);
arr.Insert(i , temp);
arr.Remove(temp);
arr.Insert(i + 1 ,index);
moved++;
}
}
j++;
if (moved == 0)
{
break;
}
}
foreach(int i in arr)
Console.Write(i + " ");
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 2, 1, 4, 3, 6,
5, 8, 7, 10, 9 };
List<int> arr1 = new List<int>();
for(int i = 0; i < arr.Length; i++)
arr1.Add(arr[i]);
// Function call
variationStalinsort(arr1);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript implementation to sort the
// array by using the variation
// of the Stalin sort
// Function to sort the array
function variationStalinsort(arr)
{
let j = 0;
while(true)
{
let moved = 0;
for(let i = 0;
i < (arr.length - 1 - j);
i++)
{
if (arr[i] > arr[i+1])
{
// Iterator<Integer> index = arr.iterator();
let index;
let temp;
index = arr[i];
temp = arr[i + 1];
arr.splice(i, 1);
arr.splice(i, 0, temp);
arr[i] = temp;
arr.splice(i + 1, 1);
arr.splice(i + 1, 0, index)
arr[i + 1] = index;
moved++;
}
}
j++;
if (moved == 0)
{
break;
}
}
document.write("[" + arr + "]");
}
// Driver Code
let arr = [ 2, 1, 4, 3, 6,
5, 8, 7, 10, 9 ];
let arr1 = [];
for(let i = 0; i < arr.length; i++)
arr1.push(arr[i]);
// Function call
variationStalinsort(arr1);
// This code is contributed by rag2127
</script>
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Peor tiempo de complejidad: O(N 2 )
Mejor tiempo de complejidad: O(N)
Publicación traducida automáticamente
Artículo escrito por jankoornstra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA