Given an array arr[] that contains N real numbers. The task is to sort the array in decreasing order of the Fractional Values
Note: If the values of the fractional part are same then sort those elements in Decreasing order of their Integer Values.
Examples:
Input: arr[] = { 8.33, -3.85, 1.999, 6.33, 5}
Output: { 1.999, 8.33, 6.33, -3.85 , 5}
Explanation:
Element Integer Value Fraction Value 8.33
8
0.33
-3.85
-4
0.15
1.999
1
0.999
6.33
6
0.33
5
5
0.0
1.999 has the biggest fractional value so it will be at index 0 while 5 has the lowest fractional value so it will be at the last index.
6.33 and 8.33 have the same fractional values but the Integer part of 8.33 is greater than 6.33 so we place 8.33 before 6.33 as the given condition in the problem statement.Fractional value = Given number – Integer Value.
Fractional Value of positive value e.g. (8.33) = 8.33 – Integer Value of ( 8.33)= 8.33 – 8= 0.33
Fractional Value of (-3.85) = -3.85- Integer Value of (-3.85)= -3.85 – ( -4 ) = -3.85 + 4 = 0.15Hence, the order for the above example will be: {1.999, 8.33, 6.33, -3.85, 5}
Input: arr[] = { 1.1, 1.11, 1.111, 2.1, 2.11, 2.111}
Output: { 2.111, 1.111, 2.11, 1.11, 2.1, 1.1 }
Explanation: Here the biggest fractional value is 0.111 which is present in both 2.111 and 1.111. But the integer value of 2.111 is greater than 1.111. so, 2.111 will come before 1.111. The same applies to other elements.
Naive Approach: The basic idea to solve the problem is to store the pair of {Fractional value, Integer value} in a vector and then sort the vector in descending order of fractional part. Lastly reverse the vector for the final answer as the desired answer should be in descending order.
Below is the implementation of the above approach:
C++
// C++ program to sort Array// in descending order of fractional value#include <bits/stdc++.h>using namespace std;// Function to sort the fractional partvoid SortFraction(long double arr[], int n){ // To store fraction and it's // corresponding integer and the // original element vector<pair<pair<long double, int>, long double> > v; for (int i = 0; i < n; i++) { // Calculate fractional value long double fraction = arr[i] - floorl(arr[i]); // Calculate integer value int integer = floorl(arr[i]); v.push_back({ make_pair(fraction, integer), arr[i] }); } // Sort the vector sort(v.begin(), v.end()); // To get final answer, // reverse the vector reverse(v.begin(), v.end()); // To print output for (int i = 0; i < n; i++) cout << v[i].second << " ";}// Driver Codeint main(){ long double arr[] = { 8.33, -3.85, 1.999, 6.33, 5 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Sort in descending order // of fractional value SortFraction(arr, N); return 0;} |
Java
import java.util.*;import java.io.*;class GFG{ // Function to sort the fractional part public static void SortFraction(double arr[], int n){ // To store fraction and it's // corresponding integer and the // original element ArrayList<ArrayList<Double>> v = new ArrayList<ArrayList<Double>>(); for(int i=0 ; i<n ; i++){ // Calculate fractional value double fraction = arr[i]-Math.floor((double)arr[i]); // Calculate integer value double integer = Math.floor((double)arr[i]); ArrayList<Double> temp = new ArrayList<Double>(); temp.add(fraction); temp.add(integer); temp.add(arr[i]); v.add(temp); } // Sort the vector Collections.sort(v,new Comp()); // To get final answer, // reverse the vector Collections.reverse(v); // To print output for(int i=0 ; i<n ; i++){ System.out.print(v.get(i).get(2) + " "); } } // Driver code public static void main(String args[]) { // Size of array int N = 5; double arr[] = {8.33, -3.85, 1.999, 6.33, 5}; // Sort in descending order // of fractional value SortFraction(arr, N); }}class Comp implements Comparator<ArrayList<Double>>{ public int compare(ArrayList<Double> a, ArrayList<Double> b){ for(int i=0 ; i<2 ; i++){ if(a.get(i).equals(b.get(i))){ continue; } return a.get(i).compareTo(b.get(i)); } return a.get(2).compareTo(b.get(2)); }};// This code is contributed by subhamgoyal2014. |
Python3
# Python program to sort Array# in descending order of fractional valueimport math# Function to sort the fractional partdef SortFraction (arr, n) : # To store fraction and it's # corresponding integer and the # original element v = [] for i in range(n) : # Calculate fractional value fraction = arr[i] - math.floor(arr[i]) # Calculate integer value integer = math.floor(arr[i]) v.append([[fraction, integer], arr[i]]) # Sort the vector v.sort() # To get final answer, # reverse the vector v.reverse() # To print output for i in range(n) : print(v[i][1],end=' ') # Driver Codeif __name__ == "__main__": arr = [8.33, -3.85, 1.999, 6.33, 5] # Size of array N = len(arr) # Sort in descending order # of fractional value SortFraction(arr, N) # This code is contributed by jana_sayantan. |
C#
// C# codeusing System;using System.Collections.Generic;class Program { // Function to sort the fractional part public static void SortFraction(double[] arr, int n){ // To store fraction and it's // corresponding integer and the // original element List<List<double>> v = new List<List<double>>(); for(int i=0 ; i<n ; i++){ // Calculate fractional value double fraction = arr[i]-Math.Floor((double)arr[i]); // Calculate integer value double integer = Math.Floor((double)arr[i]); List<double> temp = new List<double>(); temp.Add(fraction); temp.Add(integer); temp.Add(arr[i]); v.Add(temp); } // Sort the list v.Sort(new Comp()); // To get final answer, // reverse the list v.Reverse(); // To print output foreach(var item in v){ Console.Write(item[2]+ " "); } } // Driver code public static void Main(string[] args){ // Size of array int N = 5; double[] arr = {8.33, -3.85, 1.999, 6.33, 5}; // Sort in descending order // of fractional value SortFraction(arr, N); }}class Comp : IComparer<List<double>>{ public int Compare(List<double> a, List<double> b){ for(int i=0 ; i<2 ; i++){ if(a[i].Equals(b[i])){ continue; } return a[i].CompareTo(b[i]); } return a[2].CompareTo(b[2]); }};// This code is contributed by Utkarsh |
Javascript
<script> // JavaScript program to sort Array // in descending order of fractional value // Function to sort the fractional part const SortFraction = (arr, n) => { // To store fraction and it's // corresponding integer and the // original element let v = []; for (let i = 0; i < n; i++) { // Calculate fractional value let fraction = arr[i] - Math.floor(arr[i]); // Calculate integer value let integer = Math.floor(arr[i]); v.push([[fraction, integer], arr[i]]); } // Sort the vector v.sort(); // To get final answer, // reverse the vector v.reverse(); // To print output for (let i = 0; i < n; i++) document.write(`${v[i][1]} `); } // Driver Code let arr = [8.33, -3.85, 1.999, 6.33, 5]; // Size of array let N = arr.length; // Sort in descending order // of fractional value SortFraction(arr, N);// This code is contributed by rakeshsahni</script> |
Output
1.999 8.33 6.33 -3.85 5
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Efficient Approach: The idea to solve the problem in optimized way is by using Comparator, to sort the vector.
Follow the steps to solve the problem:
- Firstly, make a comparator function to sort the array according to the requirements given in the problem.
- Return true if fraction of a > fraction of b, to sort the elements in decreasing order of the fractional Values.
- If fraction of a = fraction of b then return true if integer of a > integer of b
- Return False in every other case.
- The final array is the required sorted array.
Below is the implementation of the above approach:
C++
// C++ program to sort Array// in descending order of fractional value#include <bits/stdc++.h>using namespace std;// Comparator to sort array// according to questionbool comp(long double a, long double b){ int int_a = floorl(a); int int_b = floorl(b); long double fraction_a = a - int_a; long double fraction_b = b - int_b; if (fraction_a > fraction_b) return true; if (fraction_a == fraction_b) { if (int_a > int_b) return true; else return false; } return false;}// Function to print answervoid print(long double arr[], int n){ // Sort in descending order of // fractional value pass comp to sort sort(arr, arr + n, comp); for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Driver Codeint main(){ long double arr[] = { 8.33, -3.85, 1.999, 6.33, 5 }; // Size of arr int N = sizeof(arr) / sizeof(arr[0]); print(arr, N); return 0;} |
Java
// Java program to sort Array// in descending order of fractional valueimport java.util.Arrays;import java.util.Comparator;public class Main { // Comparator to sort array // according to question static class FractionalComparator implements Comparator<Double> { @Override public int compare(Double a, Double b) { int int_a = (int) Math.floor(a); int int_b = (int) Math.floor(b); double fraction_a = a - int_a; double fraction_b = b - int_b; if (fraction_a > fraction_b) { return -1; } if (fraction_a == fraction_b) { if (int_a > int_b) { return -1; } else { return 1; } } return 1; } } // Driver Code public static void main(String[] args) { Double[] arr = { 8.33, -3.85, 1.999, 6.33, 5.0 }; // Sort in descending order of // fractional value pass comp to sort Arrays.sort(arr, new FractionalComparator()); // Function to print answer for (Double number : arr) { System.out.print(number + " "); } }}// This code is contributed by ratiagrawal. |
Python3
# Python program to sort Array# in descending order of fractional valueimport mathfrom functools import cmp_to_key# Comparator to sort array# according to questionfrom functools import cmp_to_keydef comp(a, b): int_a = math.floor(a) int_b = math.floor(b) fraction_a = a - int_a fraction_b = b - int_b if (fraction_a > fraction_b): return 1 if (fraction_a == fraction_b): if (int_a > int_b): return 1 else: return -1 return -1# Function to print answerdef Print(arr,n): # Sort in descending order of # fractional value pass comp to sort b=sorted(arr,key=cmp_to_key(comp),reverse=True) for i in range(n): print(b[i],end=' ')# Driver Codeif __name__ == "__main__": arr = [8.33, -3.85, 1.999, 6.33, 5] # Size of array N = len(arr) Print(arr,N) # This code is contributed by Pushpesh Raj. |
C#
using System;using System.Collections.Generic;public class Program{ // Comparator to sort array // according to question class FractionalComparator : IComparer<double> { public int Compare(double a, double b) { int int_a = (int)Math.Floor(a); int int_b = (int)Math.Floor(b); double fraction_a = a - int_a; double fraction_b = b - int_b; if (fraction_a > fraction_b) { return -1; } if (fraction_a == fraction_b) { if (int_a > int_b) { return -1; } else { return 1; } } return 1; } } // Main method static void Main(string[] args) { Double[] arr = { 8.33, -3.85, 1.999, 6.33, 5.0 }; // Sort in descending order of // fractional value pass comp to sort Array.Sort(arr, new FractionalComparator()); // Function to print answer for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } }}// This code is contributed by lokeshpotta20. |
Javascript
function comp(a, b) { const int_a = Math.floor(a); const int_b = Math.floor(b); const fraction_a = a - int_a; const fraction_b = b - int_b; if (fraction_a > fraction_b) { return 1; } if (fraction_a === fraction_b) { if (int_a > int_b) { return 1; } else { return -1; } } return -1;}function Print(arr, n) { // Sort in descending order of fractional value // pass comp to sort const b = arr.sort(comp).reverse(); for (let i = 0; i < n; i++) { console.log(b[i] + " "); }}const arr = [8.33, -3.85, 1.999, 6.33, 5];// Size of arrayconst N = arr.length;Print(arr, N); |
Output
1.999 8.33 6.33 -3.85 5
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
