Ordenar array dada que ya está ordenada según los valores absolutos de los elementos

Dada una array arr[] de tamaño N , ordenada según el valor absoluto de sus elementos. La tarea es ordenar esta array en función de los valores reales de los elementos.

Ejemplos: 

Entrada:  arr[] = {5, -7, 10, -11, 18}
Salida: -11, -7, 5, 10, 18
Explicación: cuando se ordena la array, los valores negativos aparecerán al principio de la array .

Entrada:   arr[] = {1, -2, -3, 4, -5}
Salida: -5, -3, -2, 1, 4

Enfoque: este problema se puede resolver utilizando una cola de dos extremos . La idea es atravesar la array de izquierda a derecha e insertar los elementos negativos en el frente y los elementos positivos en la parte posterior del deque. Ahora saque los elementos del frente del deque para llenar la array y obtener la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <deque>
#include <iostream>
using namespace std;
 
// Function to sort
void SortWithoutSorting(int arr[], int N)
{
    deque<int> dq;
    for (int i = 0; i < N; i++) {
 
        // Pushing negative elements in
        // the front of the deque
        if (arr[i] < 0) {
            dq.push_front(arr[i]);
        }
 
        // Pushing positive elements in
        // the back of the deque
        else {
            dq.push_back(arr[i]);
        }
    }
 
    // Preparing the output array
    int i = 0;
    for (auto it = dq.begin(); it !=
         dq.end(); it++)
        arr[i++] = *it;
}
 
// Function to print the array.
void showArray(int arr[], int N)
{
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, -2, 3, -4, -5, 6 };
    int N = sizeof(arr) / sizeof(int);
 
    SortWithoutSorting(arr, N);
    showArray(arr, N);
    return 0;
}

// Java Program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to sort
    public static void SortWithoutSorting(int arr[], int N)
    {
        Deque<Integer> dq = new ArrayDeque<Integer>();
        for (int i = 0; i < N; i++) {
     
            // Pushing negative elements in
            // the front of the deque
            if (arr[i] < 0) {
                dq.addFirst(arr[i]);
            }
     
            // Pushing positive elements in
            // the back of the deque
            else {
                dq.addLast(arr[i]);
            }
        }
     
        // Preparing the output array
        int i = 0;
        for (Iterator it = dq.iterator();
             it.hasNext();) {
            arr[i++] = (int)it.next();
        }
         
    }
     
    // Function to print the array.
    public static void showArray(int arr[], int N)
    {
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { 1, -2, 3, -4, -5, 6 };
        int N = arr.length;
     
        SortWithoutSorting(arr, N);
        showArray(arr, N);
    }
}
 
// This code is contributed by Shubham Singh

# Python code for the above approach
 
# Function to sort
def SortWithoutSorting(arr, N):
     
    dq = []
    for i in range(N):
        # Pushing negative elements in
        # the front of the deque
        if (arr[i] < 0):
            dq.insert(0,arr[i])
             
        # Pushing positive elements in
        # the back of the deque
        else:
            dq.append(arr[i])
             
    # Preparing the output array
    i = 0
    for it in dq:
        arr[i] = it
        i += 1
         
    return arr
 
# Function to print the array.
def showArray(arr, N):
    for i in range(N):
        print(arr[i], end= " ")
     
# Driver Code
arr = [1, -2, 3, -4, -5, 6]
N = len(arr)
 
arr = SortWithoutSorting(arr, N)
showArray(arr, N)
 
# This code is contributed by Shubham Singh

// C# Program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to sort
  public static void SortWithoutSorting(int[] arr, int N)
  {
 
    List<int> dq = new List<int>();
    int i;
    for (i = 0; i < N; i++) {
 
      // Pushing negative elements in
      // the front of the deque
      if (arr[i] < 0) {
        dq.Insert(0,arr[i]);
      }
 
      // Pushing positive elements in
      // the back of the deque
      else {
        dq.Add(arr[i]);
      }
    }
 
    // Preparing the output array
    i = 0;
    foreach(int it in dq) {
      arr[i++] = it;
    }
 
  }
 
  // Function to print the array.
  public static void showArray(int[] arr, int N)
  {
    for (int i = 0; i < N; i++) {
      Console.Write(arr[i] + " ");
    }
  }
 
  // Driver Code
  public static void Main ()
  {
    int[] arr = { 1, -2, 3, -4, -5, 6 };
    int N = arr.Length;
 
    SortWithoutSorting(arr, N);
    showArray(arr, N);
  }
}
 
// This code is contributed by Shubham Singh

<script>
      // JavaScript code for the above approach
 
      // Function to sort
      function SortWithoutSorting(arr, N)
      {
          let dq = [];
          for (let i = 0; i < N; i++) {
 
              // Pushing negative elements in
              // the front of the deque
              if (arr[i] < 0) {
                  dq.unshift(arr[i]);
              }
 
              // Pushing positive elements in
              // the back of the deque
              else {
                  dq.push(arr[i]);
              }
          }
 
          // Preparing the output array
          let i = 0;
          for (let it of dq)
              arr[i++] = it;
      }
 
      // Function to print the array.
      function showArray(arr, N) {
          for (let i = 0; i < N; i++) {
              document.write(arr[i] + " ")
          }
      }
 
      // Driver Code
      let arr = [1, -2, 3, -4, -5, 6];
      let N = arr.length;
 
      SortWithoutSorting(arr, N);
      showArray(arr, N);
 
// This code is contributed by Potta Lokesh
  </script>

-5 -4 -2 1 3 6 

Complejidad temporal: O(N)
Espacio auxiliar : O(N)