Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array.
Examples:
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
Simple solution is to first convert each array elements into its square and than apply any “O(nlogn)” sorting algorithm to sort the array elements.
Below is the implementation of above idea
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 << "
After 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 ( "
" ) 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. |
Output:
Before sort -6 -3 -1 2 4 5 After Sort 1 4 9 16 25 36
Time complexity: O(n log n)
Efficient solution is based on the fact that given array is already sorted. We do following two steps.
- Divide the array into two part “Negative and positive “.
- Use merge function to merge two sorted arrays into a single sorted array.
Below is the implementation of above idea.
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 dived array into part negative and positive int K = 0; 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 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 << "
After 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 dived array into part negative and positive int 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 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] + " " ); } } |
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 dived array into part negative and positive int 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 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 |
Output
Before sort -6 -3 -1 2 4 5 After Sort 1 4 9 16 25 36
Time complexity: O(n)
space complexity: O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
This article is attributed to GeeksforGeeks.org
0
0
leave a comment
0 Comments