Clasificación alternativa

Dada una array de enteros, imprima la array de tal manera que el primer elemento sea el primer máximo y el segundo elemento sea el primer mínimo y así sucesivamente.

Ejemplos: 

Input : arr[] = {7, 1, 2, 3, 4, 5, 6}
Output : 7 1 6 2 5 3 4

Input : arr[] = {1, 6, 9, 4, 3, 7, 8, 2}
Output : 9 1 8 2 7 3 6 4

Una solución simple es imprimir primero el elemento máximo, luego el mínimo, luego el segundo máximo, y así sucesivamente. La complejidad temporal de este enfoque es O(n ² ).

Una solución eficiente implica seguir los pasos. 

1. Ordene la array de entrada usando un algoritmo O(n Log n). 
2. Mantenemos dos punteros, uno desde el principio y otro desde el final en una array ordenada. Alternativamente, imprimimos elementos apuntados por dos punteros y los movemos uno hacia el otro.

Implementación:

// C++ program to print an array in alternate
// sorted manner.
#include <bits/stdc++.h>
using namespace std;
 
// Function to print alternate sorted values
void alternateSort(int arr[], int n)
{
    // Sorting the array
    sort(arr, arr+n);
 
    // Printing the last element of array
    // first and then first element and then
    // second last element and then second
    // element and so on.
    int i = 0, j = n-1;
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }
 
    // If the total element in array is odd
    // then print the last middle element.
    if (n % 2 != 0)
        cout << arr[i];
}
 
// Driver code
int main()
{
    int arr[] = {1, 12, 4, 6, 7, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    alternateSort(arr, n);
    return 0;
}

// Java program to print an array in alternate
// sorted manner
import java.io.*;
import java.util.Arrays;
  
class AlternativeString
{
    // Function to print alternate sorted values
    static void alternateSort(int arr[], int n)
    {
        Arrays.sort(arr);
 
        // Printing the last element of array
        // first and then first element and then
        // second last element and then second
        // element and so on.
        int i = 0, j = n-1;
        while (i < j) {
            System.out.print(arr[j--] + " ");
            System.out.print(arr[i++] + " ");
        }
      
        // If the total element in array is odd
        // then print the last middle element.
        if (n % 2 != 0)
            System.out.print(arr[i]);
    }
 
    /* Driver program to test above functions */
    public static void main (String[] args)
    {
        int arr[] = {1, 12, 4, 6, 7, 10};
        int n = arr.length;
        alternateSort(arr, n);
    }
}
/*This code is contributed by Prakriti Gupta*/

# Python 3 program to print an array
# in alternate sorted manner.
 
# Function to print alternate sorted
# values
def alternateSort(arr, n):
 
    # Sorting the array
    arr.sort()
 
    # Printing the last element of array
    # first and then first element and then
    # second last element and then second
    # element and so on.
    i = 0
    j = n-1
     
    while (i < j):
     
        print(arr[j], end =" ")
        j-= 1
        print(arr[i], end =" ")
        i+= 1
 
    # If the total element in array is odd
    # then print the last middle element.
    if (n % 2 != 0):
        print(arr[i])
 
 
# Driver code
arr = [1, 12, 4, 6, 7, 10]
n = len(arr)
 
alternateSort(arr, n)
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# program to print an array in alternate
// sorted manner
using System;
 
class AlternativeString {
     
    // Function to print alternate sorted values
    static void alternateSort(int[] arr, int n)
    {
        Array.Sort(arr);
 
        // Printing the last element of array
        // first and then first element and then
        // second last element and then second
        // element and so on.
        int i = 0, j = n - 1;
        while (i < j) {
            Console.Write(arr[j--] + " ");
            Console.Write(arr[i++] + " ");
        }
 
        // If the total element in array is odd
        // then print the last middle element.
        if (n % 2 != 0)
            Console.WriteLine(arr[i]);
    }
 
    /* Driver program to test above functions */
    public static void Main()
    {
        int[] arr = { 1, 12, 4, 6, 7, 10 };
        int n = arr.Length;
        alternateSort(arr, n);
    }
}
 
// This article is contributed by vt_m.

<?php
// PHP program to print an array in
// alternate sorted manner.
 
// Function to print alternate
// sorted values
function alternateSort($arr, $n)
{
    // Sorting the array
    sort($arr);
 
    // Printing the last element
    // of array  first and then
    // first element and then second
    // last element and then second 
    // element and so on.
    $i = 0;
    $j = $n - 1;
    while ($i < $j)
    {
        echo $arr[$j--]." ";
        echo $arr[$i++]." ";
    }
 
    // If the total element in array 
    // is odd then print the last
    // middle element.
    if ($n % 2 != 0)
        echo $arr[$i];
}
 
// Driver code
$arr= array(1, 12, 4, 6, 7, 10);
$n = sizeof($arr) / sizeof($arr[0]);
 
alternateSort($arr, $n);
 
// This code is contributed by Mithun Kumar
?>

<script>
      // JavaScript program to print an array in alternate
      // sorted manner.
 
      // Function to print alternate sorted values
      function alternateSort(arr, n)
      {
       
        // Sorting the array
        console.log(arr);
        arr.sort(function (a, b)
        {
          return a - b;
        });
        console.log(arr);
 
        // Printing the last element of array
        // first and then first element and then
        // second last element and then second
        // element and so on.
        var i = 0,
          j = n - 1;
        while (i < j)
        {
          document.write(arr[j--] + " ");
          document.write(arr[i++] + " ");
        }
 
        // If the total element in array is odd
        // then print the last middle element.
        if (n % 2 != 0) document.write(arr[i]);
      }
 
      // Driver code
      var arr = [1, 12, 4, 6, 7, 10];
      var n = arr.length;
      alternateSort(arr, n);
       
      // This code is contributed by rdtank.
    </script>

12 1 10 4 7 6 

Complejidad temporal: O(n Log n) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Sachin Bisht . 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.