Non-recursive Heap Sort σε Structure

[Dr.Fuzzy]

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

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

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)

  

[vel0city]

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

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

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

Επεξ/σία 18 Δεκεμβρίου 2018 από vel0city

[Dr.Fuzzy]

Σωστή παρατήρηση η 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);
}

 

[Dr.Fuzzy]

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

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

 

 

[vel0city]

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

Επεξ/σία 18 Δεκεμβρίου 2018 από vel0city