Θέμα: Να αντιγράψουμε ή να μην αντιγράψουμε?

[Michael]

Άσκηση:
Δίνεται δισδιάστατος πίνακας ακεραίων Α[1000,2000]. Να αναπτύξετε αλγόριθμο που υπολογίζει και εκτυπώνει τα 10 μεγαλύτερα στοιχεία του πίνακα.
(Σημείωση: Να θεωρήσετε ότι τα στοιχεία του πίνακα Α είναι μοναδικά.)

Η άσκηση αυτή "μου ήρθε" διότι ενώ έχω δει πολλές αντίστοιχες που αφορούν σε μονοδιάστατους πίνακες, δεν έχω δει ούτε μία που αφορά σε δισδιάστατους. Αν ήταν μονοδιάστατος θα τον ταξινομούσαμε κτλ... Τώρα όμως?
Μια "προφανής" λύση είναι να αντιγράψουμε τον Α[1000,2000] σε μονοδιάστατο Β[ 2000000 ]. Δηλαδή:

Για i από 1 μέχρι 1000
  Για j από 1 μέχρι 2000
    Β[ (j-1)*1000+i ] <- A[i,j]
  Τέλος_επανάληψης
Τέλος_επανάληψης

Στη συνέχεια, ταξινομούμε τον Β και εκτυπώνουμε τα 10 μεγαλύτερα.
Η ερώτησή μου είναι: Υπάρχει αποδοτικότερος (εντός ύλης) τρόπος ή πρέπει αναγκαστικά να γίνει αντιγραφή σε νέο πίνακα και στη συνέχεια φυσαλίδα σ' αυτόν? Για να το θέσω διαφορετικά: Αν στις εξετάσεις ζητούνταν κάτι αντίστοιχο, πώς θα έλυναν τη συγκεκριμένη άσκηση οι "επίσημες" λύσεις που θα είχαν στα χέρια τους οι διορθωτές?

[alkisg]

Μπορούμε να ταξινομήσουμε και τον δισδιάστατο σαν να ήταν μονοδιάστατος, δεν έχει διαφορά. Δες το https://alkisg.mysch.gr/steki/index.php?topic=310.msg2054#msg2054 για λεπτομέρειες.
Ουσιαστικά πρόκειται για τον ίδιο τύπο που έβαλες κι εσύ: Β[ (j-1)*1000+i ]

Ένας άλλος τρόπος που θα μπορούσε να σκεφτεί κάποιος μαθητής θα ήταν να έχει έναν πίνακα MAX 10 στοιχείων στον οποίο θα κρατάει τα μέγιστα.
Οπότε χωρίς ταξινόμηση,
κάνει δύο ΓΙΑ για όλα τα στοιχεία του Α,
και για κάθε στοιχείο Α[ί,j] κάνει εύρεση ελαχίστου στον πίνακα MAX κρατώντας και τη θέση του,
οπότε τελικά ΑΝ Α[ί,j] > ΜΑΧ[θέση] ΤΟΤΕ MAX[θέση] <- Α[ί,j]

Αυτή η λύση είναι πολύ πιο αποδοτική από την ταξινόμηση, και δε νομίζω ότι είναι ιδιαίτερα δύσκολη για να τη σκεφτεί (ή να την έχει διδαχτεί) ένας μαθητής...

[Michael]

Καλό! Αν κατάλαβα καλά:

Για i από 1 μέχρι 1000
  Για j από 1 μέχρι 2000
    min<- MAX[ 1 ]
    pos<- 1
    Για k από 2 μέχρι 10
      Αν MAX[ k ]<min τότε
        min<-MAX[ k ]
        pos<- k
      Τέλος_αν
    Τέλος_επανάληψης
    Αν Α[i,j]>MAX[ pos ] τότε
      ΜΑΧ[ pos ]<-A[i,j]
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

Όμως:

1) Ο πίνακας ΜΑΧ θα πρέπει να έχει ήδη αρχικοποιηθεί πριν από το παραπάνω τμήμα. Δηλαδή θα πρέπει να έχουμε αντιγράψει στον πίνακα ΜΑΧ[ 10 ], δέκα οποιαδήποτε στοιχεία του Α[1000,2000]. Στην περίπτωσή μας, αυτό θα μπορούσε να γίνει εύκολα με κάτι σαν:

Για i από 1 μέχρι 10
  ΜΑΧ[ i ]<-Α[i,1]
Τέλος_επανάληψης

(Αντιγράψαμε δηλαδή τα 10 πρώτα στοιχεία της πρώτης στήλης του Α. Είμαστε σίγουροι ότι δεν υπάρχει περίπτωση να ξεφύγουμε από τα όρια του πίνακα, διότι ο Α έχει 1000 (>10) γραμμές.)
Τι γίνεται όμως στη γενικότερη περίπτωση? Πώς θα μπορούσαμε να αρχικοποιήσουμε τον ΜΑΧ[ 10 ] αν η εκφώνηση ήταν:

Δίνεται πίνακας ακεραίων Α[Ν,Μ]. Να αναπτύξετε αλγόριθμο που υπολογίζει και εκτυπώνει τα 10 μεγαλύτερα στοιχεία του πίνακα.
Σημείωση: Να θεωρήσετε ότι τα στοιχεία του πίνακα Α είναι μοναδικά και ότι ο Α περιέχει τουλάχιστον 10 στοιχεία (Ν*Μ>=10).

2) Ακόμη κι αν θεωρήσουμε την αρχική εκφώνηση, οι δύο τρόποι λύσης είναι ισοδύναμοι βαθμολογικά?
Εσείς αν ήσασταν υποψήφιοι και ενδιαφερόσασταν για τη βαθμολογία της λύσης σας, ποιον τρόπο θα επιλέγατε να χρησιμοποιήσετε και γιατί? Ουσιαστικά, η ανησυχία μου είναι:
Διορθωτής: «Οι επίσημες λύσεις με βάση τις οποίες βαθμολογώ, δεν το λύνουν έτσι. Θα κόψω λοιπόν.»

[alkisg]

Για το (1):

Κώδικας: ΓΛΩΣΣΑ

1. ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 10
2.   MAX[ι] <- Α[(ι-1) div Ν + 1, (ι-1) mod N + 1]
3. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Δηλαδή αρχικοποιούμε με τα πρώτα 10 στοιχεία του δισδιάστατου πίνακα όπως τον διαβάζουμε, από πάνω αριστερά προς τα κάτω δεξιά.

Για το (2) προσωπική μου άποψη είναι ότι οι δύο λύσεις είναι ισοδύναμες. Μάλιστα θα έλεγα ότι είναι πιο πιθανό να βρεθεί κάποιος που θα κόψει μονάδες στην πρώτη λύση με την ταξινόμηση, επειδή λύνει το πρόβλημα... μέσω Λαμίας (αλήθεια οι Λαμιώτες πώς τη λένε αυτήν την έκφραση;!!!), παρά να βρεθεί κάποιος που θα βαρεθεί να αναλύσει τη δεύτερη λύση και να καταλάβει ότι είναι ολόσωστη.

[Γιαννούλης Γιώργος]

Η ερώτησή μου είναι: Υπάρχει αποδοτικότερος (εντός ύλης) τρόπος ή πρέπει αναγκαστικά να γίνει αντιγραφή σε νέο πίνακα και στη συνέχεια φυσαλίδα σ' αυτόν? Για να το θέσω διαφορετικά: Αν στις εξετάσεις ζητούνταν κάτι αντίστοιχο, πώς θα έλυναν τη συγκεκριμένη άσκηση οι "επίσημες" λύσεις που θα είχαν στα χέρια τους οι διορθωτές?

Αποδοτικοτεροι τροποι υπάρχουν, και ειναι και μπολικοι.  Ένας ειναι ο εξής:
1) Να ταξινομησεις ανα γραμμή τον πίνακα.
2) Δημιουργεις έναν πίνακα Β μονοδιαστατο 1000 θέσεων (οσες και οι γραμμές σου) και τον αρχικοποιείς να έχει παντου 1 (κάθε θέση αυτού του πίνακα κοιτάει στην αντιστοιχη στηλη της γραμμής του και στην αρχη ολοι κοιταν στο μικροτερο στοιχειο της γραμμης τους αφου ειναι ταξινομημένος ανα γραμμή αρα στο 1ο)
3)Συγκρίνεις ΜΟΝΟ τα στοιχεία που σου "δειχνει" ο πινακας Β καπως ετσι

Για j απο 1 μεχρι 10 ! όσα νουμερα θέλουμε να εμφανίσει Απαραιτητα <=2000 αλλιώς υπαρχει λογικό σφάλμα...
  min<-- Α[1, B[ i]]
  γρ<--1 ! Η γραμμή που βρήκαμε το μικρότερο στοιχείο
  Για i απο 2 μεχρι 2000
    Αν min>Α[i,B [ i] ] τοτε
      min<--Α[i,B [ i] ]
      γρ<--i
    Τέλος_Αν
  Τέλος_επανάληψης
  Γράψε Α[γρ,Β[γρ]]
  Β[γρ]<--Β[γρ]+1
Τέλος_επανάληψης

Με αυτόν τον τρόπο η πολυπλοκότητα ειναι για έναν πίνακα Μ*Ν αν ψάχνουμε τα κ μικρότερα στοιχεία είναι:
 (Μ*Ν^2 για τις ταξινομήσεις ) + (κ*Μ για τις συγκρίσεις)
Επειδή το κ είπαμε είνα απαραίτητα < Ν έχουμε
=Ο(Μ*Ν^2+κ*Μ) = Ο(Μ*Ν^2+Ν*Μ) = Ο(Μ*Ν^2)

Ενώ με την ταξινόμηση του πίνακα έχεις Ν*Μ στοιχεία με πολυπλοκότητα Ο( (Ν*Μ)^2  ) που είναι σαφώς μεγαλύτερη.

[evry]

Εμένα πάλι μου φαίνεται ότι με την ξερή ταξινόμηση έχουμε καλύτερη πολυπλοκότητα γιατί στην ταξινόμηση του μονοδιάστατου πίνακα με Μ*Ν στοιχεία η πολυπλοκότητα δεν θα είναι (Μ*Ν)^2 αλλά Μ*Ν*κ και αφού κ<<Μ,Ν τότε έχουμε Ο(Μ*Ν)

αφού θέλουμε να ανέβουν μόνο οι πρώτες κ φυσαλίδες άρα δεν ταξινομούμε όλον τον πίνακα, οπότε η εξωτερική επανάληψη της φυσαλίδας θα γίνει μόνο κ φορές, εκτός αν κάτι δεν κατάλαβα καλά

[Γιαννούλης Γιώργος]

Έχεις δίκιο, βασικά και αλγόριθμος που λέω έχει ίδια πολυπλοκότητα αν στην ταξινόμηση ανα κάθε γραμμη δεν την πας μεχρι τέλους αλλά μονο για κ στοιχεία. Οπότε έχεις κ*Ν*Μ+κ*Μ=κ*Ν*Μ.

Βγάζει καλύτερη πολυπλοκότητα αν προσθέσουμε ένα βήμα (μου άρεσε η ταχιστη αντίδραση σου evri) μισο να το παλεψω στο χαρτι...

[Γιαννούλης Γιώργος]

Παμε πάλι τον αλγόριθμο.
Έχουμε τον πίνακα Α[Μ,Ν] και θέλουμε τα κ μικρότερα στοιχεία του.

1)Δημιουργουμε 2 μονοδιαστατους πίνακες τον ΘΕΣΗ και τον ΜΙΝ και οι 2 μεγέθους Μ.
2)Στον πίνακα ΘΕΣΗ στην θέση ΘΕΣΗ[ i ]<--i , για κάθε i
3)Στον πίνακα ΜΙΝ στην θέση ΜΙΝ[ i ]<--το μικρότερο στοιχείο της γραμμής i
4)Ταξινόμησε τον πίνακα ΜΙΝ και παράλληλα εναλλασε και τις θέσεις στον πίνακα ΘΕΣΗ. (Έτσι στο τέλος θα έχουμε στον πίνακα ΘΕΣΗ στις κ πρώτες γραμμες του,τις γραμμές εκείνες που θα έχουν σίγουρα τα κ μικρότερα στοιχεία).
5)Στην συνέχεια ταξινομούμε τις κ γραμμες που αναφέρονται στις κ πρώτες θέσεις του πίνακα, αλλά ταξινομόντας μόνο τα κ μικρότερα στοιχεία τους.
6)Βάζω στον πίνακα ΜΙΝ στις κ πρώτες θέσεις του (οσες και οι γραμμές) 1 (κάθε θέση αυτού του πίνακα κοιτάει στην αντιστοιχη στηλη της γραμμής που βρίσκεται στον ΘΕΣΗ[ i ] και στην αρχη ολοι κοιταν στο μικροτερο στοιχειο της γραμμης τους αφου ειναι ταξινομημένος ανα γραμμή αρα στο 1ο)
7)Συγκρίνεις ΜΟΝΟ τα στοιχεία που σου "δειχνει" ο πινακας Β.

Αλγόριθμος ΤαξινομησηΔισδιάστατου
  Δεδομένα //  A,Μ,Ν,κ  //

  ! Βήμα 2,3

  Για i απο 1 μέχρι Μ
    ΘΕΣΗ[ i ]<--i
    tmin<--A[i,1]
    Για j απο 2 μέχρι Ν
      Αν tmin>Α[i,j] τοτε
        tmin<--Α[i,j]
      Τέλος_Αν
      MIN[ i ]<--tmin
  Τέλος_επανάληψης

  !Βήμα 4

  Για i απο 2 μέχρι κ+1
    Για j απο Μ μέχρι i με_βήμα -1
      Αν ΜΙΝ[ j ]<MIN[ j-1 ] τοτε
        Αντιμετάθεσε ΜΙΝ[ j ],MIN[ j-1 ]
        Αντιμετάθεσε ΘΕΣΗ[ j ],ΘΕΣΗ[ j-1]
      Τέλος_Αν
    Τέλος_Επανάληψης
  Τέλος_Επανάληψης

  !Βήμα 5

  Για γρ απο 1 μέχρι κ !το σε ποια γραμμή είμαι το βλέπω απο το ΘΕΣΗ[γρ]
    Για i απο 2 μέχρι κ+1 !Πόσες επαναλήψης χρειάζομαι ανα γραμμή
      Για j απο Ν μέχρι i με_βήμα -1 !Η στήλη που βρίσκομαι αυτήν την στιγμή
        Αν Α[ΘΕΣΗ[ γρ ],j ]<Α[ΘΕΣΗ[ γρ ],j-1 ] τοτε
          Αντιμετάθεσε Α[ΘΕΣΗ[ γρ ],j ],Α[ΘΕΣΗ[ γρ ],j-1 ]
        Τέλος_Αν
      Τέλος_Επανάληψης
    Τέλος_Επανάληψης
  Τέλος_Επανάληψης

  !Βήμα 6

  Για i απο 1 μέχρι κ
    ΜΙΝ[ i ]<--1
  Τέλος_επανάληψης

  !Βήμα 7

  !Τωρα χρησιμοποιούμε απλά τις κ πρώτες θέσεις του ΜΙΝ για να μας δείχνουν την στήλη που βρισκόμαστε στην γραμμή i
  Για i απο 1 μεχρι κ ! όσα νουμερα θέλουμε να εμφανίσει Απαραιτητα <Ν αλλιώς υπαρχει λογικό σφάλμα...
    tmin<-- Α[Θεση[ 1 ], MIN[ 1 ]]
    γρ<--1 ! Η γραμμή που βρήκαμε το μικρότερο στοιχείο
    Για j απο 2 μεχρι κ
      Αν tmin>Α[Θέση[ j ],ΜΙΝ[ j ] ] τοτε
        tmin<--Α[Θέση[ j ],ΜΙΝ[ j ] ]
        γρ<-- j
      Τέλος_Αν
    Τέλος_επανάληψης
    Εμφάνισε Α[ΘΕΣΗ[γρ],MIN[ γρ ]]
    MIN[γρ]<--MIN[γρ]+1
  Τέλος_επανάληψης
Τέλος_αλγόριθμος

Πολυπλοκότητα:
Βημα 2,3:   Μ*Ν
Βημα 4: Μ*κ
Βημα 5: κ^2 * Ν
Βήμα 6: κ
Βήμα 7: κ^2
Συνολικά: Ο(Μ*Ν+Μ*κ+κ^2*Ν+κ+κ^2) και επειδή κ<=Ν και κ<=Μ έχουμε
Ο(Μ*Ν+Ν*κ^2)=Ο(Ν*(Μ+κ^2)) το οποίο είναι καλύτερο από το Ο(Μ*Ν*κ) που δίνει ο απλός αλγόριθμος.

Ουφφφφφφ

[Καρκαμάνης Γεώργιος]

Άσκηση:
Δίνεται δισδιάστατος πίνακας ακεραίων Α[1000,2000]. Να αναπτύξετε αλγόριθμο που υπολογίζει και εκτυπώνει τα 10 μεγαλύτερα στοιχεία του πίνακα.
(Σημείωση: Να θεωρήσετε ότι τα στοιχεία του πίνακα Α είναι μοναδικά.)

Η άσκηση αυτή "μου ήρθε" διότι ενώ έχω δει πολλές αντίστοιχες που αφορούν σε μονοδιάστατους πίνακες, δεν έχω δει ούτε μία που αφορά σε δισδιάστατους. Αν ήταν μονοδιάστατος θα τον ταξινομούσαμε κτλ... Τώρα όμως?

Michael, ασκήσεις τέτοιου τύπου(ταξινόμηση σε δισδιάστατο) δεν έχεις δει, διότι στο βιβλιο του μαθητή δεν αναφέρεται ταξινόμηση δισδιάστατου πίνακα παρα μόνο μονοδιάστατου.

Αν ζητηθεί σε μια άσκηση(που δεν νομίζω) θα περιγράφει τον τρόπο που θα γίνει η ταξινόμηση δηλαδή όλα αυτά τα βήματα που περιγράφεται παραπάνω