ordenación_estable() en C++ STL

stable_sort() se usa para ordenar los elementos en el rango [primero, último] en orden ascendente. Es como std::sort , pero stable_sort() mantiene el orden relativo de los elementos con valores equivalentes. Viene bajo el archivo de encabezado <algorithm> .

Sintaxis:

template< class RandomIterator>
void stable_sort( RandomIterator first, RandomIterator last );

o

template< class RandomIterator, class Compare>
void stable_sort( RandomIterator first, RandomIterator last, Compare comp );

Parámetros:

• first:  iterador que apunta al primer elemento del rango.
• último:  iterador que apunta al último elemento pasado en el rango.
• comp: función de predicado que acepta dos argumentos y devuelve verdadero si los dos argumentos están en orden y falso en caso contrario.

Valor devuelto: No devuelve nada.

Ejemplo:

// C++ program to demonstrate stable sort() in STL
#include <bits/stdc++.h>
using namespace std;
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    stable_sort(arr, arr + n);
 
    cout << "Array after sorting using "
            "stable_sort is : \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
 
    return 0;
}

Array after sorting using stable_sort is : 
0 1 2 3 4 5 6 7 8 9 

¿Cómo ordenar en orden descendente usando stable_sort()?

Al igual que sort(), stable_sort() toma un tercer parámetro que se utiliza para especificar el orden en que se ordenarán los elementos. Podemos pasar la función «mayor()» para ordenar en orden decreciente. Esta función hace la comparación de una manera que antepone un elemento mayor. 

Sintaxis:

// arr is the array and n is the size
stable_sort(arr, arr + n, greater<int>());  

Ejemplo:

// C++ program to demonstrate descending order
// stable sort using greater<>().
#include <bits/stdc++.h>
using namespace std;
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    stable_sort(arr, arr + n, greater<int>());
 
    cout << "Array after sorting : \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
 
    return 0;
}

Array after sorting : 
9 8 7 6 5 4 3 2 1 0 

¿Cuándo preferir stable_sort sobre sort()? 

En algún momento queremos asegurarnos de que el orden de los elementos iguales sea el mismo en la array ordenada que en la array original . Esto puede ser útil si estos valores tienen asociados otros campos. Por ejemplo, 

• Considere ordenar a los estudiantes por calificaciones, si dos estudiantes tienen las mismas calificaciones, es posible que deseemos mantenerlos en el mismo orden en que aparecen en la entrada. Consulte la estabilidad en los algoritmos de clasificación para obtener más detalles.
• Considere que tenemos intervalos de tiempo ordenados por hora de finalización y queremos ordenar por hora de inicio. Además, si dos horas de inicio son iguales, queremos mantenerlas ordenadas por la hora de finalización. Esto no está garantizado por sort().

// A C++ program to demonstrate STL stable_sort()
// to sort intervals according to start time.
#include <bits/stdc++.h>
using namespace std;
 
// An interval has start time and end time
struct Interval {
    int start, end;
};
 
// Compares two intervals according to starting
// times.
bool compareInterval(Interval i1, Interval i2)
{
    return (i1.start < i2.start);
}
 
int main()
{
    // Given intervals are sorted according to end time
    Interval arr[]
        = { { 1, 3 }, { 2, 4 }, { 1, 7 }, { 2, 19 } };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // sort the intervals in increasing order of
    // start time such that the start time intervals
    // appear in same order as in input.
    stable_sort(arr, arr + n, compareInterval);
 
    cout << "Intervals sorted by start time : \n";
    for (int i = 0; i < n; i++)
        cout << "[" << arr[i].start << ", " << arr[i].end
             << "] ";
 
    return 0;
}

Intervals sorted by start time : 
[1, 3] [1, 7] [2, 4] [2, 19] 

Diferencia entre ordenar y ordenar_estable()

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.