Ταξινόμηση πίνακα με βάση το Όνομα

Ξεκίνησε από michalis, 04 Ιαν 2007, 11:41:06 ΠΜ

« προηγούμενο - επόμενο »

michalis

Καλημέρα και καλή χρονιά σέ όλους
Εχω μία ασκηση η οποία στο τελευταίο ερώτημα ζητά να γίνει η ταξινόμηση του με βάση τα ονόματα των πωλητών μια εταιρίας. μπορει κάποιος να προτείνει κάποια λύση?
ευχαριστώ.

dimitrios67

Κανονικά τα ονόματα των πωλητων πρεπει να ειναι σε κάποιον πίνακα. Η μεταβλητη ειναι χαρακτηρας, και κανεις bubblesort...
Ελπιζω να βοήθησα

EleniK

#2
Φαντάζομαι ότι με βάση τα ονόματα, εννοεί αλφαβητικά. Σε αυτήν την περίπτωση κάνεις αύξουσα ταξινόμηση με βάση των πίνακα των ονομάτων αλλά παράλληλα αντιμεταθέτεις τους παράλληλους πίνακες.

Δλδ αν π.χ. η άσκηση αναφέρει το εισόδημα των Ν πωλητών και τα ονόματα και θέλει να εμφανιστούν τα ονόματα και δίπλα το εισόδημα των πωλητών με βάση τα ονόματα τους τότε:

Για i από 2 μέχρι N
  Για j από Ν μέχρι i με_βήμα -1
      Αν Ον[j]<Oν[j-1] τότε
          Temp1 <- Oν[j]
          Oν[j] <- Oν[j-1]
          Oν[j-1] <- Temp1
          Temp2 <- Εισ[j]
          Εισ[j] <- Εισ[j-1]
          Εισ[j-1] <- Temp2
       τέλος_αν
τέλος_επανάληψης
τέλος_επανάληψης

Για j από 1 μέχρι Ν
Εμφάνισε Ον[j], Εισ[j]
τέλος_επανάληψης

Με λίγα λόγια κάνεις αύξουσα ταξινόμηση με βάση τα ονόματα (7ο Κεφ) αλλά σε κάθε αλλαγή ακολουθεί και η αντιμετάθεση των εισοδημάτων έτσι ώστε οι δυο πίνακες να παραμείνουν παράλληλοι, δλδ οι αντίστοιχες θέσεις να αναφέρονται σε στοιχεία του ίδιου πωλητή.
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

petrosp13

Οι γλώσσες προγραμματισμού υποστηρίζουν σύγκριση αλφαριθμητικών και μπορούν να κάνουν ταξινόμηση
Βέβαια, δεν ξέρω πόσοι από μας είχαμε προλάβει να το περάσουμε αυτό στους μαθητές πριν τις εξετάσεις τους 2004, όταν σε κάποιο ερώτημα ζητούσε την αλφαβητική ταξινόμηση κάποιων ονομάτων και οι περισσότεροι μαθητές έμειναν με την απορία
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

EleniK

@petrosp_13
Νομίζω ότι αρκετά βοηθήματα είχαν ασκήσεις με αλφαβητική ταξινόμηση. Παρόλαυτα το υποερώτημα έπιανε 7 μόρια, οπότε ήταν καλό για να ξεχωρίσουν και όσοι σκέφτονταν εκτός από αυτούς βέβαια που το είχαν απλά διδαχθεί.
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

johnny_xp

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

michalis

αυτό ακριβώς ζητούσα παιδια. απλα δε γνωριζα οτι η ταξινόμηση περιλαμβάνει ονόματα. επίσης κάτι άλλο
γιατι στη φυσσαλίδα βάζουμε επανάληψη και για το i και για το j απο τη στιγμή που στις εγραφές υπάρχει το j??
Για i από 2 μέχρι N  ! γιατί ξεκινά απο το 2 η αρίθμηση?
Για j από Ν μέχρι i με_βήμα -1
      Αν Ον[j]<Oν[j-1] τότε
          Temp1 <- Oν[j]


ο αλγόσριθμος που έδειξα στους μαθητέσ ήταν ακριβώς ο ιδιος με της Εlenik
σας ευχαριστώ

petrosp13

Το ότι ο πίνακας είναι μονοδιάστατος, δεν σημαίνει ότι θα χρειαστούμε 1 επανάληψη για να τον επεξεργαστούμε
Πιο συγκεκριμένα, η "μέσα" επανάληψη (η επανάληψη του j) ουσιαστικά μετακινεί το μικρότερο (ή μεγαλύτερο) στοιχείο του αταξινόμητου τμήματος του πίνακα προς τα επάνω, στην πρώτη θέση του αταξινόμητου τμήματος. Βέβαια, συγχρόνως γίνονται και άλλες αλλαγές θέσεων στον πίνακα
Η "έξω" επανάληψη (η επανάληψη του i) απλά ορίζει πόσες τέτοιες επεξεργασίες θα γίνουν (Ν-1)
Δηλαδή, Ν-1 φορές μετακινείται κάθε φορά το μικρότερο (ή μεγαλύτερο) στοιχείο από το αταξινόμητο κομμάτι προς τα πάνω

Το ι ξεκινάει από 2 γιατί η επανάληψη του j καταλήγει στην τιμή i. Άρα, τα τελευταία στοιχεία που συγκρίνονται στην πρώτη επανάληψη του j (για ι=2) είναι τα Α[j] και Α[j-1], δηλαδή το δεύτερο με το πρώτο. Αν το i ξεκινούσε από 1, θα έπρεπε να συγκρίνει το Α[1] με το ανυπόστατο Α[0]
Θα μπορούσαμε να έχουμε επανάληψη από 1 μέχρι Ν-1 και να συγκρίνουμε τα στοιχεία A[j] και A[j+1]
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

michalis

εδώ υπάρχει λάθος?

Για i απο 1 μέχρι 99 !για πίνακα 100 θέσεων
Aν Π[i+1]<Π τότε
  temp<- Π
  Π[ι]<-Π[ι+1]
  Π[ι+1]<-temp
τελος_αν
Τέλος _επανάληψης

για αύξουσα ταξινόμηση

petrosp13

Το συγκεκριμένο που έγραψες, απλά θα μεταφέρει το μεγαλύτερο στοιχείο στην τελευταία θέση
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

EleniK

@michalis

Ερώτηση 1: Γιατί από 2?
Η επανάληψη ξεκινάει απο το 2 έτσι ώστε όταν προσπαθεί να βρει το πρώτο στοιχείο της ταξινόμησης (μεγαλύτερο η μικρότερο ανάλογα με την ταξινόμηση) τα τελευταία στοιχεία που συγκρίνει είναι το  Α[2] με το Α[1]. Αν η επανάληψη του i ξεκινάει από 1, τότε  η τελευταία σύγκριση θα είναι Α[1] με Α[0] κάτι που δεν  γίνεται γιατί θα φύγεις εκτός ορίων του πίνακα  :o.



Ερώτηση 2: γιατί 2 επανάληψεις

Η επανάληψη για το i δείχνει πόσα "περάσματα" θα γίνουν μέχρι να ταξινομηθεί πλήρως ο πίνακας, ενώ η επανάληψη για το j ΄"τρέχει" τους ελέγχους απο κάτω προ τα πάνω.
Έτσι αν Ν τα στοιχεία πίνακα τότε εκτελούνται Ν-1 περάσματα.
Στο 1ο πέρασμα θα γίνουν Ν-1 έλεγχοι,
Στο 2ο πέρασμα θα γίνουν Ν-2 έλεγχοι κ.ο.κ.

Ελπίζω να βοήθησα κάπως.
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19