Wie kann ich Array-Elemente nach Anzahl der Teiler sortieren?

Question

Mein Problem ist, dass ich ein Hindernis getroffen habe, während ich einige Übungen gelöst habe. Die Quelle des Problems ist, dass ich ein Programm schreiben muss, das absteigend ein Array nach der Anzahl der Teiler jedes Elements sortiert, aber wenn zwei Element die gleiche Anzahl von Teilern hat, sollte es aufsteigend diese Werte sortieren. Mein Code so weit:

#include <iostream> 
#include <fstream> 

using namespace std; 

int cntDiv(int n) //get number of divisors 
{ 
    int lim = n; 
    int c = 0; 
    if(n == 1) 
     return 1; 
    for(int i = 1; i < lim; i++) 
    { 
     if(n % i == 0) 
     { 
      lim = n/i; 
      if(lim != i) 
       c++; 
      c++; 
     } 
    } 
    return c; 
} 

int main() 
{ 
    ifstream fin("in.txt"); 
    int n, i, j; 
    fin >> n; 
    int v[n]; 
    for(i = 0; i < n; i++) 
     fin >> v[i]; 

    int div[n]; 
    for(i = 0; i < n; i++) 
     div[i] = cntDiv(v[i]); 

    for(i = 0; i < n - 1; i++) 
    { 
     for(j = i + 1; j < n; j++) 
     { 
      if(div[i] < div[j] && div[i] != div[j]) //if the number of divisors are different 
      { 
       int t = v[i]; 
       v[i] = v[j]; 
       v[j] = t; 

       t = div[i]; 
       div[i] = div[j]; 
       div[j] = t; 
      } 
      if(div[i] == div[j] && v[i] > v[j]) //if the number of divisors are the same 
      { 
       int t = v[i]; 
       v[i] = v[j]; 
       v[j] = t; 
      } 
     } 
    } 

    for(i = 0; i < n; i++) 
    { 
     cout << v[i] << " "; 
    } 
    return 0; 
} 

In.txt:

5 
12 20 4 100 13 

Ausgang:

100 12 20 4 13 

Obwohl es funktioniert gut mit diesem und vielen anderen. Bei größeren Eingängen überschreitet sie das Zeitlimit 0.1s. Irgendwelche Ratschläge wie soll ich die Sortierung umschreiben? (Ich schrieb Blasensortierung, weil ich Sortierung Array für Eigenschaft über Quicksort nicht implementieren konnte)

Answer 1

Verwenden Sie ein Array von Strukturen. Die Struktur würde den ursprünglichen Wert enthalten und einen Behälter von Divisoren:

struct Number_Attributes 
{ 
    int number; 
    std::list<int> divisors; 
}; 

können Sie dann eine Funktion Komparator individuelle schreiben und übergeben zu std::sort:

bool Order_By_Divisors(const Number_Attributes& a, 
         const Number_Attributes& b) 
{ 
    return a.divisors.size() < b.divisors.size(); 
} 

Die Sortierung wird dann:

#define ARRAY_CAPACITY (20U) 
Number_Attributes the_array[ARRAY_CAPACITY]; 
//... 
std::sort(&array[0], &array[ARRAY_CAPACITY], Order_By_Divisors); 

Die Generierung von Divisoren bleibt als Übung für das OP übrig.

Answer 2

nacharbeiten Code mit std::sort:

std::vector<std::pair<int, int>> customSort(const std::vector<int>& v) 
{ 
    std::vector<std::pair<int, int>> ps; 
    ps.reserve(v.size()); 

    // We don't have zip sort :/ 
    // So building the pair 
    for (auto e : v) 
    { 
     ps.emplace_back(e, cntDiv(e)); 
    } 
    std::sort(ps.begin(), ps.end(), [](const auto&lhs, const auto& rhs) { 
     // descending number of divisors, increasing value 
     return std::make_tuple(-lhs.second, lhs.first) 
      < std::make_tuple(-rhs.second, rhs.first); 
    }); 
    return ps; 
} 

int main() 
{ 
    const std::vector<int> v = {12, 20, 4, 100, 13}; 
    const auto res = customSort(v); 

    for(const auto& p : res) 
    { 
     std::cout << p.first << " "; 
    } 
} 

Demo