Dada una array de enteros positivos y negativos ‘arr[]’ que se ordenan. La tarea es ordenar el cuadrado de los números del Array.
Ejemplos:
Input : arr[] = {-6, -3, -1, 2, 4, 5}
Output : 1, 4, 9, 16, 25, 36
Input : arr[] = {-5, -4, -2, 0, 1}
Output : 0, 1, 4, 16, 25
La solución simple es primero convertir cada elemento de la array en su cuadrado y luego aplicar cualquier algoritmo de clasificación «O (nlogn)» para ordenar los elementos de la array.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to Sort square of the numbers
// of the array
#include <bits/stdc++.h>
using namespace std;
// Function to sort an square array
void sortSquares(int arr[], int n)
{
// First convert each array elements
// into its square
for (int i = 0; i < n; i++)
arr[i] = arr[i] * arr[i];
// Sort an array using "sort STL function "
sort(arr, arr + n);
}
// Driver program to test above function
int main()
{
int arr[] = { -6, -3, -1, 2, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Before sort " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
sortSquares(arr, n);
cout << "\nAfter Sort " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to Sort square of the numbers
// of the array
import java.util.*;
import java.io.*;
class GFG {
// Function to sort an square array
public static void sortSquares(int arr[])
{
int n = arr.length;
// First convert each array elements
// into its square
for (int i = 0; i < n; i++)
arr[i] = arr[i] * arr[i];
// Sort an array using "inbuild sort function"
// in Arrays class.
Arrays.sort(arr);
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { -6, -3, -1, 2, 4, 5 };
int n = arr.length;
System.out.println("Before sort ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
sortSquares(arr);
System.out.println("");
System.out.println("After Sort ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Python3
# Python program to Sort square
# of the numbers of the array
# Function to sort an square array
def sortSquare(arr, n):
# First convert each array
# elements into its square
for i in range(n):
arr[i]= arr[i] * arr[i]
arr.sort()
# Driver code
arr = [-6, -3, -1, 2, 4, 5]
n = len(arr)
print("Before sort")
for i in range(n):
print(arr[i], end = " ")
print("\n")
sortSquare(arr, n)
print("After sort")
for i in range(n):
print(arr[i], end = " ")
# This code is contributed by
# Shrikant13
C#
// C# program to Sort square
// of the numbers of the array
using System;
class GFG {
// Function to sort
// an square array
public static void sortSquares(int[] arr)
{
int n = arr.Length;
// First convert each array
// elements into its square
for (int i = 0; i < n; i++)
arr[i] = arr[i] * arr[i];
// Sort an array using
// "inbuild sort function"
// in Arrays class.
Array.Sort(arr);
}
// Driver Code
public static void Main()
{
int[] arr = { -6, -3, -1,
2, 4, 5 };
int n = arr.Length;
Console.WriteLine("Before sort ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
sortSquares(arr);
Console.WriteLine("");
Console.WriteLine("After Sort ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by anuj_67.
Javascript
<script>
// JavaScript program for the above approach
// Function to sort an square array
function sortSquares(arr)
{
let n = arr.length;
// First convert each array elements
// into its square
for (let i = 0; i < n; i++)
arr[i] = arr[i] * arr[i];
// Sort an array using "inbuild sort function"
// in Arrays class.
arr.sort();
}
// Driver Code
let arr = [ -6, -3, -1, 2, 4, 5 ];
let n = arr.length;
document.write("Before sort " + "<br/>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
sortSquares(arr);
document.write("" + "<br/>");
document.write("After Sort " + "<br/>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by chinmoy1997pal.
</script>
Producción
Before sort -6 -3 -1 2 4 5 After Sort 1 4 9 16 25 36
Complejidad del tiempo: O(n log n)
La solución eficiente se basa en el hecho de que la array dada ya está ordenada. Realizamos los siguientes dos pasos.
- Divida la array en dos partes «Negativo y positivo».
- Use la función de combinación para combinar dos arrays ordenadas en una sola array ordenada.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to Sort square of the numbers of the array
#include <bits/stdc++.h>
using namespace std;
// function to sort array after doing squares of elements
void sortSquares(int arr[], int n)
{
// first divide array into negative and positive part
int K = 0;
for (K = 0; K < n; K++)
if (arr[K] >= 0)
break;
// Now do the same process that we learnt
// in merge sort to merge two sorted array
// here both two half are sorted and we traverse
// first half in reverse manner because
// first half contains negative elements
int i = K - 1; // Initial index of first half
int j = K; // Initial index of second half
int ind = 0; // Initial index of temp array
// store sorted array
int temp[n];
while (i >= 0 && j < n) {
if (arr[i] * arr[i] < arr[j] * arr[j]) {
temp[ind] = arr[i] * arr[i];
i--;
}
else {
temp[ind] = arr[j] * arr[j];
j++;
}
ind++;
}
/* Copy the remaining elements of first half */
while (i >= 0) {
temp[ind] = arr[i] * arr[i];
i--;
ind++;
}
/* Copy the remaining elements of second half */
while (j < n) {
temp[ind] = arr[j] * arr[j];
j++;
ind++;
}
// copy 'temp' array into original array
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
// Driver program to test above function
int main()
{
int arr[] = { -6, -3, -1, 2, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Before sort " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
sortSquares(arr, n);
cout << "\nAfter Sort " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to Sort square of the numbers
// of the array
import java.util.*;
import java.io.*;
class GFG {
// Function to sort an square array
public static void sortSquares(int arr[])
{
int n = arr.length;
// first divide the array into negative and positive part
int k;
for (k = 0; k < n; k++) {
if (arr[k] >= 0)
break;
}
// Now do the same process that we learnt
// in merge sort to merge two sorted arrays
// here both two halves are sorted and we traverse
// first half in reverse manner because
// first half contains negative elements
int i = k - 1; // Initial index of first half
int j = k; // Initial index of second half
int ind = 0; // Initial index of temp array
int[] temp = new int[n];
while (i >= 0 && j < n) {
if (arr[i] * arr[i] < arr[j] * arr[j]) {
temp[ind] = arr[i] * arr[i];
i--;
}
else {
temp[ind] = arr[j] * arr[j];
j++;
}
ind++;
}
while (i >= 0) {
temp[ind++] = arr[i] * arr[i];
i--;
}
while (j < n) {
temp[ind++] = arr[j] * arr[j];
j++;
}
// copy 'temp' array into original array
for (int x = 0; x < n; x++)
arr[x] = temp[x];
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { -6, -3, -1, 2, 4, 5 };
int n = arr.length;
System.out.println("Before sort ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
sortSquares(arr);
System.out.println("");
System.out.println("After Sort ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Python3
# Python3 program to Sort square of the numbers of the array
# function to sort array after doing squares of elements
def sortSquares(arr, n):
# first divide array into negative and positive part
K = 0
for K in range(n):
if (arr[K] >= 0 ):
break
# Now do the same process that we learnt
# in merge sort to merge to two sorted array
# here both two halves are sorted and we traverse
# first half in reverse manner because
# first half contains negative elements
i = K - 1 # Initial index of first half
j = K # Initial index of second half
ind = 0 # Initial index of temp array
# store sorted array
temp = [0]*n
while (i >= 0 and j < n):
if (arr[i] * arr[i] < arr[j] * arr[j]):
temp[ind] = arr[i] * arr[i]
i -= 1
else:
temp[ind] = arr[j] * arr[j]
j += 1
ind += 1
''' Copy the remaining elements of first half '''
while (i >= 0):
temp[ind] = arr[i] * arr[i]
i -= 1
ind += 1
''' Copy the remaining elements of second half '''
while (j < n):
temp[ind] = arr[j] * arr[j]
j += 1
ind += 1
# copy 'temp' array into original array
for i in range(n):
arr[i] = temp[i]
# Driver code
arr = [-6, -3, -1, 2, 4, 5 ]
n = len(arr)
print("Before sort ")
for i in range(n):
print(arr[i], end =" " )
sortSquares(arr, n)
print("\nAfter Sort ")
for i in range(n):
print(arr[i], end =" " )
# This code is contributed by shubhamsingh10
C#
// C# program to Sort square of the numbers
// of the array
using System;
class GFG {
// Function to sort an square array
public static void sortSquares(int[] arr)
{
int n = arr.Length;
// first divide array into negative and positive part
int k;
for (k = 0; k < n; k++) {
if (arr[k] >= 0)
break;
}
// Now do the same process that we learnt
// in merge sort to merge to two sorted array
// here both two halves are sorted and we traverse
// first half in reverse manner because
// first half contains negative elements
int i = k - 1; // Initial index of first half
int j = k; // Initial index of second half
int ind = 0; // Initial index of temp array
int[] temp = new int[n];
while (i >= 0 && j < n) {
if (arr[i] * arr[i] < arr[j] * arr[j]) {
temp[ind] = arr[i] * arr[i];
i--;
}
else {
temp[ind] = arr[j] * arr[j];
j++;
}
ind++;
}
while (i >= 0) {
temp[ind++] = arr[i] * arr[i];
i--;
}
while (j < n) {
temp[ind++] = arr[j] * arr[j];
j++;
}
// copy 'temp' array into original array
for (int x = 0; x < n; x++)
arr[x] = temp[x];
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { -6, -3, -1, 2, 4, 5 };
int n = arr.Length;
Console.WriteLine("Before sort ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
sortSquares(arr);
Console.WriteLine("");
Console.WriteLine("After Sort ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to Sort
// square of the numbers
// of the array
// Function to sort an square array
function sortSquares(arr)
{
let n = arr.length;
// first dived array into part
// negative and positive
let k;
for (k = 0; k < n; k++) {
if (arr[k] >= 0)
break;
}
// Now do the same process that we learn
// in merge sort to merge to two sorted array
// here both two half are sorted and we traverse
// first half in reverse meaner because
// first half contain negative element
let i = k - 1; // Initial index of first half
let j = k; // Initial index of second half
let ind = 0; // Initial index of temp array
let temp = new Array(n);
while (i >= 0 && j < n) {
if (arr[i] * arr[i] < arr[j] * arr[j]) {
temp[ind] = arr[i] * arr[i];
i--;
}
else {
temp[ind] = arr[j] * arr[j];
j++;
}
ind++;
}
while (i >= 0) {
temp[ind++] = arr[i] * arr[i];
i--;
}
while (j < n) {
temp[ind++] = arr[j] * arr[j];
j++;
}
// copy 'temp' array into original array
for (let x = 0; x < n; x++)
arr[x] = temp[x];
}
// Driver program to test above function
let arr=[ -6, -3, -1, 2, 4, 5 ];
let n = arr.length;
document.write("Before sort <br>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
sortSquares(arr);
document.write("<br>");
document.write("After Sort <br>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by rag2127
</script>
Producción
Before sort -6 -3 -1 2 4 5 After Sort 1 4 9 16 25 36
Complejidad temporal: O(n)
Complejidad espacial: O(n)
Método 3:
otra solución eficiente se basa en el método de dos punteros, ya que la array ya está ordenada, podemos comparar el primer y el último elemento para verificar cuál es más grande y continuar con el resultado.
Algoritmo:
- Inicializar izquierda = 0 y derecha = n-1
- si abs(izquierda) >= abs(derecha) entonces almacene el cuadrado(arr[izquierda])
al final de la array de resultados e incremente el puntero izquierdo - de lo contrario, almacene el cuadrado (arr [derecha]) en la array de resultados y disminuya el puntero derecho
- índice de disminución de la array de resultados
Implementación:
C++
// CPP code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to sort an square array
void sortSquares(vector<int>& arr, int n)
{
int left = 0, right = n - 1;
int result[n];
// Iterate from n - 1 to 0
for (int index = n - 1; index >= 0; index--) {
// Check if abs(arr[left]) is greater
// than arr[right]
if (abs(arr[left]) > arr[right]) {
result[index] = arr[left] * arr[left];
left++;
}
else {
result[index] = arr[right] * arr[right];
right--;
}
}
for (int i = 0; i < n; i++)
arr[i] = result[i];
}
// Driver Code
int main()
{
vector<int> arr;
arr.push_back(-6);
arr.push_back(-3);
arr.push_back(-1);
arr.push_back(2);
arr.push_back(4);
arr.push_back(5);
int n = 6;
cout << "Before sort " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
sortSquares(arr, n);
cout << endl;
cout << "After Sort " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
// this code is contributed by Manu Pathria
Java
// Java program to Sort square of
// the numbers of the array
import java.util.*;
import java.io.*;
class GFG{
// Function to sort an square array
public static void sortSquares(int arr[])
{
int n = arr.length, left = 0,
right = n - 1;
int result[] = new int[n];
for(int index = n - 1; index >= 0; index--)
{
if (Math.abs(arr[left]) > arr[right])
{
result[index] = arr[left] * arr[left];
left++;
}
else
{
result[index] = arr[right] * arr[right];
right--;
}
}
for(int i = 0; i < n; i++)
arr[i] = result[i];
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -6, -3, -1, 2, 4, 5 };
int n = arr.length;
System.out.println("Before sort ");
for(int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
sortSquares(arr);
System.out.println("");
System.out.println("After Sort ");
for(int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by jinalparmar2382
Python3
# Python3 program to Sort square of the numbers of the array
# function to sort array after doing squares of elements
def sortSquares(arr, n):
left, right = 0, n - 1
index = n - 1
result = [0 for x in arr]
while index >= 0:
if abs(arr[left]) >= abs(arr[right]):
result[index] = arr[left] * arr[left]
left += 1
else:
result[index] = arr[right] * arr[right]
right -= 1
index -= 1
for i in range(n):
arr[i] = result[i]
# Driver code
arr = [-6, -3, -1, 2, 4, 5 ]
n = len(arr)
print("Before sort ")
for i in range(n):
print(arr[i], end =" " )
sortSquares(arr, n)
print("\nAfter Sort ")
for i in range(n):
print(arr[i], end =" " )
C#
// C# program to Sort square of
// the numbers of the array
using System;
class GFG{
// Function to sort an square array
public static void sortSquares(int [] arr)
{
int n = arr.Length, left = 0,
right = n - 1;
int []result = new int[n];
for(int index = n - 1;
index >= 0; index--)
{
if (Math.Abs(arr[left]) >
arr[right])
{
result[index] = arr[left] *
arr[left];
left++;
}
else
{
result[index] = arr[right] *
arr[right];
right--;
}
}
for(int i = 0; i < n; i++)
arr[i] = result[i];
}
// Driver code
public static void Main(string[] args)
{
int []arr = {-6, -3, -1, 2, 4, 5};
int n = arr.Length;
Console.WriteLine("Before sort ");
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
sortSquares(arr);
Console.WriteLine("");
Console.WriteLine("After Sort ");
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// This function squares each value in an array
// and arranges the result in ascending order, using two pointers.
// The first pointer points to the first element of the array, and the second
// points to the last. On each iteration, each pointer is compared to the other
// and the pointer which has the lowest value is shifted closer to the other.
function sortSquares(arr) {
let
n = nums.length,
left = 0,
right = n -1,
result = new Array(n)
;
for (let i = n - 1; i >= 0; i--) {
// Here, Math.abs() is used to convert any negative numbers to their
// integer equivalent... i.e. -4 becomes 4.
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result[i] = nums[left] ** 2;
left++;
} else {
result[i] = nums[right] **2;
right--;
}
}
return result;
}
let arr = [-6, -3, -1, 2, 4, 5];
let n = arr.length;
document.write("Before sort " + "</br>");
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
sortSquares(arr);
document.write("</br>");
document.write("After Sort " + "</br>");
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code was contributed by rameshtravel07, then was edited by: Lewis Farnworth
</script>
Producción
Before sort -6 -3 -1 2 4 5 After Sort 1 4 9 16 25 36
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Nishant Singh . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA