Se dice que un algoritmo de ordenación es estable si dos objetos con claves iguales o iguales aparecen en el mismo orden en la salida ordenada que aparecen en la array de entrada para ordenar.
Cualquier algoritmo de ordenación basado en comparación que no sea estable por naturaleza puede modificarse para que sea estable cambiando la operación de comparación de claves para que la comparación de dos claves considere la posición como un factor para objetos con la misma clave o modificándolo de tal manera que su el significado no cambia y también se vuelve estable.
Ejemplo :
Note: Subscripts are only used for understanding the concept. Input : 4A 5 3 2 4B 1 Output : 1 2 3 4B 4A 5 Stable Selection Sort would have produced Output : 1 2 3 4A 4B 5
La ordenación por selección funciona encontrando el elemento mínimo y luego insertándolo en su posición correcta intercambiando con el elemento que está en la posición de este elemento mínimo. Esto es lo que lo hace inestable.
El intercambio puede afectar al empujar una tecla (digamos A) a una posición mayor que la tecla (digamos B), que son teclas iguales. lo que los hace fuera del orden deseado.
En el ejemplo anterior, 4 A se empujó después de 4 B y después de la clasificación completa, este 4 A permanece después de este 4 B. Por lo tanto, resulta en inestabilidad.
La ordenación por selección se puede hacer Estable si en lugar de intercambiar, el elemento mínimo se coloca en su posición sin intercambiar, es decir, colocando el número en su posición empujando cada elemento un paso hacia adelante.
En términos simples, use una técnica como la ordenación por inserción , que significa insertar el elemento en su lugar correcto.
EXPLICACIÓN CON EJEMPLO:
Example: 4A 5 3 2 4B 1
First minimum element is 1, now instead
of swapping. Insert 1 in its correct place
and pushing every element one step forward
i.e forward pushing.
1 4A 5 3 2 4B
Next minimum is 2 :
1 2 4A 5 3 4B
Next minimum is 3 :
1 2 3 4A 5 4B
Repeat the steps until array is sorted.
1 2 3 4A 4B 5
C++
// C++ program for modifying Selection Sort
// so that it becomes stable.
#include <iostream>
using namespace std;
void stableSelectionSort(int a[], int n)
{
// Iterate through array elements
for (int i = 0; i < n - 1; i++)
{
// Loop invariant : Elements till a[i - 1]
// are already sorted.
// Find minimum element from
// arr[i] to arr[n - 1].
int min = i;
for (int j = i + 1; j < n; j++)
if (a[min] > a[j])
min = j;
// Move minimum element at current i.
int key = a[min];
while (min > i)
{
a[min] = a[min - 1];
min--;
}
a[i] = key;
}
}
void printArray(int a[], int n)
{
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int a[] = { 4, 5, 3, 2, 4, 1 };
int n = sizeof(a) / sizeof(a[0]);
stableSelectionSort(a, n);
printArray(a, n);
return 0;
}
Java
// Java program for modifying Selection Sort
// so that it becomes stable.
class GFG
{
static void stableSelectionSort(int[] a, int n)
{
// Iterate through array elements
for (int i = 0; i < n - 1; i++)
{
// Loop invariant : Elements till
// a[i - 1] are already sorted.
// Find minimum element from
// arr[i] to arr[n - 1].
int min = i;
for (int j = i + 1; j < n; j++)
if (a[min] > a[j])
min = j;
// Move minimum element at current i.
int key = a[min];
while (min > i)
{
a[min] = a[min - 1];
min--;
}
a[i] = key;
}
}
static void printArray(int[] a, int n)
{
for (int i = 0; i < n; i++)
System.out.print(a[i]+ " ");
System.out.println();
}
// Driver code
public static void main (String[] args)
{
int[] a = { 4, 5, 3, 2, 4, 1 };
int n = a.length;
stableSelectionSort(a, n);
printArray(a, n);
}
}
// This code is contributed by Mr. Somesh Awasthi
Python3
# Python3 program for modifying Selection Sort
# so that it becomes stable.
def stableSelectionSort(a, n):
# Traverse through all array elements
for i in range(n):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i + 1, n):
if a[min_idx] > a[j]:
min_idx = j
# Move minimum element at current i
key = a[min_idx]
while min_idx > i:
a[min_idx] = a[min_idx - 1]
min_idx -= 1
a[i] = key
def printArray(a, n):
for i in range(n):
print("%d" %a[i], end = " ")
# Driver Code
a = [4, 5, 3, 2, 4, 1]
n = len(a)
stableSelectionSort(a, n)
printArray(a, n)
# This code is contributed
# by Mr. Raju Pitta
C#
// C# program for modifying Selection Sort
// so that it becomes stable.
using System;
class GFG
{
static void stableSelectionSort(int[] a, int n)
{
// Iterate through array elements
for (int i = 0; i < n - 1; i++)
{
// Loop invariant : Elements till
// a[i - 1] are already sorted.
// Find minimum element from
// arr[i] to arr[n - 1].
int min = i;
for (int j = i + 1; j < n; j++)
if (a[min] > a[j])
min = j;
// Move minimum element at current i.
int key = a[min];
while (min > i)
{
a[min] = a[min - 1];
min--;
}
a[i] = key;
}
}
static void printArray(int[] a, int n)
{
for (int i = 0; i < n; i++)
Console.Write(a[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main ()
{
int[] a = { 4, 5, 3, 2, 4, 1 };
int n = a.Length;
stableSelectionSort(a, n);
printArray(a, n);
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Javascript program for modifying Selection Sort
// so that it becomes stable.
function stableSelectionSort(a, n)
{
// Iterate through array elements
for (let i = 0; i < n - 1; i++)
{
// Loop invariant : Elements till
// a[i - 1] are already sorted.
// Find minimum element from
// arr[i] to arr[n - 1].
let min = i;
for (let j = i + 1; j < n; j++)
if (a[min] > a[j])
min = j;
// Move minimum element at current i.
let key = a[min];
while (min > i)
{
a[min] = a[min - 1];
min--;
}
a[i] = key;
}
}
function prletArray(a, n)
{
for (let i = 0; i < n; i++)
document.write(a[i]+ " ");
document.write("<br/>");
}
// driver function
let a = [ 4, 5, 3, 2, 4, 1 ];
let n = a.length;
stableSelectionSort(a, n);
prletArray(a, n);
</script>
Producción:
1 2 3 4 4 5
Este artículo es una contribución de Shubham Rana . 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 contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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