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 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;
}

// Java program to rearrange a given list such that it
// consists of alternating minimum maximum elements
import java.util.*;
 
class AlternateSort
{
    // Function to rearrange a given list such that it
    // consists of alternating minimum maximum elements
    // using LinkedList
    public static void alternateSort(LinkedList<Integer> ll)
    {
        Collections.sort(ll);
         
        for (int i = 1; i < (ll.size() + 1)/2; i++)
        {
            Integer x = ll.getLast();
            ll.removeLast();
            ll.add(2*i - 1, x);
        }
         
        System.out.println(ll);
    }
     
    public static void main (String[] args) throws java.lang.Exception
    {
        // input list
        Integer arr[] = {1, 3, 8, 2, 7, 5, 6, 4};
         
        // convert array to LinkedList
        LinkedList<Integer> ll = new LinkedList<Integer>(Arrays.asList(arr));
         
        // rearrange the given list
        alternateSort(ll);
    }
}

# Python program to rearrange a given list such that it
# consists of alternating minimum maximum elements
inp = []
 
# Function to rearrange a given list such that it
# consists of alternating minimum maximum elements
def alternateSort():
 
    global inp
     
    # sort the list in ascending order
    inp.sort()
 
    # get index to first element of the list
    it = 0
    it = it + 1
     
    i = 1
     
    while ( i < (len(inp) + 1)/2 ):
     
        i = i + 1
         
        # pop last element (next greatest)
        val = inp[-1]
        inp.pop()
 
        # insert it after next minimum element
        inp.insert(it, val)
 
        # increment the pointer for next pair
        it = it + 2
     
# Driver code
 
# input list
inp=[ 1, 3, 8, 2, 7, 5, 6, 4 ]
 
# rearrange the given list
alternateSort()
 
# print the modified list
print (inp)
 
# This code is contributed by Arnab Kundu

// C# program to rearrange a given list such that it
// consists of alternating minimum maximum elements
using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to rearrange a given list such that it
    // consists of alternating minimum maximum elements
    // using List
    public static void alternateSort(List<int> ll)
    {
        ll.Sort();
         
        for (int i = 1; i < (ll.Count + 1)/2; i++)
        {
            int x = ll[ll.Count-1];
            ll.RemoveAt(ll.Count-1);
            ll.Insert(2*i - 1, x);
        }
        foreach(int a in ll)
        {
            Console.Write(a+" ");
        }
         
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        // input list
        int []arr = {1, 3, 8, 2, 7, 5, 6, 4};
         
        // convert array to List
        List<int> ll = new List<int>(arr);
         
        // rearrange the given list
        alternateSort(ll);
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// JavaScript program to rearrange a given list such that it
// consists of alternating minimum maximum elements
let inp = []
 
// Function to rearrange a given list such that it
// consists of alternating minimum maximum elements
function alternateSort(){
 
    // sort the list in ascending order
    inp.sort()
 
    // get index to first element of the list
    let it = 0
    it = it + 1
     
    let i = 1
     
    while ( i < (inp.length + 1)/2 ){
     
        i = i + 1
         
        // pop last element (next greatest)
        let val = inp[inp.length-1]
        inp.pop()
 
        // insert it after next minimum element
        inp.splice(it,0, val)
 
        // increment the pointer for next pair
        it = it + 2
    }
}
     
// Driver code
 
// input list
inp=[ 1, 3, 8, 2, 7, 5, 6, 4 ]
 
// rearrange the given list
alternateSort()
 
// print the modified list
for(let x of inp){
    document.write(x," ")
}
 
// This code is contributed by shinjanpatra
 
</script>

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 usando espacio extra.

Este artículo es una contribución de Aditya Goel . 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 review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.