Capítulo 5: Ordenaciones y "Divide y vencerás"

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        a += 1;
    }
}

Siguiendo los pasos anteriores, podemos entender:

• el tamaño del problema es n, ya que nuestro código va a depender de este.
• Tampoco hay casos peores o mejores, debido a que n es solo un valor entero y no podemos fijarnos en valores.
• La instrucción más significativa será j <= n, esta es la que más se repite en cualquier caso.
• Desarrollando la función del coste:

$$T(n)=T(n)*T(n)=T(n^2)$$

La complejidad temporal de este algoritmo es cuadrática.

A continuación estudiaremos otros algoritmos y analizaremos sus costes temporales.

Divide y Vencerás

Divide y Vencerás es una técnica que se basa en la reducción de nuestro problema en problemas más pequeños, generalmente reduciendo el tamaño del input de manera recursiva, hasta que sean lo suficientemente simples como para ser resueltos directamente. Este paradigma es utilizado en muchos problemas para alcanzar complejidades de \(O(log\ n)\). Además, aunque parezca algo sencillo, se llega a usar en algoritmos tan complejos como la transformada discreta de Fourier.

Un ejemplo muy obvio de la aplicación de esta técnica es el Binary Search (o Busqueda Binaria).

Binary Search

Binary Search (o Busqueda Binaria) se basa en la búsqueda de un valor o solución de manera que se van descartando mitades del problema en los que se sabe que no se va a encontrar la solución. Para esto es vital tener cierto orden dentro del problema, debido a que si ese orden no existe, no se va a poder búsqueda binaria de ninguna forma.

Una de las aplicaciones más comunes es la búsqueda de un valor dentro de un array ordenado ascendentemente.

int bs(int arr[], int low, int high, int x)
{
if (high >= low) {
    int mid = low + (high - low) / 2;

    // Comprueba si el elemento es el del medio
    if (arr[mid] == x) return mid;

    // Si el elemento es menor que el del medio, 
    // sabemos que solo puede estar en la mitad inferior
    if (arr[mid] > x) return bs(arr, low, mid - 1, x);

    // En otro caso, está en la mitad superior
    return bs(arr, mid + 1, high, x);
}
return -1;  // No se encontró el número
}

// Método lanzadera
int bs(int arr[], int x) {
    return bs(arr, 0, arr.size() - 1, x);
}

En este ejemplo, vemos como la búsqueda dentro del array se va reduciendo a la mitad del tamaño con cada llamada que se realiza, haciendo que el máximo de llamadas que se requieren hacer sea, como máximo, (log n) llamadas. De esta forma, el coste temporal del algoritmo es bastante menor que en una búsqueda lineal en el peor caso:

$$T(n)\in \Omega(1),O(log\ n)$$

Ordenaciones (Sorts)

Las ordenaciones son algoritmos que permiten ordenar una secuencia de valores, ya sea de manera ascendente o descendente. Su utilidad viene de que podemos aprovechar que estas secuencias están ordenadas para aplicar ciertos algoritmos que son más óptimos que los convencionales para problemas que no están ordenados. A continuación veremos diferentes algoritmos de ordenación:

Función de utilidad

Los lenguajes de programación como Python, Java o C++ tienen funciones para ordenar listas fácilmente, en C++ se usa sort(). Estos son sus 3 usos principales:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3;

    // Ordenar arrays
    int a[n]; // [3, 1, 2]
    sort(a, a+n); // Ordenar n posiciones del array a empezando por el primer elemento

    // Ordenar strings...
    string s = "test";
    sort(s.begin(), s.end()); // Iteradores del principio y fin de la string

    // ... y vectores
    vector<int> v(n);  // [3, 1, 2]
    sort(v.begin(), v.end()); // Iteradores del principio y fin del vector
}

El uso de sort() es poco transparente, no se sabe a simple vista que pasa exactamente cuando llamamos a la función. Es la forma más eficiente de ordenar arrays y listas, por lo general no se deberían implementar funciones propias cada problema. Sin embargo este capítulo se explican algunos algoritmos de ordenación importantes que hay que saberse.

Bubble sort

Bubble sort es un algoritmo de ordenación sencillo de implementar, y que, como su nombre indica, si nos fijamos en la traza que deja, parece que mueve los elementos mayores hacia la derecha como si fuesen burbujas subiendo hasta el techo. Este algoritmo funciona de la siguiente manera:

• Realizando n pasadas, siendo n la cantidad de elementos en la lista, comenzando siempre por el elemento de la izquierda del todo.
• Repetiremos por cada posición una comparación entre el elemento en la posición i, y el elemento en la posición i + 1, y si el elemento en la posición i es más grande, se intercambian ambos elementos. De esta forma, en cada pasada lo que hacemos es mover el elemento de mayor valor a la derecha del todo, quedando este ordenado, y reduciendo la cantidad de elementos a ordenar con cada pasada, ya que no tendremos que tener este en cuenta para las próximas iteraciones.

Por ejemplo, aquí tenemos una traza del algoritmo:

Inicio: [1,5,4,2,3,3]
Pasada 0:
    i = 0 -> [1,5,4,2,3,3]
    i = 1 -> [1,4,5,2,3,3]
    i = 2 -> [1,4,2,5,3,3]
    i = 3 -> [1,4,2,3,5,3]
    i = 4 -> [1,4,2,3,3,5]
    
Pasada 1:
    i = 0 -> [1,4,2,3,3,5]
    i = 1 -> [1,2,4,3,3,5]
    i = 2 -> [1,2,3,4,3,5]
    i = 3 -> [1,2,3,3,4,5]

Pasada 2:
    ...
    i = 2 -> [1,2,3,3,4,5]

Pasada 3: 
    ...
    i = 1 -> [1,2,3,3,4,5]
    
Pasada 4:
    i = 0 -> [1,2,3,3,4,5]

Podemos observar como después de la segunda pasada el array ya se encuentra ordenado, pero aún así, se realizan las pasadas 2, 3 y 4. Esto es debido al algoritmo en sí, necesita una forma de comprobar que todos los elementos están ordenados, y sin realizar esas pasadas extra, no se puede confirmar.

Dicho esto, podemos ver que el coste temporal de este algoritmo es, en cualquier caso:

$$T(n)=O(n^2)$$

Esto lo posiciona como uno de los algoritmos de ordenación más lentos, y por lo tanto, menos recomendables de utilizar. Sin embargo, dada su fácil implementación y su simplicidad, es bastante usado para introducir el concepto de ordenación.

Una posible implementación en C++ es:

void bubbleSort(int arr[], int n) 
{ 
    for (i = 0; i < n - 1; i++) 
        for (j = 0; j < n - i - 1; j++) 
            if (arr[j] > arr[j + 1]) 
                swap(arr[j], arr[j + 1]); 
}

Insertion sort

Insertion sort, como su nombre indica, se basa en insertar los valores en su posición “ordenada”. Esto se consigue de la siguiente forma:

• Se asume que el primer elemento está ordenado.
• En n iteraciones, se seleccionará el siguiente siguiente elemento a ordenar, y se moverá, dentro de la sublista ordenada que se va creando, en su posición ordenada, solamente si es menor que el elemento mayor de esta sublista. Esta última condición, nos ahorra cierta cantidad de comparaciones, cosa que reduce el coste temporal del algoritmo en el mejor caso.

Un ejemplo del funcionamiento de este algoritmo es:

Inicio:       [2, 13, 9, 7, 10] 
Iteración 0:  [2, 13, 9, 7, 10] // [2]
Iteración 1:  [2, 13, 9, 7, 10] // [2, 13]
Iteración 2:  [2, 9, 13, 7, 10] // [2, 9, 13]
Iteración 3:  [2, 7, 9, 13, 10] // [2, 7, 9, 13]
Iteración 4:  [2, 7, 9, 10, 13] // [2, 7, 9, 10, 13]

El coste temporal de este algoritmo contiene un mejor y un peor, caso, y es que si la lista está ordenada, no requeriremos de comparaciones extra para las ocasiones en las que debemos insertar un elemento en una posición diferente a la que está. En cambio, si la lista ordenada de manera inversa, nos encontraremos frente al peor caso, ya que en cada iteración deberemos comparar el elemento con todos los de la sublista hasta llegar a su posición ordenada.

$$T(n) \in \Omega(n), O(n^2)$$

Una posible implementación de este algoritmo en C++ es:

void insertionSort(int arr[])
{
    int key;
    int n = arr.size();
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Selection sort

Selection sort se basa en seleccionar los elementos de menor a mayor(en este caso), e ir ubicándolos en los que serían sus posiciones ordenadas. Es decir:

• Itera sobre la lista para encontrar el menor elemento y ubícalo en la primera posición de la lista.
• Repite pero con los siguientes elementos, y situándolos en orden en la lista.

Ejemplo:

Inicio:       [2, 13, 9, 7, 10]
Iteración 0:  [2, 13, 9, 7, 10]
Iteración 1:  [2, 7, 9, 13, 10]
Iteración 2:  [2, 7, 9, 13, 10]
Iteración 0:  [2, 7, 9, 10, 13]

Como podemos ver, este algoritmo no da lugar a ningún caso mejor, siempre va a realizar la misma cantidad de comparaciones, por lo tanto, su coste temporal es:

$$T(n) = O(n^2)$$s

Una posible implementación en C++ es:

void selectionSort(int arr[]) {
    int min_idx;
    for (i = 0; i < arr.size() - 1; i++) {
        
        // Buscamos el menor
        min_idx = i;
        for (j = i + 1; j < arr.size(); j++) {
            if (arr[j] < arr[min_idx]) min_idx = j;
        }

        // Cambiamos su posición
        if (min_idx != i) swap(arr[min_idx], arr[i]);
    }
}

Merge sort

Basado en la técnica de Divide y Vencerás, el algoritmo de merge sort se divide en los siguientes pasos:

• Caso base: Cualquier lista de tamaño 1 está ordenada.
• Partiendo de lo anterior, se divide de manera recursiva la lista a ordenar hasta que todas las sublistas son de tamaño 1.
• A partir de ahora, combinar y ordenar pares de sublistas que se han obtenido de manera recursiva, hasta que se alcanza la lista completamente ordenada, sabiendo que es más eficiente ordenar dos listas ordenadas que dos listas no ordenadas.

Este ejemplo lo dejará más claro:

Inicio:                  [2, 13, 9, 7, 10, 32, 11]
Division 0:     [2, 13, 9, 7]                 [10, 32, 11]
División 1:   [2, 13]        [9, 7]        [10, 32]     [11]
División 3: [2]    [13]    [9]    [7]    [10]    [32]   [11]
Unión 0:       [2, 13]        [7, 9]        [10, 32]     [11]
Unión 1:        [2, 7, 9, 13]                 [10, 11, 32]
Unión 2:                  [2, 7, 9, 10, 11, 13, 32]

De esta forma, el merge sort consigue un coste temporal de:

$$T(n)=O(n log n)$$

Una posible implementación en C++ es:

void merge(vector<int> &res, vector<int> &l1, vector<int> &l2) {
    // Combina y ordena ambas listas en res
    int i1 = 0, i2 = 0;
    for (int i = 0; i < res.size(); i++) {
        if (l1.size() == i1) {
            res[i] = l2[i2++];
        } else if (l2.size() == i2) {
            res[i] = l1[i1++];
        } else if (l2[i2] < l1[i1]) {
            res[i] = l2[i2++];
        } else {
            res[i] = l1[i1++];
        }
    }
}


void solve(vector<int> &l) {
    // Caso base
    if (l.size() == 1) { return; }
    
    // División de la lista
    int mid = (l.size() / 2) - 1;
    vector<int> l1(l.begin(), l.begin() + mid + 1);
    vector<int> l2(l.begin() + mid + 1, l.begin() + l.size());
    
    // Llamada recursiva para dividir
    solve(l1);
    solve(l2);
    
    // Unir sublistas
    merge(l, l1, l2);
}

Quick sort

Al igual que el Merge sort, el algoritmo Quick sort también se basa en la técnica de Divide y Vencerás. Este tipo de algoritmos consiste en partir el problema en partes más pequeñas hasta que cada parte sea lo suficientemente simple para que se pueda resolver de manera directa.

Hay multiples formas de implementar Quick sort, cada una tiene sus diferencias aunque la idea principal es la misma. Vamos a ver como se puede implementar de la forma más eficiente en cuanto a memoria, 'in-place', que significa que no usaremos ningún array auxiliar:

Comenzamos con una lista de elementos sin ordenar:

[1, 5, 9, 4, 2, 3, 3, 8, 5]

Ahora, repetiremos los pasos a continuación hasta que toda la lista este ordenada. Aunque primero debemos que comprender el concepto pivote, es un elemento que seleccionaremos al azar en el segmento de la lista que queremos ordenar. Cuando hayamos elegido pivote, tendremos que mover los elementos menores a este a un lado del pivote y los que son mayores al otro lado; de esta manera sabemos que el pivote está ordenado, en su posición final, y ahora tendremos que aplicar Quick sort a ambos lados recursivamente para ordenar toda la lista.

1. Para el segmento que queremos ordenar, seleccionaremos un pivote, por ejemplo el último elemento del segmento.

2. Recorremos todos los elementos del segmento (menos el último) de principio a final

• Si un elemento es estrictamente más pequeño que el pivote, intercambiaremos este elemento por el primer elemento que no sea más pequeño que el pivote de la lista, para ello habrá que mantener un index que se incremente cada vez que realicemos un cambio. Por ejemplo para la lista inicial seleccionaremos el último elemento, 5, como pivote:

Iteración 0:
i = 0:  [1, 5, 9, 4, 2, 3, 3, 8, 5] // Se cambia 1 a la pos 0
i = 1:  [1, 5, 9, 4, 2, 3, 3, 8, 5] // No hace falta mover el 5
i = 2:  [1, 5, 9, 4, 2, 3, 3, 8, 5] // El 9 es mayor, no se mueve
i = 3:  [1, 4, 9, 5, 2, 3, 3, 8, 5] // Se cambia 4 a la pos 1
i = 4:  [1, 4, 2, 5, 9, 3, 3, 8, 5] // Se cambia 2 a la pos 2
i = 5:  [1, 4, 2, 3, 9, 5, 3, 8, 5] // Se cambia 3 a la pos 3
i = 6:  [1, 4, 2, 3, 3, 5, 9, 8, 5] // Se cambia 3 a la pos 4
i = 7:  [1, 4, 2, 3, 3, 5, 9, 8, 5] // El 8 es mayor, no se mueve
i = 8:  [1, 4, 2, 3, 3, 5, 9, 8, 5] // Se cambia el pivote a pos 5.

Y ahora tenemos los elementos más pequeños que el pivote a un lado y los más grandes a otros.

1. Ahora simplemente repetiremos desde el paso 1 para cada lado del segmento, sin incluir el pivote, ya que está ordenado.

Pese a que el algoritmo de Quick sort es muy potente, debemos tener en cuenta su mayor debilidad, y es que la elección del pivote es muy importante, dado que puede determinar si el algoritmo será eficiente. Para más información sobre la elección de pivotes, click aquí.

Dependiendo de la posición en la que acaba el pivote tras cada iteración, nos podemos encontrar frente a un best case si este termina en el medio, o un worst case, si el pivote acaba en un extremo de la lista, debido a que esto determinará la cantidad de llamadas recursivas que se deben hacer. Esto nos deja con una complejidad temporal de:

$$T(n) \in \Omega(n log n), O(n^2)$$

Una posible implementación es:

int *a;

void quicksort(int l, int r) { // Ambos índices válidos
    if (r-l < 1) return;
    int pivot = a[r]; // En este caso, cojemos el último
    int i = l, j = l;
    
    while (j <= r) {
        // Reemplazamos si es menor que el pivot
        if (a[j] < pivot) {
            swap(a[i], a[j]);
            ++i;
        }
        ++j;
    }
    
    // Cambia el pivot por su posición ordenada
    swap(a[i], a[r]);
    
    // Ordena ambos lados
    quicksort(l, i-1);
    quicksort(i+1, j-1);

}

Pigeonhole sort

Este método de ordenación también es muy fácil de implementar, además es un algoritmo muy especial, porque su complejidad de tiempo es O(n), ¡increible! Pero tiene sus limitaciones, los números que queremos ordenar solo pueden ser enteros, y además no deben ser excesivamente grandes ($210^5$) o pequeños ($-210^5$). Así se implementa:

Empezamos con una lista de elementos:

[1, 3, 3, -1, 0]

Obtendremos el valor mínimo y máximo de la lista,  - 1 y 3. Ahora crearemos un array auxiliar de tamaño (max - min +  1) para llevar una cuenta de cuantas veces ha salido ese número, además para guardar números muy grandes o negativos, calcularemos un offset, que es la diferencia entre el número más pequeño y el 0. El array auxiliar será:

Con offset = -1 

(Con offset):         [-1, 0, 1, 2, 3] // Básicamente, el rango de [min...max]
Array auxiliar:       [1, 1, 1, 0, 2]  // -1 aparece 1 vez, el 0,1 vez...
Indices:               0  1  2  3  4

Se puede ver como el array auxiliar guarda un -1, un 0, un 1 y dos 3. Ahora solo queda imprimirlos de izquierda a derecha para obtener (acordándose del offset):

[-1, 0, 1, 3, 3]

Aquí hay un ejemplo más visual:

              0   1   2    3  4
Inicio:      [12, 16, 19, 10, 9]

Tamaño de array aux = max - min = 19 - 9 = 10

      0  1  2  3  4  5  6  7  8  9  10
Aux: [1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1]
Num:  9  10    12          16       19
Resultado:  [9, 10, 12, 16, 19]

Radix sort

Radix sort es un algoritmo de ordenación un tanto especial, ya que en vez de comparar valores para ordenar estos, lo que hace es ordenar los elementos comparándolos dígito por dígito, de esta forma, no solo es eficiente ordenando números, sino que también strings.

La idea clave detrás de Radix Sort es explotar el concepto de valor posicional. Se supone que ordenar números dígito por dígito eventualmente dará como resultado una lista completamente ordenada. La clasificación por base se puede realizar utilizando diferentes variaciones, como la clasificación por base del dígito menos significativo (LSD) o la clasificación por base del dígito más significativo (MSD), dependiendo del dígito por el cuál se quiera empezar.

Los pasos a seguir para este algoritmo son:

1. Busca el mayor elemento dentro de la lista, y dependiendo de la cantidad de dígitos(o caracteres que posee), se realizarán tantas iteraciones como dígitos.
2. Por cada dígito, se realiza un sort de todos los elementos, usando para la comparación el dígito en la posición que corresponde(por ejemplo, si usamos LSD, comenzaremos por el dígito de la derecha del todo, e iremos hacia la izquierda). Es importante tener en cuenta que el método de sorting que utilicemos debe ser estable, es decir, dos elementos iguales deben tener el mismo orden de entrada que de salida.

Un ejemplo de este algoritmo es:

Inicio:   [170, 45, 75, 90, 802, 24, 2, 66]
Mayor elemento -> 802, tiene 3 dígitos
Utilizaremos LSD, es decir, comenzamos con las unidades

Iteración 0: Sort en base a las unidades
[170, 90, 802, 2, 24, 45, 75, 66]

Iteración 1: Sort en base a las decenas
[802, 2, 24, 45, 66, 170, 75, 90]

Iteración 2: Sort en base a las centenas
[2, 24, 45, 66, 75, 90, 170, 802]

De esta forma, el coste temporal de este algoritmo puede llegar a ser mejor incluso que el de Quick sort o Merge sort para grandes conjuntos de información, pero se ha de tener en cuenta la cantidad de dígitos de los elementos, ya que esto determina la cantidad de iteraciones.

$$T(n)=O(d * (n + b))$$

• d: Cantidad de dígitos
• n: tamaño de la lista
• b: base del sistema numérico que se utiliza

Una posible implementación de este algoritmo es:

// Obtener el mayor elemento
int getMax(int arr[], int n)
{
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

// Utilizaremos counting sort
void countSort(int arr[], int n, int exp)
{
    // count contiene en cada casilla, la cantidad de números con ese
    // dígito i en la posición específica
    int output[n], i, count[10] = {0};

    // Conteo
    for (i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Calcula la cuenta cumulativa, sumando los anteriores
    for (i = 1; i < 10; i++)
        count[i] += count[i-1];

    // Insertar valores en output
    for (i = n - 1; i >= 0; i--)
    {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Asignar output a arr
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixsort(int arr[], int n)
{
    int exp, m;
    m = getMax(arr, n);

    // LLamada por cada dígito en el mayor elemento
    for (exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

Pair

Mencionar también que se puede utilizar la función sort para arrays, vectores y strings.

La clase pair nos permite juntar dos valores, aún siendo de tipo de datos diferentes, como si fuesen una única unidad. Generalmente son utilizados para almacenar tuplas.

// Declaración de un pair, debemos especificar los tipos de datos
pair<int, char> pareja;

// Otras formas de inicializar un pair
pair pareja1(1, 'a'); // Se infieren los tipos de datos
pair pareja2;
pareja2 = make_pair('a', 8);

// Leer o escribir sobre un pair
pareja.first = 4;
pareja.second = 'G';

cout << pareja.first << endl;
> 4

// Otras posibilidades a considerar
pareja.swap(pareja1) // Cambia los contenidos de cada pair

// Se pueden usar operadores ==, <, >, !=... entre pairs
// Pero todos excepto == comparan solamente el first.
pareja = make_pair(2, 'G');
pareja1 = make_pair(8, 'D');
cout << pareja == pareja1 << endl; 
> false

cout << pareja < pareja1 << endl;
> true

Los pairs pueden resultar muy útiles cuando queremos mantener cierta relación entre pares de valores para resolver algún problema, pero entonces nos puede venir a la mente: ¿Y cómo se ordenan? Aquí tenemos la explicación.

La función std::sort() es una función que utilizaremos en incontables ocasiones, ya que nos ahorra implementar un método de sorting para cada problema, y posee bastante versatilidad con la capacidad de recibir comparadores como parámetro de la función. Estos comparadores serán funciones externas que nos servirán para devolver un boolean dependiendo de si el elemento que se está comparando debe ser reemplazado o no.

pair<int, int> lista[4];
lista[0] = make_pair(3, 8);
lista[1] = make_pair(8, 3);
lista[2] = make_pair(7, 5);
lista[3] = make_pair(7, 4);

sort(lista, lista+3);
// lista+3 es el puntero al último elemento del array MÁS una posición. Se ordenarán
// todos los pairs por defecto en orden creciente del primer elemento de la pair,
// y en caso de ser iguales (a.first == b.first) entonces se ordenan estos elementos 
// en orden creciente del segundo elemento de la pair
> [0] = {3, 8}
[1] = {7, 4}
[2] = {7, 5}
[3] = {8, 3}

// Si queremos ordenar elementos con un criterio propio, podemos pasar como tercer
// parámetro al método sort una función que devuelve verdadero si el elemento a se
// quiere poner antes que el elemento b

// En este caso para ordenar el array de parejas por el segundo elemento de la pair
// se podría usar este criterio de ordenación, si a.second es menor que b.second, 
// entonces a irá antes que b en la lista
lista.sort([] (auto &a, auto &b) {return a.second < b.second});
// o también
sort(lista, lista + 3, [](auto &a, auto &b {
    return a.second < b,second
}));

La ordenación de una lista de pairs mediante la función sort nos da una complejidad temporal de:

$$T(n)=O(n log n)$$

Tuplas

La clase tuple nos permite juntar más de dos valores (a diferencia de pair), incluso de tipos de datos diferentes, como si fuesen una única unidad. Son especialmente útiles cuando queremos agrupar varias informaciones relacionadas en un solo elemento.

// Declaración de un tuple, debemos especificar los tipos de datos
tuple<int, char, string> tupla; 

// Otras formas de inicializar una tupla
tuple<int, char, string> tupla1(1, 'a', "hola");  
auto tupla2 = make_tuple(2, 'b', "mundo"); 

// Leer o escribir sobre una tupla
get<0>(tupla) = 5;  
get<1>(tupla) = 'Z';  
get<2>(tupla) = "adiós";  

cout << get<0>(tupla) << endl;  
// > 5

tupla = make_tuple(2, 'G', "abc");  
tupla1 = make_tuple(8, 'D', "xyz");  

// Se pueden comparar tuplas usando los operadores ==, <, >, !=, etc.
cout << (tupla == tupla1) << endl;
// > false  

cout << (tupla < tupla1) << endl;  
// > true