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

[nikolasmer]

Έστω πίνακας μονοδιάστατος με ακέραια στοιχεία. Θέλω παραλλαγή της Φυσαλίδας ώστε να ταξινομεί όλα τα στοιχεία (κατά αύξουσα ή φθίνουσα σειρά) ενώ θα αφήνει στις θέσεις τους τα στοιχεία που είναι πολλαπλάσια ενός αριθμού. Μια βοήθεια παρακαλώ καθώς δε μπορώ να σκεφτώ κάτι σχετικό.

[petrosp13]

Στην δομή επιλογής θα βάλεις κριτήριο να μην είναι πολλαπλάσιο του αριθμού
Και τα 2 στοιχεία που συγκρίνονται

[Λαμπράκης Μανώλης]

καλησπέρα σε όλους

κάπως περίεργη εκφώνηση...συμφωνώ με τον Πέτρο αλλά αν τα στοιχεία πχ είναι εναλλάξ πολλαπλάσια του αριθμού και μη, πως θα γίνει ??

αντιγραφή σε νέο πίνακα ίσως, αλλά και πάλι πως θα δημιουργηθεί ο αρχικός πίνακας ??

δύσκολούτσικο..έχουμε έξτρα πληροφορίες??

[nikolasmer]

καλησπέρα σε όλους

κάπως περίεργη εκφώνηση...συμφωνώ με τον Πέτρο αλλά αν τα στοιχεία πχ είναι εναλλάξ πολλαπλάσια του αριθμού και μη, πως θα γίνει ??

αντιγραφή σε νέο πίνακα ίσως, αλλά και πάλι πως θα δημιουργηθεί ο αρχικός πίνακας ??

δύσκολούτσικο..έχουμε έξτρα πληροφορίες??

Αντιγράφω από μια άσκηση που έπεσε στα χέρια μου...προσπαθώ να φτιάξω παραλλαγή άσκηση με κενά.
Κατασκευάστε τη συνάρτηση sort_but_aA_words(a) η οποία ταξινομεί αλφαβητικά τα αλφαριθμητικά (string) που περιέχονται στη λίστα a, ενώ αφήνει στις θέσεις τους τα στοιχεία των οποίων ο πρώτος χαρακτήρας είναι 'a' ή 'A'.
Για παράδειγμα, ο ακόλουθος κώδικας Python:

ls = ['cat', 'bat', 'all', 'bin', 'fat', 'Add'] 
sort_but_aA_words(ls) 
for word in ls: 
 print(ls + ' ')

θα πρέπει να εμφανίζει: bat bin all cat fat Add

[evry]

Δεν θα έχεις j και j-1.
Θα υλοποιήσεις κανονικά την φυσαλίδα με διπλό while όμως και θα έχεις δυο δείκτες pred και next.
Κάθε φορά θα συγκρίνεις τα A[pred] με A[next] .
Η ιδέα είναι η εξής:
Ξεκινάς από κάτω προς τα πάνω μέχρι να βρεις μη πολλαπλάσιο του αριθμού.
Εκεί είναι το pred
Μετά από εκεί και πάνω πας ως εξής:

Αν το A[next] είναι πολλαπλάσιο του αριθμού τότε 
       next=next+1
Αλλιώς  if φυσαλίδας
            
        Μετά την αντιμετάθεση μέσα στο if θέτεις και pred=next και next=next+1

κλπ
Νομίζω ότι αυτό είναι το πιο απλό πάνω στον πίνακα.

[ssimaiof]

Και το δικό μου σκεπτικό είναι παρόμοιο με του evry. Μέσα στη διπλή επανάληψη ξεκινώντας από τη j θέση και πηγαίνοντας προς τα επάνω (φυσαλίδα) βρίσκεις τη θέση Κ του 1ου στοιχείου που δεν ικανοποιεί τον περιορισμό (π.χ. δεν είναι πολλαπλάσιο κάποιου αριθμού). Ξεκινώντας από την Κ-1 θέση και πηγαίνοντας πάλι προς τα επάνω (φυσαλίδα) εντοπίζουμε την θέση Λ του επόμενου στοιχείου που δεν ικανοποιεί τον περιορισμό. Τελικά συγκρίνουμε τα στοιχεία στις θέσεις Κ, Λ για την ταξινόμηση.
Μια πρόχειρη λύση σε ΓΛΩΣΣΑ είναι η παρακάτω :

ΥΓ. Διορθώθηκε η ΑΝ στην 32η γραμμή (πρσθέθηκε έλεγχος και για την Κ θέση) κατόπιν παρατήρησης του "Λυρικό Δαιμόνιο".

! Ταξινόμηση πίνακα ακεραίων αφήνοντας στην αρχική τους θέση
! τα πολλαπλάσια του Ω
ΠΡΟΓΡΑΜΜΑ Μερική_Ταξινόμηση
ΣΤΑΘΕΡΕΣ
  Ν = 10
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Π[Ν], i, j, Κ, Λ, Ω, Temp
ΑΡΧΗ
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ 'Πίνακας[', i, '] :  '
    ΔΙΑΒΑΣΕ Π[i] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ 'Ποιού αριθμού τα πολλαπλάσια να εξαιρεθούν :  '
  ΔΙΑΒΑΣΕ Ω

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν
    ΓΙΑ j ΑΠΟ Ν ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1

      ! Βρες τη θέση Κ του 1ου στοιχείου που δεν είναι πολλαπλάσιο
      Κ <- j
      ΟΣΟ Π[Κ] mod Ω = 0 ΚΑΙ Κ > 2 ΕΠΑΝΑΛΑΒΕ
        Κ <- Κ - 1
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

      ! Βρες τη θέση Λ του 2ου στοιχείου που δεν είναι πολλαπλάσιο
      Λ <- Κ - 1
      ΟΣΟ Π[Λ] mod Ω = 0 ΚΑΙ Λ > 1 ΕΠΑΝΑΛΑΒΕ
        Λ <- Λ - 1
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

      ΑΝ Π[Κ] mod Ω <> 0 ΚΑΙ Π[Λ] mod Ω <> 0 ΤΟΤΕ
        ΑΝ Π[Κ] < Π[Λ] ΤΟΤΕ
          Temp <- Π[Κ] 
          Π[Κ] <- Π[Λ] 
          Π[Λ] <- Temp
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ Π[i], '  '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

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

Να δώσω και εγώ τη δικιά μου λύση που δεν περιλαμβάνει επιπλέον εσωτερική επανάληψη.
Η λογική της είναι ότι στον αλγόριθμο της φυσαλίδας συγκρίνουμε το στοιχείο της θέση j με το προηγούμενο στοιχείο (συνήθως της θέσης j-1).
Εμείς δεν θέλουμε να ακουμπήσουμε τις θέσεις που είναι πολλαπλάσια του Ν που δίνεται.
Συνεπώς όταν η θέση του j είναι πολ/σιο του N μην κάνεις καμία σύγκριση.
Όταν όμως η θέση j είναι ΟΚ (δεν είναι πολ/σιο του Ν) αλλά η  προηγούμενη (j-1) είναι πολ/σιο του Ν τότε απλά συγκρινε με την πρόπροηγούμενη της θέση, δηλαδή την j-2.
Αυτό μπορούμε να το κάνουμε γιατί δεν παίζει 2 πολ/σια να είναι συνεχόμενα εκτός από όταν Ν=1.
Ομως τότε δεν έχουμε πρόβλημα γιατί δεν θα ισχύει η πρώτη συνθήκη γιατί για Ν = 1 όλες οι θέσεις είναι πολ/σια του 1.

Σημείωση : Μπορείτε να αλλάξετε τον κώδικα ώστε το ΑΝ να μην έχει τη αδιάφορη συνθήκη Ν <- Ν, αλλά το άφησα έτσι για να φαίνεται ο τρόπος σκέψης.
Σημείωση 2: Ο αλγόριθμος που έγραψα ταξινομεί τις θέσεις που δεν είναι πολλαπλάσια όχι τις τιμές... Για τις τιμές δεν νομίζω να μπορείς να αποφύγεις την εσωτερική επανάληψη.

ΠΡΟΓΡΑΜΜΑ ταξινομησηΣεΜηΠολλαπλασια
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: A[10], N, i, j, temp
ΑΡΧΗ
  ΔΙΑΒΑΣΕ N
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ A[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 10
    ΓΙΑ j ΑΠΟ 10 ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
      ΑΝ j mod N = 0 ΤΟΤΕ                                                  !φυγε
        N <- N
      ΑΛΛΙΩΣ_ΑΝ (j - 1) mod N = 0 ΤΟΤΕ!Εδω θα μπω μόνο αν η θέση j δεν ειναι πολλαπλάσιο αλλά η θέση j-1 είναι, άρα σύγκρινε αυτή που είναι 2 θέσεις απόσταση που είναι αδύνατο να είναι και αυτή πολλαπλάσιο
        ΑΝ j - 2 >= 1 ΤΟΤΕ   !ελεγχος οτι ειμαστε ακομα μεσα στα όρια του πίνακα
          ΑΝ A[j] < A[j - 2] ΤΟΤΕ
            temp <- A[j]
            A[j] <- A[j - 2]
            A[j - 2] <- temp
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΑΝ
      ΑΛΛΙΩΣ
        ΑΝ A[j] < A[j - 1] ΤΟΤΕ
          temp <- A[j]
          A[j] <- A[j - 1]
          A[j - 1] <- temp
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

[Anastasis13]

Οι δύο παραπάνω αλγόριθμοι δεν δουλεύουν πάντα σωστά. Δοκιμάστε ως αρχείο εισόδου να βάλετε στον πίνακα τους αριθμούς:
[11,2,2,2,2,2,2,2,2,3], Για K = 2 (Πολλαπλάσια του K).

Παραθέτω την λύση μου:


Αλγόριθμος μερική_ταξινόμηση
Δεδομένα // a, n, k //
! Βρίσκω την θέση με το πρώτο πολλαπλάσιο του k
x ← 0
Αρχή_επανάληψης
  x ← x + 1
Μέχρις_ότου a[ x ] mod k ≠ 0 ή x = n
! Βρίσκω την θέση με το τελευταίο πολλαπλάσιο του k
z ← n + 1
Αρχή_επανάληψης
  z ← z - 1
Μέχρις_ότου a[z] mod k ≠ 0 ή z = 1
! Ταξινομώ
Για i από 1 μέχρι z - x ! Θα χρειαστώ το πολύ z - x εξωτερικές επαναλήψεις
  y ← x ! Αποθηκεύω στην y κάθε φορά την θέση του πρώτου πολλαπλασίου του k
  Για j από x + 1 μέχρι z ! Συγκρίνω μέχρι τη θέση του τελευταίου πολλαπλασίου του k
    Αν a[j] mod k ≠ 0 τότε
      Αν a[y] > a[j] τότε Αντιμετάθεσε a[y], a[j]
      y ← j
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
Αποτελέσματα // a //
Τέλος

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

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

Oι παραπάνω αλγόριθμοι που προτάθηκαν, σε κάθε εξωτερικό βήμα της επανάληψης θα πρέπει να ξαναψάχνουν να βρίσκουν σε ποια θέση είναι τα πολλαπλάσια του Κ. Αφού πολλαπλάσια του Κ αντιμετατίθενται μόνο πολλαπλάσια του Κ, αν αποθηκεύσω σε ποιες θέσεις είναι τα πολλαπλάσια του Κ σε έναν πίνακα Θ με ένα πέρασμα πριν από την ταξινόμηση. Στη συνέχεια αντί να συγκρίνω τις διαδοχικές θέσεις j με j-1, θα συγκρίνω τις διαδοχικές θέσεις που έχουν πολ/σια, δηλαδή τις Θ[j] με Θ[j-1].

Ο κώδικας που κάνει το παραπάνω φαίνεται εδώ:

ΠΡΟΓΡΑΜΜΑ ταξινομωΜονοΠολλαπλασιαΚ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: i, A[10], K, πλ_πολλαπλασια, Θ[10], j, temp
ΑΡΧΗ
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ A[i] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΔΙΑΒΑΣΕ K

  πλ_πολλαπλασια <- 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10    !Αποθηκεύω τις θέσεις των πολ/σιων του Κ στον πίνακα Θ
    ΑΝ A[i] mod K = 0 ΤΟΤΕ
      πλ_πολλαπλασια <- πλ_πολλαπλασια + 1
      Θ[πλ_πολλαπλασια] <- i
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ πλ_πολλαπλασια
    ΓΙΑ j ΑΠΟ πλ_πολλαπλασια ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
            ! Για να εντοπίσω τις θέσεις που συγκρίνω συμβουλεύομαι τον πίνακα Θ
      ΑΝ A[Θ[j]] > A[Θ[j - 1]] ΤΟΤΕ
        temp <- A[Θ[j - 1]] 
        A[Θ[j - 1]] <- A[Θ[j]] 
        A[Θ[j]] <- temp
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΡΑΨΕ A[i] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

[Anastasis13]

Καταρχήν δεν ταξινομείς τα πολλαπλάσια, ταξινομείς τις θέσεις που δεν είναι πολλαπλάσια κάποιου αριθμού. Επίσης σκέψου ο πίνακας να είχε 1 εκατομμύριο θέσεις, θα δημιουργούσες άλλον έναν ίδιου μεγέθους ; Δεν νομίζω ότι αξίζει παραπάνω η λύση σου, επειδή το Space complexity είναι O(n).

[George Eco]

Η παρακάτω λύση δοκιμάστηκε σε αύξουσα σειρά με δεδομένα:
Ν = 7
Πίνακας: 3,21,2,18,14,1,9
και ζητούμενο 7
με αναμενόμενο αποτέλεσμα το 1,21,2,3,14,9,18 και δούλεψε σωστά.
Δεν είμαι πολύ περήφανος για τη λύση, σίγουρα θα υπάρχει καλύτερη αλλά είναι περασμένες 1 και δε μου έρχεται κάτι καλύτερο κατά νου.
Όσοι πιστοί προσέλθετε να το βελτιστοποιήσουμε, αν χρειάζεται.

ΠΡΟΓΡΑΜΜΑ ΤΕΑΔΠ
ΣΤΑΘΕΡΕΣ
  Ν = 7
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ι, κ, λ, ξ, Α[Ν], βα, ζ
  ΛΟΓΙΚΕΣ: flag
ΑΡΧΗ
! Ταξινόμηση Ευθείας Ανταλλαγής Δίχως Πολλαπλάσια.
! Δέχεται πίνακα Ν ακεράιων στοιχείων και μια ζητούμενη τιμή (ζ)
! Επιστρέφει ταξινομξημένο το πίνακα, δίχως να αγγίξει τις θέσεις
! των πολλαπλασίων του ζ.
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ 'Παρακαλώ δώστε το ', ι, ' ο στοιχείο του πίνακα: '
    ΔΙΑΒΑΣΕ Α[ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Παρακαλώ δώστε τώρα τον αριθμό που πολλαπλάσιά του '
  ΓΡΑΨΕ 'δε θα τα αλλάξουμε θέση κατά τη ταξινόμηση: '
  ΔΙΑΒΑΣΕ ζ
  ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
    κ <- Ν
    ΟΣΟ κ >= ι ΕΠΑΝΑΛΑΒΕ
      ΑΝ Α[κ] mod ζ <> 0 ΤΟΤΕ
        λ <- 1
        flag <- ΨΕΥΔΗΣ
        ξ <- κ
        ΟΣΟ flag = ΨΕΥΔΗΣ ΚΑΙ ξ - λ >= 1 ΕΠΑΝΑΛΑΒΕ
          ΑΝ Α[ξ - λ] mod ζ <> 0 ΤΟΤΕ
            flag <- ΑΛΗΘΗΣ
            ΑΝ Α[ξ - λ] > Α[ξ] ΤΟΤΕ
                βα <- Α[ξ - λ]
                Α[ξ - λ] <- Α[ξ]
                Α[ξ] <- βα
            ΤΕΛΟΣ_ΑΝ
            ξ <- ξ - λ + 1
          ΑΛΛΙΩΣ
            λ <- λ + 1
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΑΝ
      κ <- κ - 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ Α[ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

[alkisg]

Ας πούμε ότι μιλάμε για πολλαπλάσια του 3.
Αν κάνετε μια συνάρτηση που μετατρέπει τους δείκτες:
1, 2, *, 3, 4, *, 5, 6, *, 7, 8
σε:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
δηλαδή:
f(3) = 4
f(7) = 10

Τότε μπορεί να γίνει κανονικότατη ταξινόμηση φυσαλίδας με δύο ΓΙΑ (μόνο 8 επαναλήψεις, όχι 11), και όπου χρησιμοποιείται Πίνακας[k] να αλλαχθεί σε Πίνακας[f(k)].

Έτσι δεν αλλάζει ούτε η πολυπλοκότητα του χρόνου ούτε του χώρου.
Το αν η λύση αυτή είναι πιο εύκολη ή πιο δύσκολη είναι υπό συζήτηση! 
Έχει όμως μια γενικότητα, οποιαδήποτε συνάρτηση μετασχηματισμού θέσης μπορεί να εφαρμοστεί σε οποιονδήποτε αλγόριθμο.

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

Καταρχήν δεν ταξινομείς τα πολλαπλάσια, ταξινομείς τις θέσεις που δεν είναι πολλαπλάσια κάποιου αριθμού. Επίσης σκέψου ο πίνακας να είχε 1 εκατομμύριο θέσεις, θα δημιουργούσες άλλον έναν ίδιου μεγέθους ; Δεν νομίζω ότι αξίζει παραπάνω η λύση σου, επειδή το Space complexity είναι O(n).

O αλγόριθμος που προτείνω έχει Ο(n) Space Complexity, αλλά όποιον αλγόριθμο και να προτείνεις θα έχει Ο(n) γιατί έχεις ήδη έναν πίνακα n θέσεων και πρέπει να επισκεφτείς όλες τις θέσεις. Μάλλον εννοείς ότι έχει 2*n + O(1) αντί για n + O(1).
 
Μάλλον όμως δεν εκτιμάς ότι έχεις μεγάλο όφελος σε ταχύτητα, γιατί είναι κλασσική περίπτωση trade-off χώρου-χρόνου. Αυτό γιατί οι προηγούμενοι αλγόριθμοι επισκέπτονται όλες τις θέσεις είτε για αντιμετάθεση, είτε για να ελέγξουν εάν το περιεχόμενο είναι πολλαπλάσιο άρα έχουν την κλασσική πολυπλοκότητα του BubbleSort δηλαδή Ο(n^2), ενώ ο αλγόριθμος που προτείνω εάν έχουμε m πολλαπλάσια (m<=n και όσο πιο μεγάλος ο αριθμός, τόσο μικραίνει η πιθανότητα να πετύχεις πολλαπλάσιο) θα έχει πολυπλοκότητα O(m^2+n) το οποίο είναι μεγάλο όφελος όσο μειώνονται τα πολλαπλάσια που βρίσκονται στον πίνακα.

[George Eco]

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

[Anastasis13]

Σχετικά με το θέμα της ταξινόμησης, δοκιμάστε σε ΓΛΩΣΣΑ να υλοποιήσετε το παρακάτω:

Να γραφεί πρόγραμμα/αλγόριθμος σε ΓΛΩΣΣΑ/Ψευδογλώσσα, ο οποίος να διαβάζει αριθμούς μέχρι να δοθεί το 0. Ύστερα να διαβάζει έναν αριθμό N και να εμφανίζει τους N μεγαλύτερους αριθμούς από αυτούς που διάβασε. Θεωρείστε ότι οι αριθμοί που δίνονται είναι ακέραιοι θετικοί στο διάστημα [1,9]. Επίσης θεωρείστε ότι το N θα είναι πάντα μικρότερο ή ίσο από τους
αριθμούς που διαβάζονται.

Περιορισμοί:

Πολυπολοκότητα χώρου: O(1)

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

Φαντάζομαι η πιο απλή λύση είναι με τη λογική του 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.
Η φράση "το πολύ" ουσιαστικά σου ορίζει το μέγεθος του πίνακα. Έχει πέσει πρόσφατα σχετικά παρόμοιο θέμα Πανελληνίων.