Ταξινόμηση με Εισαγωγή - Εκπαιδευτικό Πρόγραμμα

Θεωρία Αλγορίθμου

Τι είναι η Ταξινόμηση με Εισαγωγή;

Η Ταξινόμηση με Εισαγωγή (Insertion Sort) είναι ένας αλγόριθμος που δουλεύει όπως ταξινομούμε τα χαρτιά στο χέρι μας. Παίρνουμε κάθε στοιχείο και το τοποθετούμε στη σωστή θέση ανάμεσα στα ήδη ταξινομημένα.

Ο Αλγόριθμος σε ΓΛΩΣΣΑ

ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 50
  j ← i
  flag ← ΑΛΗΘΗΣ
  ΟΣΟ j > 1 ΚΑΙ flag = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ
    ΑΝ Π[j-1] > Π[j] ΤΟΤΕ
      temp ← Π[j-1]
      Π[j-1] ← Π[j]
      Π[j] ← temp
      j ← j - 1
    ΑΛΛΙΩΣ
      flag ← ΨΕΥΔΗΣ
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Πώς λειτουργεί βήμα-βήμα;

1. Εξωτερική Επανάληψη (i από 2 μέχρι 50)

Ξεκινάμε από το 2ο στοιχείο (το 1ο θεωρείται ήδη ταξινομημένο). Για κάθε i, θα εισάγουμε το στοιχείο Π[i] στη σωστή θέση.

2. Αρχικοποίηση j και flag

Θέτουμε j ← i και flag ← ΑΛΗΘΗΣ. Το flag μας βοηθά να σταματήσουμε όταν βρούμε τη σωστή θέση.

3. Εσωτερική Επανάληψη (ΟΣΟ)

Συγκρίνουμε το Π[j] με το Π[j-1]. Αν το Π[j-1] > Π[j], τα ανταλλάσσουμε και συνεχίζουμε προς τα αριστερά (j ← j-1). Αλλιώς, σταματάμε (flag ← ΨΕΥΔΗΣ).

4. Ανταλλαγή με temp

Χρησιμοποιούμε προσωρινή μεταβλητή temp για να ανταλλάξουμε τα δύο στοιχεία χωρίς να χάσουμε δεδομένα.

Παράδειγμα: Π = [5, 2, 4, 1, 3]

i=2: Εισαγωγή του 2 → [2, 5, 4, 1, 3]

i=3: Εισαγωγή του 4 → [2, 4, 5, 1, 3]

i=4: Εισαγωγή του 1 → [1, 2, 4, 5, 3]

i=5: Εισαγωγή του 3 → [1, 2, 3, 4, 5] ✅

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

Οπτικοποίηση Αλγορίθμου