Ordena los números según su suma de dígitos

Dada una array arr[] de N enteros no negativos, la tarea es ordenar estos enteros según la suma de sus dígitos.
Ejemplos: 
 

Entrada: arr[] = {12, 10, 102, 31, 15} 
Salida: 10 12 102 31 15 
10 => 1 + 0 = 1 
12 => 1 + 2 = 3 
102 => 1 + 0 + 2 = 3 
31 => 3 + 1= 4 
15 => 1 + 5 = 6
Entrada: arr[] = {14, 1101, 10, 35, 0} 
Salida: 0 10 1101 14 35 
 

Primer enfoque: la idea es almacenar cada elemento con su suma de dígitos en un par de vectores y luego ordenar todos los elementos del vector de acuerdo con las sumas de dígitos almacenadas. Finalmente, imprima los elementos en orden.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the sum
// of the digits of n
int sumOfDigit(int n)
{
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n = n / 10;
    }
    return sum;
}
 
// Function to sort the array according to
// the sum of the digits of elements
void sortArr(int arr[], int n)
{
    // Vector to store digit sum with respective element
    vector<pair<int, int> > vp;
 
    // Inserting digit sum with element in the vector pair
    for (int i = 0; i < n; i++) {
        vp.push_back(make_pair(sumOfDigit(arr[i]), arr[i]));
    }
 
    // Quick sort the vector, this will sort the pair
    // according to sum of the digits of elements
    sort(vp.begin(), vp.end());
 
    // Print the sorted vector content
    for (int i = 0; i < vp.size(); i++)
        cout << vp[i].second << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 14, 1101, 10, 35, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sortArr(arr, n);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
class GFG
{
 
  // Function to return the sum
  // of the digits of n
  static int sumOfDigit(int n)
  {
    int sum = 0;
    while (n > 0) {
      sum += n % 10;
      n = Math.floorDiv(n , 10);
    }
    return sum;
  }
 
  // Function to sort the array according to
  // the sum of the digits of elements
  static void sortArr(int[] arr,int n)
  {
 
    // Vector to store digit sum with respective element
    ArrayList<ArrayList<Integer>> vp = new ArrayList<ArrayList<Integer>>();
 
    // Inserting digit sum with element in the vector pair
    for (int i = 0; i < n; i++) {
      ArrayList<Integer>temp = new ArrayList<Integer>();
      temp.add(sumOfDigit(arr[i]));
      temp.add(arr[i]);
      vp.add(temp);
    }
 
    // Quick sort the vector, this will sort the pair
    // according to sum of the digits of elements
    Collections.sort(vp,new Comparator<ArrayList<Integer>>(){
      @Override
      public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
        return o1.get(0) - o2.get(0);
      }  
    });
 
    // Print the sorted vector content
    for (int i = 0; i < vp.size(); i++){
      System.out.printf("%d ",vp.get(i).get(1));
    }
  }
 
  // Driver code
  public static void main(String args[])
  {
    int[] arr = { 14, 1101, 10, 35, 0 };
    int n = arr.length;
    sortArr(arr, n);
  }
}
 
// This code is contributed by shinjanpatra

# Python3 implementation of the approach
 
# Function to return the sum
# of the digits of n
def sumOfDigit(n) :
     
    sum = 0;
    while (n > 0) :
         
        sum += n % 10;
        n = n // 10;
         
    return sum;
 
# Function to sort the array according to
# the sum of the digits of elements
def sortArr(arr, n) :
     
    # Vector to store digit sum with
    # respective element
    vp = [];
 
    # Inserting digit sum with element
    # in the vector pair
    for i in range(n) :
        vp.append([sumOfDigit(arr[i]), arr[i]]);
 
    # Quick sort the vector, this will
    # sort the pair according to sum
    # of the digits of elements
    vp.sort()
 
    # Print the sorted vector content
    for i in range(len(vp)) :
        print(vp[i][1], end = " ");
 
# Driver code
if __name__ == "__main__" :
 
    arr = [14, 1101, 10, 35, 0];
    n = len(arr);
    sortArr(arr, n);
 
# This code is contributed by Ryuga

<script>
 
// JavaScript implementation of the approach
 
// Function to return the sum
// of the digits of n
function sumOfDigit(n)
{
    let sum = 0;
    while (n > 0) {
        sum += n % 10;
        n = Math.floor(n / 10);
    }
    return sum;
}
 
// Function to sort the array according to
// the sum of the digits of elements
function sortArr(arr, n)
{
 
    // Vector to store digit sum with respective element
    let vp = [];
 
    // Inserting digit sum with element in the vector pair
    for (let i = 0; i < n; i++) {
        vp.push([sumOfDigit(arr[i]), arr[i]]);
    }
 
    // Quick sort the vector, this will sort the pair
    // according to sum of the digits of elements
    vp.sort();
 
    // Print the sorted vector content
    for (let i = 0; i < vp.length; i++)
        document.write(vp[i][1]," ");
}
 
// Driver code
let arr = [ 14, 1101, 10, 35, 0 ];
let n = arr.length;
sortArr(arr, n);
 
// This code is contributed by shinjanpatra
 
</script>

0 10 1101 14 35 

Complejidad de tiempo: O (n log n) para ordenar por combinación y ordenar por montón, pero O (n^2) para ordenar rápidamente

Espacio Auxiliar: O(n)

Segundo enfoque: la idea es utilizar una función de ordenación integrada con una función de comparación que calcule la suma de cada par de enteros que se comparan.

1. Pase la array arr a la función de clasificación con la función de comparación Sum_Compare .

2. Dentro de la función Sum_Compare , calcule la suma de los dígitos de ambos números x e y como sumx y sumy tomando el módulo por 10 y luego dividiéndolo por 10 .

3. devuelve si sumx es menor que sumy .

#include <bits/stdc++.h>
 
using namespace std;
 
bool Sum_Compare(int x,int y)
{
    int tempx=x,tempy=y;
    int sumx=0,sumy=0;
     
    while(tempx)
    {
        sumx+=tempx%10;
        tempx/=10;
    }
     
    while(tempy)
    {
        sumy+=tempy%10;
        tempy/=10;
    }
     
    return sumx<sumy;
}
 
int main()
{
    int arr[]={12, 10, 102, 31, 15};
    int n=sizeof(arr)/sizeof(arr[0]);
     
    sort(arr,arr+n,Sum_Compare);
     
    for(auto& x:arr)
    cout<<x<<" ";
 
    return 0;
}

# Python3 code for the approach
 
from functools import cmp_to_key
 
 
def Sum_Compare(x, y):
 
    tempx,tempy = x,y
    sumx,sumy = 0,0
     
    while(tempx > 0):
 
        sumx += tempx % 10
        tempx = tempx // 10
     
    while(tempy > 0):
        sumy += tempy % 10
        tempy = tempy // 10
     
    return sumx - sumy
 
 
arr = [12, 10, 102, 31, 15]
n = len(arr)
     
arr.sort(key = cmp_to_key(Sum_Compare))
 
for x in arr:
    print(x,end = " ")
     
# This code is contributed by shinjanpatra

<script>
 
// JavaScript code for the approach
 
function Sum_Compare(x, y)
{
    let tempx = x,tempy = y;
    let sumx = 0,sumy = 0;
     
    while(tempx)
    {
        sumx += tempx % 10;
        tempx /= 10;
    }
     
    while(tempy)
    {
        sumy += tempy % 10;
        tempy /= 10;
    }
     
    return sumx<sumy;
}
 
let arr = [12, 10, 102, 31, 15];
let n = arr.length;
     
arr.sort(Sum_Compare);
 
for(let x of arr)
    document.writea(x," ");
     
// This code is contributed by shinjanpatra
 
</script>

10 12 102 31 15 

Complejidad de tiempo: O (n (log n) ^ 2) para clasificación de combinación y clasificación de montón pero O (n ^ 2 log n) para clasificación rápida.

Espacio auxiliar: O(1) para clasificación rápida y clasificación en montón, pero O(n) para clasificación combinada.