Μερική Ταξινόμηση Φυσαλίδας

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

Φαντάζομαι η πιο απλή λύση είναι με τη λογική του countsort με 9 μετρητές, την αφήνω για όποιον ενδιαφέρεται να τη γράψει.

Όμως μια άλλη ενδιαφέρουσα λύση είναι να αποθηκεύουμε τους αριθμούς εισόδου σε ένα μόνο αριθμό ως ψηφία του και αντίστοιχα να τα εξάγουμε με βάση τη θέση τους μέσα στον αριθμό. Οπότε μπορούμε να προσαρμόσουμε τον bubblesort να αντιμεταθέτει ψηφία ενός αριθμού στη θέση j και j-1.

ΠΡΟΓΡΑΜΜΑ ΜεγαλυτεροιΝαπο1_9
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: πλ, numbers, x, N, i, j
ΑΡΧΗ
  πλ <- 0
  numbers <- 0          !Εδω θα αποθηκευτούν όλοι οι αριθμοι ως συνεχόμενα ψηφία
  ΔΙΑΒΑΣΕ x
  ΟΣΟ x <> 0 ΕΠΑΝΑΛΑΒΕ
    numbers <- numbers*10 + x
    πλ <- πλ + 1
    ΔΙΑΒΑΣΕ x
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΔΙΑΒΑΣΕ N                              !τους Ν μεγαλύτερους αριθμούς στο [1,9]

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ N + 1
    ΓΙΑ j ΑΠΟ πλ ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
      ΑΝ ΨηφιοΣτηΘεση(numbers, j) > ΨηφιοΣτηΘεση(numbers, j - 1) ΤΟΤΕ
        numbers <- Αντιμεταθεσε(numbers, j) 
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
    ΓΡΑΨΕ ΨηφιοΣτηΘεση(numbers, i) 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΣΥΝΑΡΤΗΣΗ ΨηφιοΣτηΘεση(numbers, k): ΑΚΕΡΑΙΑ      !Επιστρέφει το ψηφίο στη θέση κ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: numbers, k
ΑΡΧΗ
  ΨηφιοΣτηΘεση <- numbers div Α_Μ(10^(k - 1)) mod 10
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

ΣΥΝΑΡΤΗΣΗ Αντιμεταθεσε(numbers, j): ΑΚΕΡΑΙΑ!Επιστρέφει τον αριθμό με τις τιμές στα ψηφία στις θέσεις j και j-1 αντιμεταθετιμένες
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: numbers, j, ψηφιοj, ψηφιοj_1
ΑΡΧΗ
  ψηφιοj <- ΨηφιοΣτηΘεση(numbers, j) 
  ψηφιοj_1 <- ΨηφιοΣτηΘεση(numbers, j - 1) 
  Αντιμεταθεσε <- Α_Μ(numbers - ψηφιοj*10^(j - 1) - ψηφιοj_1*10^(j - 2) + ψηφιοj*10^(j - 2) + ψηφιοj_1*10^(j - 1)) 
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

[Foto]

Θέλουμε ένα πίνακα με δείκτη από 1 έως 9 όπου θα γράφουμε τις παρουσίες αριθμών. Αν εισαχθεί το 3 τότε το Α[3] θα αυξηθεί κατά 1. Μετά την εισαγωγή του 0 βγαίνουμε από το κομμάτι του κώδικα για εισαγωγή και πάμε στην εισαγωγή του Ν. Οπότε ξεκινάμε σε διπλό Για, το πρώτο από Ν+1 έως 9, το δεύτερο εφόσον το Α[ι]>0 από 1 μέχρι Α[ι] εμφανίζουμε το ι, Α[ι] φορές. Επειδή αναφέρει Ο(1), μπορούμε να αποφύγουμε το εσωτερικό Για με μια απλή Γράψε ι τόσες φορές Α[ι].

[Εβελινακι]

Καλησπέρα έχω μία απορία για την αρχή του παρακάτω προγράμματος Πως θα εκτελέσω την εντολή εισαγωγής των ονομάτων(«το πολύ»)

Να γράφει πρόγραμμα το οποίο να διαβάζει το πολύ 100 ονόματα και να τα εμφανίζει αλφαβητικά. Σε περίπτωση που δοθεί ο χαρακτήρας '#' Να σταματάει η εισαγωγή των ονομάτων και να ταξινομούνται όσα έχουν δοθεί.

[George Eco]

Καλησπέρα έχω μία απορία για την αρχή του παρακάτω προγράμματος Πως θα εκτελέσω την εντολή εισαγωγής των ονομάτων(«το πολύ»)

Να γράφει πρόγραμμα το οποίο να διαβάζει το πολύ 100 ονόματα και να τα εμφανίζει αλφαβητικά. Σε περίπτωση που δοθεί ο χαρακτήρας '#' Να σταματάει η εισαγωγή των ονομάτων και να ταξινομούνται όσα έχουν δοθεί.

Ο πίνακας θα είναι 100 στοιχείων.
Ωστόσο μπορεί να σταματήσει η εισαγωγή προτού συμπληρωθούν και τα 100 στοιχεία.
Οπότε θα πρέπει να κρατάς και σε μια μεταβλητή το πλήθος εισαχθέντων και θα αντιμετωπίζεις τον πίνακα ως μικρότερο αν τερματιστεί η εισαγωγή πριν το 100.
Η φράση "το πολύ" ουσιαστικά σου ορίζει το μέγεθος του πίνακα. Έχει πέσει πρόσφατα σχετικά παρόμοιο θέμα Πανελληνίων.