diziyi sıralar

Question

Merhaba ben bu özel durumda diziyi sıralamak için denedim

a) ilk ascendingly

b gelmelidir 3 ile bölünebilir Tek sayılar) 3 ile bölünebilir bile numaralar) 3 ile bölünebilir olmayan Numaraları descendingly

c son gelmelidir ascendingly

bu benim kod edilir sıralanır

#include<algorithm> 
#include<iostream> 
using namespace std ; 

bool cmp(int b,int a){ 

    if((b%2 && b%3==0) && (a%2==0 || a%3 || b>a)) 
     return true ; 

    if((a%2==0 && a%3==0) && (b%2 || b%3)) 
     return true ; 

    return false ; 
} 

int main(){ 

int ar[8]={18 ,5 ,24 ,9 ,12 ,6 ,2, 3}; 

sort(ar,ar+8,cmp); 

for(int i=0;i<8;i++) 
    cout<<ar[i]<<endl ; 

return 0; 
} 

benim çıktı

Excepted

3 9 2 5 24 şimdi dizidir 3 bloka ayrılmış ama yukarıda belirtilen özel durum olarak sınıflandırılmamış

Answer 1

Karşılaştırma işleviniz oldukça karmaşık olduğundan, çok ayrıntılı bir şekilde yeniden yazdım, böylece olası her durum ayrı ayrı denetlenebilir. Ayrıca, her bir elemanın hangi bölüme girdiğine dair kararın farklı bir işleve ayrıldığını gördüm.

#include <algorithm> 
#include <iostream> 
#include <iterator> 

int classify(int const i) 
{ 
    if (i%3==0 && i%2!=0) { 
     return 1; 
    } 
    else if (i%3!=0) { 
     return 2; 
    } 
    else { 
     return 3; 
    } 
} 

bool comp(int const a, int const b) 
{ 
    int const a_part = classify(a); 
    int const b_part = classify(b); 

    if (a_part==1) { 
     if (b_part==1) { 
      // both in first partition, order ascending 
      return a<b; 
     } 
     else { 
      // a in first partition, b not, so a always first 
      return true; 
     } 
    } 
    else if (a_part==2) { 
     if (b_part==1) { 
      // b comes before a 
      return false; 
     } 
     else if (b_part==2) { 
      // both in middle partition, order ascendingly 
      return a<b; 
     } 
     else { 
      // a in middle partition, b in last partition, so a always first 
      return true; 
     } 
    } 
    else { // (a_part==3) 
     if (b_part!=3) { 
      // a in last partition, b in first or middle partition, 
      // so b always comes first 
      return false; 
     } 
     else { 
      // both in last partition, order descending 
      return b<a; 
     } 
    } 

} 

int main() 
{ 
    int ar[8] = {18 ,5 ,24 ,9 ,12 ,6 ,2, 3}; 
    std::sort(std::begin(ar), 
       std::end(ar), 
       comp); 
    std::copy(std::begin(ar), 
       std::end(ar), 
       std::ostream_iterator<int>(std::cout, 
             "\n")); 
} 

Çıktı:

$ ./SO 
3 
9 
2 
5 
24 
18 
12 
6 

Ayı düşünülerek karşılaştırıcı Bunu yapan düşünmek hangi bir Strict Weak Ordering uyarmak zorunda, ama bir normalde Sıralama için kullanmak istiyorsunuz daha biraz farklıdır.

Daima değil kısa mümkün olduğunca, mümkün olduğunca açıkça şekilde yazın. Bazı karmaşık mantıklarınız varsa, parçalara ayırın, parçaları fonksiyonlara taşıyın ve bol miktarda yorum ekleyin. Unutmayın, diğer insanlar 6 ay içinde kendiniz de dahil olmak üzere, onu okumalı ve anlamalıdır.

---

Daha iyi bir yaklaşım daha iyi bir yaklaşım olabilir. Diziyi, her biri farklı şekilde ele alınan 3 bölüme ayırmaktan bahsediyorsunuz. Bu nedenle, std::partition'u iki kez ve std::sort üç kez kullanın. Bence bu daha anlaşılabilir olabilir.

bool isOddMultipleOfThree(int const i) 
{ 
    return (i%3==0 && i%2!=0); 
} 

bool isEvenMultipleOfThree(int const i) 
{ 
    return (i%3==0 && i%2==0); 
} 

int main() 
{ 
    int ar[8] = {18 ,5 ,24 ,9 ,12 ,6 ,2, 3}; 

    // split off the first partition 
    auto firstSplit = std::partition(std::begin(ar), 
            std::end(ar), 
            isOddMultipleOfThree); 
    // sort the first partition 
    std::sort(std::begin(ar), 
       firstSplit, 
       std::less<int>()); 

    // split off end partition 
    // use a lambda to invert the predicate, because we want the matching 
    // values pushed to the end 
    auto secondSplit = std::partition(firstSplit, 
             std::end(ar), 
             [](int const i) { 
             return !isEvenMultipleOfThree(i); 
             }); 

    // sort middle partition 
    std::sort(firstSplit, 
       secondSplit, 
       std::less<int>()); 
    // sort last partition 
    std::sort(secondSplit, 
       std::end(ar), 
       std::greater<int>()); 

    // print 
    std::copy(std::begin(ar), 
       std::end(ar), 
       std::ostream_iterator<int>(std::cout, 
             "\n")); 
} 

Ayrıca

---

kayda değer, birçok kişi (ben dahil) using namespace std; düşünün ve std::endl kötü uygulamalar verilmiştir: Bu kod yukarıdaki gibi aynı çıkışa sahiptir.Üç bölümleri ve ardından her bölüm sıralama içine

Answer 2

ilk "bölünmüş" için std::partition kullanılması dizi, sen Soring sonra çıkış ne kadar olduğunu

#include <iostream> 
#include <array> 
#include <algorithm> 
#include <functional> 

int main() 
{ 
    std::array<int, 8> array = {{ 18 ,5 ,24 ,9 ,12 ,6 ,2, 3 }}; 

    std::cout << "Before first partitioning: "; 
    for (auto const value : array) 
     std::cout << value << ' '; 
    std::cout << '\n'; 

    // First partition putting all odd number even divisible by three first 
    auto second_start = std::partition(std::begin(array), std::end(array), [](int const& value) { 
     return (value % 2 != 0 && value % 3 == 0); 
    }); 

    std::cout << "Before second partitioning: "; 
    for (auto const value : array) 
     std::cout << value << ' '; 
    std::cout << '\n'; 

    // Then partition putting all even number even divisible by three first 
    auto third_start = std::partition(second_start, std::end(array), [](int const& value) { 
     return !(value % 2 == 0 && value % 3 == 0); 
    }); 

    std::cout << "Before sorting: "; 
    for (auto const value : array) 
     std::cout << value << ' '; 
    std::cout << '\n'; 

    std::sort(std::begin(array), second_start, std::less<int>()); 
    std::sort(second_start, third_start, std::less<int>()); 
    std::sort(third_start, std::end(array), std::greater<int>()); 

    std::cout << "After sorting: "; 
    for (auto const value : array) 
     std::cout << value << ' '; 
    std::cout << '\n'; 
} 

Çıktı

 
Before first partitioning: 18 5 24 9 12 6 2 3 
Before second partitioning: 3 9 24 5 12 6 2 18 
Before sorting: 3 9 2 5 12 6 24 18 
After sorting: 3 9 2 5 24 18 12 6 

gibi bir şey alacak beklersiniz.

"eylem" bölümünde bunun için here konusuna bakın.

Daha çok iştir, ancak beklendiği gibi davranması da garanti edilir.

Answer 3

Bu basit karşılaştırma işlevi benim için çalışıyor:

bool cmp(int lhs, int rhs){ 
    bool lhs_div_3 = lhs % 3 == 0; 
    bool rhs_div_3 = rhs % 3 == 0; 
    bool lhs_odd = lhs & 1; 
    bool rhs_odd = rhs & 1; 

    if (lhs_div_3 && lhs_odd) // lhs in class a) 
     if (rhs_div_3 && rhs_odd) 
      return lhs < rhs; 
     else 
      return true; 

    if (!lhs_div_3) // lhs in class c) 
     if (!rhs_div_3) 
      return lhs < rhs; 
     else 
      return !rhs_odd; 

    // else lhs in class b) 
    if (rhs_div_3 && !rhs_odd) 
     return rhs < lhs; 

    return false; 
} 

Ama Büyük diziler varsa ve başkaları tarafından tavsiye edildiği gibi muhtemelen bölüm verilerini toplar ve sonra bağımsız olarak her 3 parça sıralanması gerekir, performans umurumda (kaçınmak için böyle bir kompleks, yani, yavaş karşılaştırma fonksiyonu).

Answer 4

Bunun {partition1, partition2, order} için bir demet inşa edecek:

auto helper(int i) 
{ 
    bool isEven = i % 2 == 0; 
    bool isMul3 = i % 3 == 0; 
    return std::make_tuple(!(!isEven && isMul3), // partition 1 
          isEven && isMul3,  // partition2 
          isEven && isMul3 ? -i : i); // order 
} 

bool cmp(int lhs, int rhs){ 
    return helper(lhs) < helper(rhs); 
} 

Demo