Блог пользователя __noob___

Sort using comparator in c++
Автор __noob___, история, 6 лет назад, По-английски

Can anybody tell me how to sort using Comparator in C++ in any specific order what are the condition required for such sorting and also what is the time complexity for sorting using comparator.
Example sort the pairs (1,2),(3,4),(6,10),(7,2) on the basis of if( ( a1 / b1 ) < ( a2 / b2 ) ) then (a1,b1) pair should come first in the order.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

http://bfy.tw/NJxy

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have tried to google but still not cleared with it. Can you pls help me?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      first link in the google searching list:

      http://www.cplusplus.com/reference/algorithm/sort/

      I am not sure if it can be explained even more clear.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        So If I need to sort the pair according to the same method then I just need to do like.
        bool myfunction (pair<int,int> i,pair<int,int> j) { return (i.first*j.second<j.first*i.second); }
        //what exactly is returning i<j doing?

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          In your code, myfunction returns if the pair i should come before the pair j.

          Returning i < j (which is the default), will compare it by first then second:

          if(i.first == j.first)
    return i.second < j.second;
return i.first < j.first;
          → Ответить
          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            So if I want to sort according to a_i/b_i then my code will work.
            One last thing what can we say about the time complexity of this sorting and why?

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Your code above is OK.

              Since comparison takes O(1), the whole sort method is O(NlogN).

              → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          yes, and after that do sort(.., .., myfunction)

          → Ответить