Programa C++ para reorganizar una lista dada de modo que consista en elementos mínimos máximos alternos

Dada una lista de números enteros, reorganice la lista de modo que consista en alternar elementos mínimos y máximos usando solo operaciones de lista . El primer elemento de la lista debe ser el mínimo y el segundo elemento debe ser el máximo de todos los elementos presentes en la lista. De manera similar, el tercer elemento será el siguiente elemento mínimo y el cuarto elemento será el siguiente elemento máximo, y así sucesivamente. No se permite el uso de espacio adicional. Ejemplos:

Input:  [1 3 8 2 7 5 6 4]
Output: [1 8 2 7 3 6 4 5]

Input:  [1 2 3 4 5 6 7]
Output: [1 7 2 6 3 5 4]

Input:  [1 6 2 5 3 4]
Output: [1 6 2 5 3 4]

La idea es ordenar la lista en orden ascendente primero. Luego comenzamos a sacar elementos del final de la lista y los insertamos en su posición correcta en la lista. A continuación se muestra la implementación de la idea anterior: 

// C++ program to rearrange a given list
// such that it consists of alternating
// minimum maximum elements
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange a given list
// such that it consists of alternating
// minimum maximum elements
void alternateSort(list<int>& inp)
{
    // sort the list in ascending order
    inp.sort();
 
    // get iterator to first element of
    // the list
    list<int>::iterator it = inp.begin();
    it++;
 
    for (int i = 1;
            i < (inp.size() + 1) / 2; i++)
    {
        // pop last element (next greatest)
        int val = inp.back();
        inp.pop_back();
 
        // insert it after next minimum
        // element
        inp.insert(it, val);
 
        // increment the pointer for next
        // pair
        ++it;
    }
}
 
// Driver code
int main()
{
    // Input list
    list<int> inp({ 1, 3, 8, 2, 7, 5, 6, 4 });
 
    // Rearrange the given list
    alternateSort(inp);
 
    // Print the modified list
    for (int i : inp)
        cout << i << " ";
 
    return 0;
}

Producción:

1 8 2 7 3 6 4 5

Complejidad de tiempo: O(N*logN), ya que estamos usando una función de clasificación.

Espacio auxiliar: O(1), ya que no estamos utilizando espacio extra.

¡ Consulte el artículo completo sobre Reorganizar una lista dada de modo que consista en elementos mínimos máximos alternos para obtener más detalles!