Προς το περιεχόμενο
  • 1
Dr.Fuzzy

Non-recursive Heap Sort σε Structure

Ερώτηση

Λίγο τα φώτα σας.

'Εστω οι παρακάτω κλάσεις:

class Point2D {
 public:
  int x, y;
  Point2D();
};

class Vertex : public Point2D {
 public:
  int id;
  Vertex();
};

class Triangle {
 public:
  int id;  // Id number of this triangle
  Vertex a, b, c;
  int change;
  Triangle();
    
  static int sort_by;// Determines which member to sort by
  
  bool operator<(const Triangle& rhs) const {
  if( sort_by == 1) return a.id < rhs.a.id;// Sort by num1
    return a.id < rhs.b.id;// Sort by num2
  }
};
int Triangle::sort_by = 1;// Default will be to sort by num1

Χρησιμοποιώ την std::sort που είναι defined στο <algorithm>:

  Triangle::sort_by = 1;// default will be to sort by num1
  sort(triangles, triangles + MAX_NO_TRIANGLES);

και για παράδειγμα στις παρακάτω τριάδες (no, a.id, b.id, c.id):

Spoiler

(0,7,49,73)
(1,9,40,65)
(2,40,12,3)
(3,78,16,35)
(4,79,49,79)
(5,45,28,91)
(6,68,90,24)
(7,24,1,53)
(8,35,13,65)
(9,94,29,1)

 το sorted ως προς το a.id θα είναι:

Spoiler

(0,7,49,73)
(1,9,40,65)
(2,24,1,53)
(3,35,13,65)
(4,40,12,3)
(5,45,28,91)
(6,68,90,24)
(7,78,16,35)
(8,79,49,79)
(9,94,29,1)

Μέχρι εδώ καλά, όμως η sort χρησιμοποιεί αναδρομή που δεν υποστηρίζεται σε αυτό που κάνω οπότε βρήκα τον παρακάτω κώδικα που κάνει heap sort χωρίς recursion:

int c,root,temp;
for (int i = 1; i < MAX_NO_TRIANGLES; i++) {
        c = i;
        do {
            root = (c - 1) / 2;             
            if (triangles[root] < triangles[c]) {  /* to create MAX heap array */
                temp = triangles[root].a.id;
                triangles[root].a.id = triangles[c].a.id;
                triangles[c].a.id = temp;
            }
            c = root;
        } while (c != 0);
    }
 
    for (int j = MAX_NO_TRIANGLES - 1; j >= 0; j--) {
        temp = triangles[0].a.id;
        triangles[0].a.id = triangles[j].a.id;    /* Swap max element with rightmost leaf element */
        triangles[j].a.id = temp;
        root = 0;
        do {
            c = 2 * root + 1;    /* Left node of root element */
            if ((triangles[c].a.id < triangles[c + 1].a.id) && c < j-1)
                c++;
            if (triangles[root].a.id<triangles[c].a.id && c<j) {   /* Again rearrange to max heap array */
                temp = triangles[root].a.id;
                triangles[root].a.id = triangles[c].a.id;
                triangles[c].a.id = temp;
            }
            root = c;
        } while (c < j);
    }

Οπότε θέλω να το τροποποιήσω προκειμένου να κάνει sort ως προς το a.id ή b.id ή c.id ανάλογα τι θα διαλέξω. Έτσι όπως είναι τώρα προφανώς κάνει sort το a.id ανεξάρτητα αφήνοντας στις αρχικές τους θέσεις τα b.id, c.id.:

Spoiler

(0,7,49,73)
(1,9,40,65)
(2,40,12,3)
(3,78,16,35)
(4,79,49,79)
(5,45,28,91)
(6,68,90,24)
(7,24,1,53)
(8,35,13,65)
(9,94,29,1)
sorted
(0,7,49,73)
(1,9,40,65)
(2,24,12,3)
(3,35,16,35)
(4,40,49,79)
(5,45,28,91)
(6,68,90,24)
(7,78,1,53)
(8,79,13,65)
(9,94,29,1)

  

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

4 απαντήσεις σε αυτή την ερώτηση

Προτεινόμενες αναρτήσεις

  • 0
Δημοσ. (επεξεργασμένο)

Ο αλγόριθμος heap sort που έδωσες κάνει swap σε 2 σημεία (εκεί που χρησιμοποιεί την temp).

Απλά αλλαξε τον κωδικα εκει ετσι ωστε να κανει swap ολα τα στοιχεια αντι για μονο το a.id.

Επιπλέον θα προτεινα να το αντικαταστησεις με χρηση std::swap γιατι ειναι πιο συντομο και για να αποφυγεις το copy paste 3 γραμμων 2*2  φορες.

Επεξ/σία από vel0city
  • Thanks 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Σωστή παρατήρηση η swap, αυτά είναι τα κακά όταν παίρνεις έτοιμο κώδικα. Για την ακρίβεια είναι τρία τα swap.

Το άλλαξα και κάνει sort ως προς το a.id σωστά αλλά όχι ως προς το b.id (sort_by = 2). Λογικά το λάθος είναι κάπου στο bool operator που ορίζω μέσα στην κλάση Triangle. 

int c,root,temp;
for (int i = 1; i < MAX_NO_TRIANGLES; i++) {
  c = i;
    do {
        root = (c - 1) / 2;             
        if (triangles[root] < triangles[c]) {  // Create MAX heap array
          swap(triangles[root], triangles[c]);
        }
        c = root;
    } while (c != 0);
}
 
for (int j = MAX_NO_TRIANGLES - 1; j >= 0; j--) {
  swap(triangles[0], triangles[j]);
  root = 0;
  do {
      c = 2 * root + 1;  // Left node of root element
      if ((triangles[c] < triangles[c + 1]) && c < j-1) {
        c++;
      }
      if (triangles[root] < triangles[c] && c<j) {  // Again rearrange to max heap array
        swap(triangles[root], triangles[c]);
      }
      root = c;
  } while (c < j);
}

 

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Άκυρο το βρήκα, λάθος λόγω copy-paste στο bool operator! Στο else πρέπει να είναι:

return b.id < rhs.b.id; // Sort by num2

 

 

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0
Δημοσ. (επεξεργασμένο)

Μου φάνηκε περίεργο όταν το είδα αλλά λέω κάποιο λόγο θα'χει 😃

Επεξ/σία από vel0city
  • Haha 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε έναν λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι εύκολο!

Εγγραφείτε για έναν νέο λογαριασμό

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
×
×
  • Δημιουργία νέου...

Χρήσιμες πληροφορίες

Με την περιήγησή σας στο insomnia.gr, αποδέχεστε τη χρήση cookies που ενισχύουν σημαντικά την εμπειρία χρήσης.