Ταξινόμηση δισδιάστατου πίνακα nxn

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
kkkkonstantina
Δημοσιεύσεις: 14
Εγγραφή: 12 Νοέμ 2009 17:49

Ταξινόμηση δισδιάστατου πίνακα nxn

Δημοσίευση από kkkkonstantina » 20 Οκτ 2012 00:56

Θα ήθελα να ταξινομήσω ένα δισδιάστατο δυναμικό πίνακα,γίνεται να κάνω κατευθείαν ταξινόμηση σε πίνακα δύο διαστάσεων ή θα πρέπει να τον μετατρέψω πρώτα σε μονοδιάστατο.? Σκεφτόμουν να τον ταξινομήσω με insertion sort έχω έτοιμο τον αλγόριθμο για τον μονοδιάστατο πίνακα βέβαια αλλά κολλάω στο πως να κάνω την ταξινόμηση να λειτουργεί για δισδιάστατο πίνακα..Ευχαριστώ!

PanosPss
Δημοσιεύσεις: 78
Εγγραφή: 10 Μάιος 2008 19:53

Ταξινόμηση δισδιάστατου πίνακα nxn

Δημοσίευση από PanosPss » 05 Δεκ 2012 01:54

Κωνσταντίνα μου ταξινόμηση σε δισδιάστατο πίνακα γίνετε ΜΟΝΟ είτε κατα γραμμή είτε ΜΟΝΟ κατα στήλη... ΠΟΤΕ σε συνδυασμό δεν γίνετε. Οπότε θα πρέπει να επιλέξεις :)

mariosal
Honorary Member
Δημοσιεύσεις: 1473
Εγγραφή: 09 Νοέμ 2007 23:55

Ταξινόμηση δισδιάστατου πίνακα nxn

Δημοσίευση από mariosal » 12 Δεκ 2012 11:33

Η βέλτιση ταξινόμηση n × n που μπορώ να σκεφτώ έχει worst-case πολυπλοκότητα O( n²logn ).

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <algorithm>

using namespace std;

int n;

bool cmp&#40; int *a, int *b &#41; &#123;
  for &#40; int i = 0; i < n; ++i &#41; &#123;
    if &#40; a&#91; i &#93; != b&#91; i &#93; &#41; &#123;
      return a&#91; i &#93; < b&#91; i &#93;;
    &#125;
  &#125;
&#125;

int main&#40;&#41; &#123;
  int i, j, **a;

  scanf&#40; "%d", &n &#41;;

  // Allocating memory and reading
  a = new int*&#91; n &#93;;
  for &#40; i = 0; i < n; ++i &#41; &#123;
    a&#91; i &#93; = new int&#91; n &#93;;
    for &#40; j = 0; j < n; ++j &#41; &#123;
      scanf&#40; "%d", a&#91; i &#93; + j &#41;;
    &#125;
  &#125;

  // Sorting
  for &#40; i = 0; i < n; ++i &#41; &#123;
    sort&#40; a&#91; i &#93;, a&#91; i &#93; + n &#41;;
  &#125;
  sort&#40; a, a + n, cmp &#41;;

  // Printing
  for &#40; i = 0; i < n; ++i &#41; &#123;
    for &#40; j = 0; j < n; ++j &#41; &#123;
      printf&#40; "%s%d", j ? " " &#58; "", a&#91; i &#93;&#91; j &#93; &#41;;
    &#125;
    printf&#40; "\n" &#41;;
  &#125;

  return 0;
&#125;

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες