Ordenar según el número de factores usando STL

Dada una array de enteros positivos. Ordene la array dada en orden decreciente del número de factores de cada elemento, es decir, el elemento que tiene el mayor número de factores debe ser el primero en mostrarse y el número que tiene el menor número de factores debe ser el último. Dos elementos con el mismo número de factores deben estar en el mismo orden que en la array original. Ejemplos:

Input : {5, 11, 10, 20, 9, 16, 23}
Output : 20 16 10 9 5 11 23
Number of distinct factors:
For 20 = 6, 16 = 5, 10 = 4, 9 = 3
and for 5, 11, 23 = 2 (same number of factors
therefore sorted in increasing order of index)

Input : {104, 210, 315, 166, 441, 180}
Output : 180 210 315 441 104 166

Ya hemos discutido una solución basada en la estructura para ordenar según el número de factores . Los siguientes pasos ordenan los números en orden decreciente de conteo de factores.

1. Cuente un número distinto de factores de cada elemento. Consulte esto .
2. Cree un vector de pares que almacene elementos y sus recuentos de factores.
3. Ordene esta array sobre la base de la declaración del problema utilizando cualquier algoritmo de clasificación.

// Sort an array of numbers according
// to number of factors.
#include <bits/stdc++.h>
using namespace std;
 
// Function that helps to sort elements
// in descending order
bool compare(const pair<int, int> &a,
             const pair<int, int> &b) {
  return (a.first > b.first);
}
 
// Prints array elements sorted in descending
// order of number of factors.
void printSorted(int arr[], int n) {
 
  vector<pair<int, int>> v;
 
  for (int i = 0; i < n; i++) {
 
    // Count factors of arr[i].
    int count = 0;
    for (int j = 1; j * j <= arr[i]; j++) {
 
      // To check Given Number is Exactly
      // divisible
      if (arr[i] % j == 0) {
        count++;
 
        // To check Given number is perfect
        // square
        if (arr[i] / j != j)
          count++;
      }
    }
 
    // Insert factor count and array element
    v.push_back(make_pair(count, arr[i]));
  }
 
  // Sort the vector
  sort(v.begin(), v.end(), compare);
 
  // Print the vector
  for (int i = 0; i < v.size(); i++)
    cout << v[i].second << " ";
}
 
// Driver's Function
int main() {
  int arr[] = {5, 11, 10, 20, 9, 16, 23};
  int n = sizeof(arr) / sizeof(arr[0]);
 
  printSorted(arr, n);
 
  return 0;
}

// java program to Sort on the basis of
// number of factors using STL
  
import java.io.*;
import java.util.*; 
 
class Pair
{
    int a;
    int b;
    Pair(int a, int b)
    {
        this.a=a;
        this.b=b;
         
    }
     
}
 
// creates the comparator for comparing first element
class SComparator implements Comparator<Pair> {
    // override the compare() method
    public int compare(Pair o1, Pair o2)
    {
        if (o1.a == o2.a) {
            return 0;
        }
        else if (o1.a < o2.a) {
            return 1;
        }
        else {
            return -1;
        }
    }
}
 
class GFG {
    // Function to find maximum partitions.
    static void printSorted(int arr[], int n)
    {
        ArrayList<Pair> v = new ArrayList<Pair>();
         for (int i = 0; i < n; i++) {
   
        // Count factors of arr[i].
        int count = 0;
        for (int j = 1; j * j <= arr[i]; j++) {
       
          // To check Given Number is Exactly
          // divisible
          if (arr[i] % j == 0) {
            count++;
       
            // To check Given number is perfect
            // square
            if (arr[i] / j != j)
              count++;
          }
    }
   
    // Insert factor count and array element
    v.add(new Pair (count, arr[i]));
  }
   
  // Sort the vector
  // Sorting the arraylist elements in descending order
    Collections.sort(v, new SComparator());
   
  // Print the vector
  for (Pair i : v)
    System.out.print(i.b+" ");
}
  
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 5, 11, 10, 20, 9, 16, 23 };
        int n = arr.length;
        printSorted(arr, n);
    }
}
  
// This code is contributed by Aarti_Rathi

# python program to Sort on the basis of
# number of factors using STL
from functools import cmp_to_key
 
# creates the comparator for comparing first element
def compare(a, b):
    return b[0] - a[0]
     
# Function to find maximum partitions.
def printSorted(arr,n):
    v =[]
    for i in range(n):
        count=0
        j=1
        # Count factors of arr[i].
        while(j*j<=arr[i]):
             
            # To check Given Number is Exactly
            # divisible
            if(arr[i]%j ==0):
                count+=1
                 
                # To check Given number is perfect
                # square
                if(arr[i]/j!=j):
                    count+=1
                 
            j+=1
        # Insert factor count and array element
        v.append((count,arr[i]))
         
    # Sort the vector
    # Sorting the arraylist elements in descending order
    v=sorted(v, key=cmp_to_key(compare))
     
    # Print the vector
    for a,b in v:
        print(b,end=" ")
 
# Driver Code
arr = [5, 11, 10, 20, 9, 16, 23]
n = len(arr)
printSorted(arr, n)
 
# This code is contributed by Aarti_Rathi

20 16 10 9 5 11 23

Complejidad de tiempo: O(n*sqrt(n)) 

Complejidad auxiliar: O(n)