Πληροφορική Γ' Λυκείου

1) Συγχώνευση ταξινομημένων πινάκων χωρίς χρήση ταξινόμησης

i <— 1
j <— 1
k <— 1
Όσο (i <= Μ) και (j <= N) επανέλαβε
Αν (A[i] < B[j]) τότε
Γ[k] <— A[i]
i <— i + 1
Αλλιώς
Γ[k] <— B[j]
j <— j + 1
Τέλος_Αν
k <— k + 1
Τέλος_Επανάληψης
Αν (i > M) τότε
Για z από j μέχρι Ν
Γ[k] <— B[z]
k <— k + 1
Τέλος_Επανάληψης
Αλλιώς
Για z από i μέχρι M
Γ[k] <— A[z]
k <— k + 1
Τέλος_Επανάληψης
Τέλος_Αν

Θεωρία – Είδη συγχώνευσης

Απλή Συγχώνευση (χωρίς ταξινόμηση)

• Τοποθετούμε διαδοχικά τα στοιχεία του πρώτου πίνακα στον νέο.
• Συνεχίζουμε με τα στοιχεία του δεύτερου πίνακα.
  📌 Η σειρά εξαρτάται από την αρχική σειρά των πινάκων.
  Χρήσιμη όταν η σειρά δεν έχει σημασία.

Συγχώνευση Ταξινομημένων Πινάκων (Merge)

• Οι πίνακες είναι ήδη ταξινομημένοι (συνήθως σε αύξουσα σειρά).
• Συγκρίνουμε το πρώτο στοιχείο κάθε πίνακα και εισάγουμε το μικρότερο στον νέο πίνακα.
• Επαναλαμβάνουμε μέχρι να εξαντληθούν όλα τα στοιχεία.
  📌 Αυτός ο τρόπος είναι και η βάση του Merge Sort.

Συγχώνευση με Κριτήρια

• Επιλέγουμε μόνο τα στοιχεία που πληρούν μια προϋπόθεση (π.χ. θετικοί αριθμοί, τιμές > 50).
• Η μέθοδος μπορεί να είναι είτε απλή είτε ταξινομημένη.

Παρατηρήσεις – Συμβουλές

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

Συγχώνευση Πινάκων – Εισαγωγή

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

• Σειρά ταξινόμησης (αν οι αρχικοί πίνακες ήταν ταξινομημένοι, ο νέος παραμένει ταξινομημένος).
• Μοναδικότητα στοιχείων (αποφυγή διπλοεγγραφών).
• Συγχώνευση κατά κριτήριο (π.χ. συγχώνευση μόνο συγκεκριμένων τιμών).

Η συγχώνευση είναι ιδιαίτερα χρήσιμη σε εφαρμογές όπου:

• Συνδυάζουμε δεδομένα από διαφορετικές πηγές.
• Θέλουμε να ενώσουμε δύο ταξινομημένες λίστες σε μία ταξινομημένη.
• Ετοιμάζουμε δεδομένα για περαιτέρω επεξεργασία (αναζήτηση, στατιστικά).

Αφού ολοκληρώσετε το Quiz μπορείτε να προχωρήσετε στις ασκήσεις προς λύση!

Για την επίλυση τους θα χρειαστείτε τον Διερμηνευτή της γλώσσας:

https://www.gloeditor.gr/editor

Καλή Επιτυχία!

Ταξινόμηση σε Μονοδιάστατους Πίνακες

1. Ταξινόμηση πίνακα σε αύξουσα σειρά με τη μέθοδο της φυσαλίδας

Για i από 2 μέχρι Ν
Για j από N μέχρι i με_βήμα -1
Αν (Α[j] < Α[j-1]) τότε
tmp <-- Α[j]
Α[j] <-- Α[j-1]
Α[j-1] <-- tmp
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης

Για φθίνουσα ταξινόμηση αλλάζει μόνο η σύγκριση:

Αν (Α[j] > Α[j-1]) τότε
2. Παραλλαγή της φυσαλίδας που σταματά όταν ο πίνακας είναι ήδη ταξινομημένος

Αρχή_Επανάληψης
πλ <-- 0     ! πλήθος αντιμεταθέσεων
i <— 2
Για j από N μέχρι i με_βήμα -1
Αν (Α[j] < Α[j-1]) τότε
πλ <-- πλ + 1
tmp <-- Α[j]
Α[j] <-- Α[j-1]
Α[j-1] <-- tmp
Τέλος_Αν
Τέλος_Επανάληψης
i <-- i + 1
Μέχρις_Ότου (i > N Ή πλ = 0)

3. Ταξινόμηση πίνακα σε αύξουσα σειρά με τη μέθοδο της επιλογής

Για i από 1 μέχρι Ν - 1
min <— A[i]
θmin <— i
Για j από i+1 μέχρι Ν
Αν (Α[j] < min) τότε
min <— A[j]
θmin <— j
Τέλος_ΑΝ
Τέλος_Επανάληψης
tmp <-- Α[θmin]
Α[θmin] <-- Α[i]
Α[i] <-- tmp
Τέλος_Επανάληψης
4. Ταξινόμηση πίνακα σε αύξουσα σειρά με τη μέθοδο της παρεμβολής

Για i από 2 μέχρι Ν

key <— A[i]

stop <— Ψευδής

j <— i - 1

Όσο (j >= 1) και (stop = Ψευδής) επανάλαβε

Αν (key < A[j]) τότε

A[j+1] <— A[j]

j <— j - 1

Αλλιώς

stop <— Αληθής

Τέλος_Αν

Τέλος_Επανάληψης

A[j+1] <— key

Τέλος_Επανάληψης

 Ταξινόμηση σε Δισδιάστατους Πίνακες

1. Ταξινόμηση δισδιάστατου πίνακα σε αύξουσα σειρά με φυσαλίδα

Βήμα α – Μεταφορά στοιχείων σε μονοδιάστατο πίνακα

κ <-- 1

Για i από 1 μέχρι Μ

Για j από 1 μέχρι N

Β[κ] <-- Α[i,j]

κ <-- κ + 1

Τέλος_Επανάληψης

Τέλος_Επανάληψης

Βήμα β – Ταξινόμηση του μονοδιάστατου πίνακα Β

Για i από 2 μέχρι Μ*Ν

Για j από Μ*Ν μέχρι i με_βήμα -1

Αν (Β[j] < Β[j-1]) τότε

tmp <-- Β[j]

Β[j] <-- Β[j-1]

Β[j-1] <-- tmp

Τέλος_Αν

Τέλος_Επανάληψης

Τέλος_Επανάληψης

Βήμα γ – Μεταφορά πίσω στον δισδιάστατο πίνακα Α

κ <-- 1

Για i από 1 μέχρι Μ

Για j από 1 μέχρι N

Α[i,j] <-- Β[κ]

κ <-- κ + 1

Τέλος_Επανάληψης

Τέλος_Επανάληψης

Ταξινόμηση Φυσαλίδας (Bubble Sort)

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

• Βασική Ιδέα:
  • Συγκρίνουμε συνεχώς διπλανά στοιχεία.
  • Αν είναι σε λάθος σειρά, τα ανταλλάσσουμε.
  • Σε κάθε πέρασμα, το επόμενο μεγαλύτερο στοιχείο τοποθετείται στη θέση του.
• Σταματά: Όταν δεν χρειάζονται άλλες ανταλλαγές.
• Πολυπλοκότητα:
  • Χειρότερη περίπτωση: O(n²).
  • Χρειάζεται δύο εμφωλευμένους βρόχους.
• Πλεονεκτήματα: Απλή στην κατανόηση.
• Μειονεκτήματα: Αργή για μεγάλα σύνολα δεδομένων.

Ταξινόμηση Επιλογής (Selection Sort)

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

• Βασική Ιδέα:
  • Εντοπίζουμε το ελάχιστο στοιχείο.
  • Το ανταλλάσσουμε με το στοιχείο της τρέχουσας θέσης.
• Μετακινήσεις: Ελάχιστες, καθώς αλλάζουμε θέση μόνο στο στοιχείο που είναι το ελάχιστο.
• Πολυπλοκότητα:
  • O(n²) συγκρίσεις.
  • Δύο εμφωλευμένοι βρόχοι: ένας για την επιλογή, ένας για τη σύγκριση.
• Πλεονεκτήματα: Λίγες μετακινήσεις στοιχείων.
• Μειονεκτήματα: Δεν είναι σταθερή μέθοδος (ίσου μεγέθους στοιχεία μπορεί να αλλάξουν σειρά).

Ταξινόμηση Εισαγωγής (Insertion Sort)

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

• Βασική Ιδέα:
  • Ξεκινάμε από το δεύτερο στοιχείο και το συγκρίνουμε με τα προηγούμενα.
  • Το εισάγουμε στη σωστή θέση μετακινώντας τα υπόλοιπα.
• Αποδοτικότητα:
  • Πολύ καλή για μικρά ή ήδη σχεδόν ταξινομημένα σύνολα.
  • Στην καλύτερη περίπτωση (ήδη ταξινομημένος πίνακας): O(n).
  • Στη χειρότερη περίπτωση: O(n²).
• Πλεονεκτήματα: Σταθερή μέθοδος (δεν αλλάζει τη σειρά ισοδύναμων στοιχείων).
• Μειονεκτήματα: Αργή για πολύ μεγάλα και αταξινόμητα σύνολα.

Εισαγωγή στην Ταξινόμηση

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

Στην Πληροφορική, υπάρχουν πολλές μέθοδοι ταξινόμησης, καθεμία με τα δικά της πλεονεκτήματα και μειονεκτήματα. Στο μάθημα, επικεντρωνόμαστε σε τρεις βασικές μεθόδους:

• Ταξινόμηση Φυσαλίδας (Bubble Sort)
• Ταξινόμηση Επιλογής (Selection Sort)
• Ταξινόμηση Εισαγωγής (Insertion Sort)

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

Αφού ολοκληρώσετε το Quiz μπορείτε να προχωρήσετε στις ασκήσεις προς λύση!

Για την επίλυση τους θα χρειαστείτε τον Διερμηνευτή της γλώσσας:

https://www.gloeditor.gr/editor

Καλή Επιτυχία!

Αναζήτηση σε Μονοδιάστατους Πίνακες

1) Σειριακή αναζήτηση της πρώτης εμφάνισης του στοιχείου key, και έξοδος από την αναζήτηση

toBrika <-- Ψευδής
i <-- 1
Όσο (i <= Ν) και (toBrika = Ψευδής) επανάλαβε
Αν (Α[i] = key) τότε
toBrika <-- Αληθής
θ <-- i
Αλλιώς
i <- i + 1
Τέλος_Αν
Τέλος_Επανάληψης
Αν (toBrika = Αληθής) τότε
Γράψε ‘Το στοιχείο’, key, ‘βρέθηκε στη θέση’, θ
Αλλιώς
Γράψε ‘Το στοιχείο’, key, ‘δεν υπάρχει στον πίνακα’
Τέλος_Αν

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

π <-- 0
Για i από 1 μέχρι Ν
Αν (Α[i] = key) τότε
Γράψε ‘Το στοιχείο’, key, ‘βρέθηκε στη θέση’, i
π <-- π + 1
Τέλος_Αν
Τέλος_Επανάληψης
Αν (π = 0) τότε
Γράψε ‘Το στοιχείο’, key, ‘δεν υπάρχει στον πίνακα’
Αλλιώς
Γράψε ‘Ο συνολικός αριθμός εμφανίσεων του στοιχείου’, key, ‘είναι’, π
Τέλος_Αν

3) Εύρεση όλων των εμφανίσεων του μεγαλύτερου στοιχείου πίνακα, και πλήθους αυτών.

max <-- Α[1]
Για i από 2 μέχρι Ν
Αν (Α[i] > max) τότε
max <-- Α[i]
Τέλος_Αν
Τέλος_Επανάληψης
Γράψε ‘Το μέγιστο στοιχείο είναι το‘, max, ‘και βρίσκεται στις θέσεις:’
π <-- 0
Για i από 1 μέχρι Ν
Αν (Α[i] = max) τότε
Γράψε i
π <-- π + 1
Τέλος_Αν
Τέλος_Επανάληψης
Γράψε ‘Ο συνολικός αριθμός εμφανίσεων του στοιχείου’, max, ‘είναι’, π
(Παρομοίως για εύρεση ελαχίστου)

4) Δυαδική αναζήτηση

αρχή <— 1

τέλος <— Ν

toBrika <— Ψευδής

Όσο (αρχή <= τέλος) και (toBrika = Ψευδής) επανέλαβε

μεσαίο <— (αρχή + τέλος) div 2

Αν (Α[μεσαίο] = key) τότε

toBrika <— Αληθής

θ <— μεσαίο

Αλλιώς_Αν (Α[μεσαίο] < key) τότε

αρχή <— μεσαίο + 1   Αλλιώς

τέλος <— μεσαίο – 1

Τέλος_Αν

Τέλος_Επανάληψης

Αν (toBrika = Αληθής) τότε

Γράψε ‘Το στοιχείο βρέθηκε στη θέση’, θ

Αλλιώς

Γράψε ‘Το στοιχείο δεν βρέθηκε’ Τέλος_Αν

Αναζήτηση σε Δισδιάστατους Πίνακες

1) Σειριακή αναζήτηση της πρώτης εμφάνισης του στοιχείου key, και έξοδος από την αναζήτηση

toBrika <-- Ψευδής
i <-- 1
Όσο (i <= Μ) και (toBrika = Ψευδής) επανάλαβε
j <— 1
Όσο (j <= N) και (toBrika = Ψευδής) επανάλαβε
Αν (Α[i,j] = key) τότε
toBrika <-- Αληθής
θγ <-- i
θσ <-- j
Τέλος_Αν
j <-- j + 1
Τέλος_Επανάληψης
i <-- i + 1
Τέλος_Επανάληψης
Αν (toBrika = Αληθής) τότε
Γράψε ‘Το στοιχείο’, key, ‘βρέθηκε στη γραμμή’, θγ, ‘και στη στήλη’, θσ
Αλλιώς
Γράψε ‘Το στοιχείο’, key, ‘δεν υπάρχει στον πίνακα’
Τέλος_Αν

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

π <-- 0
Για i από 1 μέχρι Μ
Για j από 1 μέχρι N
Αν (Α[i,j] = key) τότε
Γράψε ‘Το στοιχείο’, key, ‘βρέθηκε στη γραμμή’, i, ‘και στήλη’, j
π <-- π + 1
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης
Αν (π = 0) τότε
Γράψε ‘Το στοιχείο’, key, ‘δεν υπάρχει στον πίνακα’
Αλλιώς
Γράψε ‘Ο συνολικός αριθμός εμφανίσεων του στοιχείου’, key, ‘είναι’, π
Τέλος_Αν

3) Εύρεση όλων των εμφανίσεων του μεγαλύτερου στοιχείου πίνακα, και πλήθους αυτών.

max <-- Α[1,1]
Για i από 1 μέχρι M
Για j από 1 μέχρι N
Αν (Α[i,j] > max) τότε
max <-- Α[i,j]
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης
Γράψε ‘Το μέγιστο στοιχείο είναι το‘, max, ‘και βρίσκεται στις θέσεις:’
π <-- 0
Για i από 1 μέχρι Μ
Για j από 1 μέχρι N
Αν (Α[i] = max) τότε
Γράψε i, j
π <-- π + 1
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης
Γράψε ‘Ο συνολικός αριθμός εμφανίσεων του στοιχείου’, max, ‘είναι’, π
(Παρομοίως για εύρεση ελαχίστου)

1. Σειριακή Αναζήτηση (Γραμμική)

Ορισμός

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

Βασικά χαρακτηριστικά

• Δεν απαιτεί ταξινόμηση του πίνακα.
• Λειτουργεί σε οποιονδήποτε πίνακα (ταξινομημένο ή μη).
• Εύκολη στην υλοποίηση.
• Μπορεί να τερματίσει νωρίτερα αν βρεθεί το στοιχείο (π.χ. με την εντολή ΔΙΑΚΟΠΗ στη ΓΛΩΣΣΑ).
• Χρήσιμη σε μικρούς πίνακες ή όταν η αναζήτηση γίνεται σπάνια.

Περιορισμοί

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

Παράδειγμα ψευδοκώδικα (ΓΛΩΣΣΑ):

Βρέθηκε ← ΨΕΥΔΗΣ
Για i από 1 μέχρι Ν
Αν Α[i] = x τότε
Βρέθηκε ← ΑΛΗΘΗΣ
Θέση ← i
ΔΙΑΚΟΠΗ
Τέλος_αν
Τέλος_επανάληψης

Αν Βρέθηκε τότε
Γράψε 'Το στοιχείο βρέθηκε στη θέση', Θέση
Αλλιώς
Γράψε 'Το στοιχείο δεν βρέθηκε'
Τέλος_αν

2. Δυαδική Αναζήτηση

Ορισμός

Η δυαδική αναζήτηση είναι πολύ πιο αποδοτική, αλλά εφαρμόζεται μόνο σε ταξινομημένους πίνακες. Η μέθοδος βασίζεται στην αρχή "διαίρει και βασίλευε":
Σε κάθε βήμα συγκρίνουμε το ζητούμενο στοιχείο με το μεσαίο του πίνακα:

• Αν είναι ίσο, βρήκαμε το στοιχείο.
• Αν είναι μικρότερο, συνεχίζουμε στο αριστερό μισό.
• Αν είναι μεγαλύτερο, συνεχίζουμε στο δεξί μισό.

Βασικά χαρακτηριστικά

• Απαιτεί ταξινομημένο πίνακα.
• Σε κάθε βήμα αποκλείεται το μισό των στοιχείων.
• Πολύ γρήγορη για μεγάλους πίνακες (χρόνος εκτέλεσης O(log n)).

Περιορισμοί

• Δεν μπορεί να εφαρμοστεί σε μη ταξινομημένους πίνακες.
• Η προετοιμασία (ταξινόμηση) μπορεί να είναι χρονοβόρα αν δεν είναι ήδη ταξινομημένος.

Παράδειγμα ψευδοκώδικα (ΓΛΩΣΣΑ):

Αρχή ← 1
Τέλος ← Ν
Βρέθηκε ← ΨΕΥΔΗΣ

Όσο Αρχή <= Τέλος και Βρέθηκε = ΨΕΥΔΗΣ επανάλαβε
Μέσος ← (Αρχή + Τέλος) DIV 2
Αν Α[Μέσος] = x τότε
Βρέθηκε ← ΑΛΗΘΗΣ
Θέση ← Μέσος
Αλλιώς_αν Α[Μέσος] < x τότε
Αρχή ← Μέσος + 1
Αλλιώς
Τέλος ← Μέσος - 1
Τέλος_αν
Τέλος_επανάληψης

Αν Βρέθηκε τότε
Γράψε 'Το στοιχείο βρέθηκε στη θέση', Θέση
Αλλιώς
Γράψε 'Το στοιχείο δεν βρέθηκε'
Τέλος_αν