Μέθοδοι ταξινόμησης

Author

Κώστας Κούδας

Published

May 13, 2026

# Καθαρισμός μνήμης R.
rm(list = ls())

Η παρούσα ενότητα είναι μια εργασία για το μάθημα Δομές Δεδομένων του τμήματος Πληροφορικής του Ιονίου Πανεπιστημίου. Σε αυτήν θα παρουσιαστούν κάποιες μέθοδοι ταξινόμησης λιστών απαρτιζόμενων από αριθμούς. Η παρουσίαση θα γίνει:

1 Selection Sort - Ταξονόμηση με επιλογή

Η ταξινόμηση με επιλογή λειτουργεί ως εξής:

Ας φανταστούμε ότι έχουμε ανακατεμένους αριθμούς. Ο αλγόριθμος Selection Sort κάνει τα εξής βήματα:

  1. Ψάχνει σε ΟΛΗ τη λίστα για να βρει το μικρότερο στοιχείο.

Ας ξεκινήσουμε με την αταξινόμητη λίστα \((4, 10, 3, 5, 1)\). Η μικρότερη λύση που εντοπίζουμε είναι η:

Εύρεση μικρότερου 🔎

(4, 10, 3, 5, [1])
  1. Το βάζει στην πρώτη θέση (ανταλλάσσοντάς το με ό,τι ήταν εκεί).

Εναλλάσουμε, δηλαδή, το \(1\) με το \(4\) της \((4, 10, 3, 5, 1)\):

Ανταλλαγή. Κατασκευή ημι-ταξινομημένης λίστας 🔄 

(1 | 10, 3, 5, 4)
  1. Τώρα ψάχνει στην ΥΠΟΛΟΙΠΗ λίστα για το μικρότερο στοιχείο της.
Εύρεση μικρότερου 🔎

(1 | 10, [3], 5, 4)
  1. Το βάζει στη δεύτερη θέση (πάλι με ανταλλαγή).

Εναλλάσουμε, δηλαδή, το \(3\) με το \(10\) της \((1, 10, 3, 5, 4)\):

Ανταλλαγή. Κατασκευή ημι-ταξινομημένης λίστας 🔄 

(1, 3 | 10, 5, 4)
  1. Συνεχίζει έτσι μέχρι να ταξινομηθούν όλα τα στοιχεία.

Εύρεση μικρότερου 🔎

(1, 3 | 10, [5], 4)

Ανταλλαγή. Κατασκευή ημι-ταξινομημένης λίστας 🔄

(1, 3, 5 | 10, 4)

Εύρεση μικρότερου 🔎

(1, 3, 5 | 10, [4])

Ανταλλαγή. Κατασκευή ημι-ταξινομημένης λίστας 🔄

(1, 3, 5 , 4 | 10)

Απομένει μόνο το 10, που είναι αυτομάτως στη σωστή θέση.

(1, 3, 5 , 4 | 10)

ΤΕΛΟΣ ⛔

TipΕν συντομία

Είναι σαν να ταξινομείς τραπουλόχαρτα επιλέγοντας κάθε φορά το μικρότερο στοιχείο που απομένει.

selectionSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας (πόσα στοιχεία έχει)
  n <- length(arr)
  
  # Ξεκινάμε ένα βρόχο που θα τρέξει n-1 φορές
  # (Δεν χρειάζεται να ελέγξουμε το τελευταίο στοιχείο γιατί θα είναι ήδη στη σωστή θέση)
  for (i in 1:(n-1)) {
    
    # Υποθέτουμε ότι το τρέχον στοιχείο (i) είναι το μικρότερο
    min_idx <- i
    
    # Ψάχνουμε στα υπόλοιπα στοιχεία (από i+1 μέχρι το τέλος)
    # για να βρούμε αν υπάρχει κάτι μικρότερο
    if (i < n) {  # Ελέγχουμε αν υπάρχουν ακόμα στοιχεία για σύγκριση
      for (j in (i+1):n) {
        # Αν βρούμε στοιχείο μικρότερο από το τρέχον "μικρότερο"
        if (arr[j] < arr[min_idx]) {
          # Ενημερώνουμε τη θέση του μικρότερου στοιχείου
          min_idx <- j
        }
      }
    }
    
    # Αν βρήκαμε κάποιο μικρότερο στοιχείο (min_idx άλλαξε)
    if (min_idx != i) {
      # Κάνουμε ανταλλαγή: το μικρότερο στοιχείο πηγαίνει στη θέση i
      temp <- arr[i]           # Αποθηκεύουμε προσωρινά το στοιχείο στη θέση i
      arr[i] <- arr[min_idx]   # Βάζουμε το μικρότερο στη θέση i
      arr[min_idx] <- temp     # Βάζουμε το προηγούμενο στοιχείο στη θέση του μικρότερου
    }
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα
test_array <- c(64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# SELECTION SORT
print(selectionSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

2 Insertion Sort - Ταξινόμηση με παρεμβολή

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

  1. Ξεκινάμε με το πρώτο στοιχείο αριστερά, το οποίο θεωρούμε προσορινώς ήδη «ταξινομημένο».

Ας ξεκινήσουμε πάλι με την αταξινόμητη λίστα \((4, 10, 3, 5, 1)\). Επιλέγουμε το πρώτο στοιχείο της ως χώρο «ταξινομημένης» περιοχής:

Ημι-ταξινομημένη λίστα 🌗

(4 | 10, 3, 5, 1)
  1. Παίρνουμε το επόμενο στοιχείο και το συγκρίνουμε με τα στοιχεία στο ταξινομημένο μέρος (αριστερά του).

Εν προκειμένω συγκρίνουμε το \(10\) με τα στοιχεία της \((4)\), δηλαδή μόνο με το \(4\).

Επιλογή 🔎

(4 | [10], 3, 5, 1)

Σύγκριση 🆚

4 < 10
  1. Αν είναι μικρότερο το 2ο στοιχείο, το παρεμβάλουμε στη σωστή θέση μέσα στο ταξινομημένο μέρος, μετακινώντας όλα τα μεγαλύτερα στοιχεία μία θέση δεξιά.

Αφού προέκυψε \(10>4\), δεν θα υπάρξει μετακίνηση. Απλά η ταξινομημένη περιοχή θα επεκταθεί.

Ημι-ταξινομημένη λίστα 🌗

(4, 10 | 3, 5, 1)
  1. Παίρνουμε το επόμενο στοιχείο και το συγκρίνουμε με τα στοιχεία στο ταξινομημένο μέρος (αριστερά του).

Εν προκειμένω συγκρίνουμε το \(10\) με τα στοιχεία της \((4)\), δηλαδή μόνο με το \(4\).

Επιλογή 🔎

(4, 10 | [3], 5, 1)

Σύγκριση 🆚

3 < 4 < 10
  1. Το παρεμβάλουμε στη σωστή θέση μέσα στο ταξινομημένο μέρος, μετακινώντας τα μεγαλύτερα στοιχεία προς τα δεξιά.

Αφού προέκυψε \(3<4<10\), θα μετακινηθούν τα στοιχεία της ταξινομημένης λίστας μία θέση δεξιά.

Ημι-ταξινομημένη λίστα 🌗

(3, 4, 10 | 5, 1)
  1. Συνεχίζουμε έτσι και με τα επόμενα στοιχεία, μέχρις εξαντλήσεως της λίστας.

Εν προκειμένω συγκρίνουμε το \(10\) με τα στοιχεία της \((4)\), δηλαδή μόνο με το \(4\).

Επιλογή 🔎

(3, 4, 10 | [5], 1)

Σύγκριση 🆚

3 < 4 < 5 < 10

Ημι-ταξινομημένη λίστα 🌗

(3, 4, 5, 10 | 1)

Επιλογή 🔎

(3, 4, 5, 10 | [1])

Σύγκριση 🆚

1 < 3 < 4 < 5 < 10

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 4, 5, 10 | )

Ταξινομημένη λίστα 🌕

(1, 3, 4, 5, 10 )

ΤΕΛΟΣ ⛔
TipΕν συντομία

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

insertionSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Ξεκινάμε από το δεύτερο στοιχείο (θέση 2)
  # γιατί το πρώτο θεωρείται ήδη "ταξινομημένο"
  for (i in 2:n) {
    
    # Κρατάμε το τρέχον στοιχείο που θέλουμε να παρεμβάλουμε
    key <- arr[i]
    
    # Ξεκινάμε από τη θέση αριστερά του τρέχοντος στοιχείου
    j <- i - 1
    
    # Μετακινούμε όλα τα στοιχεία που είναι μεγαλύτερα από το key
    # μία θέση δεξιά, για να κάνουμε χώρο για το key
    while (j > 0 && arr[j] > key) {
      # Μετακινούμε το στοιχείο μία θέση δεξιά
      arr[j + 1] <- arr[j]
      # Προχωράμε στο προηγούμενο στοιχείο (αριστερά)
      j <- j - 1
    }
    
    # Όταν βρούμε τη σωστή θέση (ή φτάσουμε στην αρχή)
    # βάζουμε το key στη θέση j+1
    arr[j + 1] <- key
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# INSERTION SORT
print(insertionSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

3 Shell Sort - Ταξινόμηση παρεμβολής με φθίνοντα διαστήματα

Η Shell Sort είναι μια βελτιωμένη έκδοση της Insertion Sort:

  1. Αντί να συγκρίνουμε μόνο γειτονικά στοιχεία, συγκρίνουμε στοιχεία που απέχουν μια συγκεκριμένη απόσταση (gap\(<\frac{n}{3}\), όπου \(n\) το πλήθος των προς ταξινόμισιν αριθμών).
  2. Ξεκινάμε με μεγάλο gap και το μικραίνουμε σταδιακά.
  3. Για κάθε διάστημα, εφαρμόζουμε Insertion Sort στα στοιχεία που απέχουν αυτό το gap.
  4. Όταν το gap γίνει 1, κάνουμε μια τελική Insertion Sort.
TipΕν συντομία

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

Ας ξεκινήσουμε πάλι με την \((4, 10, 3, 5, 1)\). Δεδομένου ότι αυτή έχει \(5\) στοιχεία, έχουμε ότι το αρχικό gap θα είναι \(\operatorname{floor}\left(\frac{5}{2}\right)=2\), όπερ σημαίνει ότι συγκρίνουμε τα στοιχεία που απέχουν \(2\) θέσεις. Δηλαδή έχουμε προς σύγκριση τις δύο υπο-λίστες:

\[ L_1=(4, 𖤓, 3, 𖤓, 1) \text{ και } L_2=(𖤓, 10, 𖤓, 5, 𖤓) \]

Ξεκινάμε ταξινομώντας με Insertion Sort την κάθε μία λίστα \(L_1\), \(L_2\):

Ημι-ταξινομημένη λίστα 🌗

L1=(4 | 𖤓, 3, 𖤓, 1)

Επιλογή 🔎

L1=(4 | 𖤓, [3], 𖤓, 1)

Σύγκριση 🆚

4 > 3

Ημι-ταξινομημένη λίστα 🌗

L1=(3, 𖤓, 4 | 𖤓, 1)

Επιλογή 🔎

L1=(3, 𖤓, 4 | 𖤓, [1])

Σύγκριση 🆚

1 < 3 < 4

Ημι-ταξινομημένη λίστα 🌗

L1=(1, 𖤓, 3, 𖤓, 4)

Ημι-ταξινομημένη λίστα 🌗

L2=(𖤓, 10 | 𖤓, 5, 𖤓)

Επιλογή 🔎

L2=(𖤓, 10 | 𖤓, [5], 𖤓)

Σύγκριση 🆚

10 > 5

Ημι-ταξινομημένη λίστα 🌗

L2=(𖤓, 5, 𖤓, 10, 𖤓)

Συνδυάζοντας τα δύο αποτελέσματα έχουμε την ημι-ταξινομημένη λίστα:

\[ L= (1, 5, 3, 10, 4) \]

Στο επόμενο βήμα μειώνουμε το gap στο μισό, ήτοι γίνεται \(\operatorname{floor}\left(\frac{2}{1}\right)=1\). Αυτό σημαίνει ότι η λίστα, της οποίας τα στοιχεία θα ταξινομηθούν μέσω Insertion Sort, προκύπτει από τα στοιχεία της \(L\) που απέχουν μία θέση. Προφανώς αυτή είναι η ίδια η \(L\). Έχουμε, λοιπόν:

Ημι-ταξινομημένη λίστα 🌗

(1 | 5, 3, 10, 4)

Επιλογή 🔎

(1 | [5], 3, 10, 4)

Σύγκριση 🆚

1 < 5

Ημι-ταξινομημένη λίστα 🌗

(1, 5 | 3, 10, 4)

Επιλογή 🔎

(1, 5 | [3], 10, 4)

Σύγκριση 🆚

1 < 3 < 5

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 5 | 10, 4)

Επιλογή 🔎

(1, 3, 5 | [10], 4)

Σύγκριση 🆚

5 < 10

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 5, 10 | 4)

Επιλογή 🔎

(1, 3, 5, 10 | [4])

Σύγκριση 🆚

3 < 4 < 5

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 4, 5, 10)

ΤΕΛΟΣ ⛔

shellSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Ξεκινάμε με διάστημα ίσο με το μισό του μήκους της λίστας
  gap <- floor(n / 2)
  
  # Συνεχίζουμε όσο το διάστημα είναι μεγαλύτερο από 0
  while (gap > 0) {
    
    # Για κάθε στοιχείο από τη θέση gap μέχρι το τέλος
    for (i in (gap + 1):n) {
      
      # Κρατάμε το τρέχον στοιχείο που θέλουμε να παρεμβάλουμε
      temp <- arr[i]
      
      # Ξεκινάμε από τη θέση i
      j <- i
      
      # Μετακινούμε τα στοιχεία που απέχουν gap θέσεις και είναι
      # μεγαλύτερα από το temp, μία θέση δεξιά
      while (j > gap && arr[j - gap] > temp) {
        # Μετακίνηση του στοιχείου
        arr[j] <- arr[j - gap]
        # Προχωράμε πίσω κατά gap θέσεις
        j <- j - gap
      }
      
      # Βάζουμε το temp στη σωστή θέση
      arr[j] <- temp
    }
    
    # Μειώνουμε το διάστημα στο μισό (ακέραιη διαίρεση)
    gap <- floor(gap / 2)
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# SHELL SORT
print(shellSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

Αυτή η ακολουθία υπολογίζεται με τον αναδρομικό τύπο: gap = 3*gap + 1. Δηλαδή έχουμε gap\(=\frac{3^k-1}{2}\), όπου φυσικά αρχίζουμε με το μεγαλύτερο gap, όπως πριν.

Ας ξεκινήσουμε και αυτή τη φορά με την \((4, 10, 3, 5, 1)\). Δεδομένου ότι αυτή έχει \(5\) στοιχεία, πρέπει να βρούμε το μεγαλύτερο gap από την ακολουθία Knuth που είναι μικρότερο από το \(5\). Έχουμε, δηλαδή, gap\(=4\), όπερ σημαίνει ότι συγκρίνουμε τα στοιχεία που απέχουν \(4\) θέσεις.

Όπως και στην προηγούμενη εκδοχή της Shell Sort, έτσι κι εδώ θα εφαρμόσουμε Insertion Sort σε κάποιες υπο-λίστε της \((4, 10, 3, 5, 1)\). Συγκεκριμένα:

\[ L_1=(4, 𖤓, 𖤓, 𖤓, 1) \]

\[ L_2=(𖤓, 10, 𖤓, 𖤓, 𖤓) \]

\[ L_3=(𖤓, 𖤓, 3, 𖤓, 𖤓) \]

\[ L_4=(𖤓, 𖤓, 𖤓, 5, 𖤓) \]

Ημι-ταξινομημένη λίστα 🌗

L1=(4 | 𖤓, 𖤓, 𖤓, 1)

Επιλογή 🔎

L1=(4 | 𖤓, 𖤓, 𖤓, [1])

Σύγκριση 🆚

4 > 1

Ημι-ταξινομημένη λίστα 🌗

L1=(1, 𖤓, 𖤓, 𖤓, 4)

---

Οι υπόλοιπες υπο-λίστες L2, L3, L4 έχουν από ένα μόνο στοιχείο,
οπότε θεωρούνται ήδη ταξινομημένες:

L2=(𖤓, 10, 𖤓, 𖤓, 𖤓)
L3=(𖤓, 𖤓, 3, 𖤓, 𖤓)
L4=(𖤓, 𖤓, 𖤓, 5, 𖤓)

Συνδυάζοντας τα αποτελέσματα έχουμε:

\[ L=(1, 10, 3, 5, 4) \]

Το επόμενο gap στην ακολουθία Knuth είναι \(1\) (πάμε προς τα πίσω στην ακολουθία). Έτσι, τώρα συγκρίνουμε γειτονικά στοιχεία (gap\(=1\)), άρα εφαρμόζουμε κανονική Insertion Sort στην \(L\):

Ημι-ταξινομημένη λίστα 🌗

(1 | 10, 3, 5, 4)

Επιλογή 🔎

(1 | [10], 3, 5, 4)

Σύγκριση 🆚

1 < 10

Ημι-ταξινομημένη λίστα 🌗

(1, 10 | 3, 5, 4)

Επιλογή 🔎

(1, 10 | [3], 5, 4)

Σύγκριση 🆚

1 < 3 < 10

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 10 | 5, 4)

Επιλογή 🔎

(1, 3, 10 | [5], 4)

Σύγκριση 🆚

3 < 5 < 10

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 5, 10 | 4)

Επιλογή 🔎

(1, 3, 5, 10 | [4])

Σύγκριση 🆚

3 < 4 < 5

Ημι-ταξινομημένη λίστα 🌗

(1, 3, 4, 5, 10)

ΤΕΛΟΣ ⛔
shellSort2 <- function(arr) {
  n <- length(arr)
  
  # Αν ο πίνακας είναι κενός ή έχει 1 στοιχείο, επέστρεψέ τον ως έχει
  if (n <= 1) return(arr)
  
  gap <- 1
  while (gap < n / 3) {
    gap <- 3 * gap + 1
  }
  
  while (gap > 0) {
    # Προσθήκη ελέγχου: Μόνο αν το gap + 1 δεν ξεπερνά το n
    if (gap + 1 <= n) {
      for (i in (gap + 1):n) {
        temp <- arr[i]
        j <- i
        
        # Προσθέτουμε και έναν έλεγχο !is.na(temp) για extra ασφάλεια
        while (j > gap && !is.na(arr[j - gap]) && arr[j - gap] > temp) {
          arr[j] <- arr[j - gap]
          j <- j - gap
        }
        arr[j] <- temp
      }
    }
    gap <- floor(gap / 3)
  }
  
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# SHELL SORT 2 (Knuth)
print(shellSort2(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

4 Bubble Sort - Ταξινόμηση με αντιμετάθεση

Η ταξινόμηση με αντιμετάθεση (φυσαλίδα) λειτουργεί ως εξής:

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

Ξεκινάμε για άλλη μια φορά με τη λίστα \((4, 10, 3, 5, 1)\).

  1. Αρχίζουμε με τη σύγκριση 1ου-2ου στοιχείου, ήτοι των \(4\) και \(10\). Επειδή \(4<10\), τ’ αφήνουμε ως έχουν:

\[ (4, 10, 3, 5, 1) \]

  1. Συνεχίζουμε με τη σύγκριση 2ου-3ου στοιχείου, ήτοι των \(10\) και \(3\). Επειδή \(10>3\), τα αντιμεταθέτουμε:

\[ (4, 3, 10, 5, 1) \]

  1. Συνεχίζουμε με τη σύγκριση 3ου-4ου στοιχείου (της νέας λίστας), ήτοι των \(10\) και \(5\). Επειδή \(10>5\), τα αντιμεταθέτουμε:

\[ (4, 3, 5, 10, 1) \]

  1. Συνεχίζουμε με τη σύγκριση 4ου-5ου στοιχείου (της νέας λίστας), ήτοι των \(10\) και \(1\). Επειδή \(10>1\), τα αντιμεταθέτουμε:

\[ (4, 3, 5, 1, 10) \]

Παρατηρούμε ότι το \(10\), δηλαδή το μέγιστο της λίστας μας, ανέβηκε σαν φυσσαλίδα πάνω-πάνω.

  1. Επαναλαμβάνουμε αυτή τη διαδικασία πολλές φορές.

Συνεχίζουμε από εκεί που έμεινε η \((4, 3, 5, 1, 10)\).

Σύγκριση 🆚

4>3

Αντιμετάθεση  🔄 

(3, 4, 5, 1, 10)

Σύγκριση 🆚

4<5

Παραμένουν ίδια  ✅

(3, 4, 5, 1, 10)

Σύγκριση 🆚

5>1

Αντιμετάθεση  🔄 

(3, 4, 1, 5, 10)

Το 2ο σε μέγεθος στοιχείο (5) έφτασε στην 2η από το τέλος θέση, άρα τέλος αυτός ο βρόχος ⛔

Σύγκριση 🆚

3<4

Παραμένουν ίδια  ✅

(3, 4, 1, 5, 10)

Σύγκριση 🆚

4>1

Αντιμετάθεση  🔄 

(3, 1, 4, 5, 10)

Το 3ο σε μέγεθος στοιχείο (4) έφτασε στην 3η από το τέλος θέση, άρα τέλος αυτός ο βρόχος ⛔

Σύγκριση 🆚

3>1

Αντιμετάθεση  🔄 

(1, 3, 4, 5, 10)

Το 4ο και το 5ο σε μέγεθος στοιχείο (1, 3) έφτασαν στην 4η και την 5η αντίστοιχα από το τέλος θέση, άρα ΤΕΛΟΣ ⛔
TipΕν συντομία

Το κάθε στοιχείο ανέρχεται προς τα πάνω μέχρι να συναντήσει κάποιο μεγαλύτερο.

bubbleSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Εξωτερικός βρόχος: επαναλαμβάνουμε τη διαδικασία n-1 φορές
  # (Κάθε φορά ένα στοιχείο "φτάνει" στη σωστή θέση στο τέλος)
  for (i in 1:(n-1)) {
    
    # Εσωτερικός βρόχος: διατρέχουμε τη λίστα συγκρίνοντας γειτονικά στοιχεία
    # Σταματάμε στο n-i γιατί τα i τελευταία στοιχεία είναι ήδη στη σωστή θέση
    for (j in 1:(n-i)) {
      
      # Συγκρίνουμε το τρέχον στοιχείο με το επόμενο
      if (arr[j] > arr[j + 1]) {
        # Αν το τρέχον είναι μεγαλύτερο, τα αντιμεταθέτουμε
        temp <- arr[j]           # Αποθηκεύουμε προσωρινά το πρώτο στοιχείο
        arr[j] <- arr[j + 1]     # Βάζουμε το δεύτερο στη θέση του πρώτου
        arr[j + 1] <- temp       # Βάζουμε το πρώτο στη θέση του δεύτερου
      }
    }
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# BUBBLE SORT
print(bubbleSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

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

Ξεκινάμε και αυτή τη φορά με τη λίστα \((4, 10, 3, 5, 1)\). Ας δούμε τον 1ο βρόχο

swapped=F 👎

Σύγκριση 🆚

4<10

Παραμένουν ίδια  ✅

(4, 10, 3, 5, 1)

swapped=F 👎

Σύγκριση 🆚

10>3

Αντιμετάθεση  🔄 

(4, 3, 10, 5, 1)

swapped=T 👍

Σύγκριση 🆚

10>5

Αντιμετάθεση  🔄 

(4, 3, 5, 10, 1)

swapped=Τ (από πριν) 👍

Σύγκριση 🆚

10>1

Αντιμετάθεση  🔄 

(4, 3, 5, 1, 10)

swapped=Τ (από πριν) 👍

Καθόσον swapped=Τ, συνεχίζουμε στον επόμενο βρόχο θέτοντας swapped=F.

swapped=F   👎

Σύγκριση 🆚

4>3

Αντιμετάθεση  🔄 

(3, 4, 5, 1, 10)

swapped=Τ 👍

Σύγκριση 🆚

4<5

Παραμένουν ίδια  ✅

(3, 4, 5, 1, 10)

swapped=Τ (από πριν) 👍

Σύγκριση 🆚

5>1

Αντιμετάθεση  🔄 

(3, 4, 1, 5, 10)

swapped=Τ (από πριν) 👍

Καθόσον swapped=Τ, συνεχίζουμε στον επόμενο βρόχο θέτοντας swapped=F.

swapped=F   👎

Σύγκριση 🆚

3<4

Παραμένουν ίδια  ✅

(3, 4, 1, 5, 10)

swapped=F   👎

Σύγκριση 🆚

4>1

Αντιμετάθεση  🔄 

(3, 1, 4, 5, 10)

swapped=Τ 👍

Καθόσον swapped=Τ, συνεχίζουμε στον επόμενο βρόχο θέτοντας swapped=F.

swapped=F   👎

Σύγκριση 🆚

3>1

Αντιμετάθεση  🔄 

(1, 3, 4, 5, 10)

swapped=Τ 👍

Αφού swapped=Τ, θα έπρεπε κανονικά να συνεχίσουμε, αλλά εδώ τελειώνει ούτως ή άλλως η όλη διαδικασία. Εν κατακλείδι η βελτιστοποιημένη εκδοχή της Bubble Sort δεν εκτελέστηκε σε λιγότερα βήματα.

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

\[ (1, 3, 10, 5, 4) \]

TipΕν συντομία

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

bubbleSort_opt <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Εξωτερικός βρόχος: μέχρι n-1 φορές
  for (i in 1:(n-1)) {
    
    # Σημαία που δείχνει αν έγινε κάποια ανταλλαγή σε αυτή τη διέλευση
    # Ξεκινάει ως FALSE (καμία ανταλλαγή)
    swapped <- FALSE
    
    # Εσωτερικός βρόχος: διατρέχουμε τη λίστα
    for (j in 1:(n-i)) {
      
      # Συγκρίνουμε γειτονικά στοιχεία
      if (arr[j] > arr[j + 1]) {
        # Αντιμετάθεση
        temp <- arr[j]
        arr[j] <- arr[j + 1]
        arr[j + 1] <- temp
        
        # Σημειώνουμε ότι έγινε ανταλλαγή
        swapped <- TRUE
      }
    }
    
    # Αν δεν έγινε καμία ανταλλαγή σε αυτή τη διέλευση,
    # σημαίνει ότι η λίστα είναι ήδη ταξινομημένη
    if (!swapped) {
      # Βγαίνουμε από τον βρόχο νωρίτερα (εξοικονόμηση χρόνου!)
      break
    }
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# BUBBLE SORT (Βελτιστοποιημένο)
print(bubbleSort_opt(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

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

Ας πάρουμε πάλι τη λίστα \((4, 10, 3, 5, 1)\) κι ας δούμε τον 1ο βρόχο, ο οποίος διατρέχει τη λίστα από αριστερά προς δεξιά. Πάλι το swapped δηλώνει αν έχει γίνει αντιμετάθεση στον βρόχο.

ΚΙΝΗΣΗ ➡️

swapped=F 👎

Σύγκριση 🆚

4<10

Παραμένουν ίδια  ✅

(4, 10, 3, 5, 1)

swapped=F 👎

Σύγκριση 🆚

10>3

Αντιμετάθεση  🔄 

(4, 3, 10, 5, 1)

swapped=T 👍

Σύγκριση 🆚

10>5

Αντιμετάθεση  🔄 

(4, 3, 5, 10, 1)

swapped=Τ (από πριν) 👍

Σύγκριση 🆚

10>1

Αντιμετάθεση  🔄 

(4, 3, 5, 1, 10)

swapped=Τ (από πριν) 👍

Δεδομένου ότι swapped=Τ, πάμε στον επόμενο βρόχο, ο οποίος στην εκδοχή αυτή της Bubble Sort θα πηγαίνει από δεξιά προς αριστερά. Η λίστα έχει ως εξής (εντός [ ] τα νούμερα στη σωστή θέση σύμφωνα με τη φάση του αλγορίθμου):

\[ (4, 3, 5, 1, [10]) \]

Δεδομένου ότι το μέγιστο στοιχείο (\(10\)) είναι στην τελευταία θέση, οι συγκρίσεις αρχίζουν από την προτελευταία.

ΚΙΝΗΣΗ ⬅️

swapped=F 👎

Σύγκριση 🆚

1<5

Αντιμετάθεση  🔄 

(4, 3, 1, 5, 10)

swapped=T 👍

Σύγκριση 🆚

1<3

Αντιμετάθεση  🔄 

(4, 1, 3, 5, 10)

swapped=T (από πριν) 👍

Σύγκριση 🆚

1<4

Αντιμετάθεση  🔄 

(1, 4, 3, 5, 10)

swapped=T (από πριν) 👍

Καθόσον swapped=T, συνεχίζουμε, λαμβάνοντας υπ’ όψιν ότι το ελάχιστο (\(1\)) και το μέγιστο στοιχείο (\(10\)) της λίστας είναι στις σωστές θέσεις. Έχουμε (εντός [ ] στη σωστή θέση):

\[ ([1], 4, 3, 5, [10]) \]

Επομένως η σύγκριση αρχίζει από το 2ο στοιχείο αριστερά και κινείται προς τα δεξιά.

ΚΙΝΗΣΗ ➡️

swapped=F 👎

Σύγκριση 🆚

4>3

Αντιμετάθεση  🔄 

(1, 3, 4, 5, 10)

swapped=T 👍

Σύγκριση 🆚

4<5

Παραμένουν ίδια  ✅

(1, 3, 4, 5, 10)

swapped=T (από πριν) 👍

«Με το μάτι» βλέπουμε πως η λίστα είναι ταξινομημένη. Όμως ο αλγόριθμος βλέπει swapped=T, άρα συνεχίζουμε. Σύμφωνα με τη μέχρι τώρα φάση έχουμε ταξινομημένα τα κάτωθι εντός [ ]:

\[ ([1], 3, 4, [5, 10]) \]

Επομένως αρχίζουμε από το 3ο στοιχείο από δεξιά (το \(4\)).

ΚΙΝΗΣΗ ⬅️

swapped=F 👎

Σύγκριση 🆚

4>3

Παραμένουν ίδια  ✅

(1, 3, 4, 5, 10)

swapped=F 👎

Δεδομένου ότι δεν έχει απομείνει κάτι να ταξινομήσουμε, ο βρόχος σταματάει εκεί. Κι εκεί τελειώνει και η όλη διαδικασία, αφού έχουμε swapped=F.

bubbleSort_shake <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Ορίζουμε τα όρια της περιοχής που χρειάζεται ταξινόμηση
  left <- 1      # Αρχή της λίστας
  right <- n     # Τέλος της λίστας
  
  # Συνεχίζουμε όσο υπάρχει περιοχή για ταξινόμηση
  while (left < right) {
    
    # Σημαία για να δούμε αν έγινε ανταλλαγή
    swapped <- FALSE
    
    # ΦΑΣΗ 1: Από αριστερά προς τα δεξιά
    # Τα μεγάλα στοιχεία "φουσκώνουν" προς τα δεξιά
    for (i in left:(right-1)) {
      if (arr[i] > arr[i + 1]) {
        # Αντιμετάθεση
        temp <- arr[i]
        arr[i] <- arr[i + 1]
        arr[i + 1] <- temp
        swapped <- TRUE
      }
    }
    
    # Αν δεν έγινε ανταλλαγή, η λίστα είναι ταξινομημένη
    if (!swapped) break
    
    # Μειώνουμε το δεξί όριο γιατί το μεγαλύτερο στοιχείο έφτασε στο τέλος
    right <- right - 1
    
    # Επαναφορά της σημαίας για τη δεύτερη φάση
    swapped <- FALSE
    
    # ΦΑΣΗ 2: Από δεξιά προς τα αριστερά
    # Τα μικρά στοιχεία "βυθίζονται" προς τα αριστερά
    for (i in right:left) {
      if (i > 1 && arr[i-1] > arr[i]) {
        # Αντιμετάθεση
        temp <- arr[i-1]
        arr[i-1] <- arr[i]
        arr[i] <- temp
        swapped <- TRUE
      }
    }
    
    # Αν δεν έγινε ανταλλαγή, η λίστα είναι ταξινομημένη
    if (!swapped) break
    
    # Αυξάνουμε το αριστερό όριο γιατί το μικρότερο στοιχείο έφτασε στην αρχή
    left <- left + 1
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# BUBBLE SORT (Shake/Cocktail)
print(bubbleSort_shake(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

5 Quick Sort - Ταξινόμηση με διαμερισμό

Η Quick Sort χρησιμοποιεί τη στρατηγική «διαίρει και βασίλευε»:

  1. Επιλέγουμε ένα στοιχείο ως pivot (σημείο αναφοράς).

Υπάρχουν διάφορες επιλογές. Εδώ θα επιλέξουμε την 1η για λόγους απλότητας του κώδικα.

  1. Σταθερή επιλογή (Πρώτο ή Τελευταίο στοιχείο). Στις πιο απλές υλοποιήσεις, επιλέγεται πάντα το πρώτο ή το τελευταίο στοιχείο του πίνακα.
  • Το πρόβλημα: Αν ο πίνακας είναι ήδη ταξινομημένος (ή σχεδόν ταξινομημένος), αυτή η επιλογή είναι η χειρότερη δυνατή, οδηγώντας σε πολυπλοκότητα \(O(n^2)\) αντί για το επιθυμητό \(O(n \log n)\).
  1. Τυχαία επιλογή (Randomized Quick Sort). Εδώ, το pivot επιλέγεται όντως τυχαία από τα διαθέσιμα στοιχεία του υπο-πίνακα.
  • Πλεονέκτημα: Είναι μια εξαιρετική άμυνα ενάντια σε «κακά» σετ δεδομένων. Η πιθανότητα να επιλέγεις συνεχώς το χειρότερο δυνατό pivot σε κάθε βήμα είναι πρακτικά μηδενική. Έτσι, εξασφαλίζεις μέση απόδοση \(O(n \log n)\) για οποιοδήποτε είδος εισόδου.
  1. Η μέθοδος “Median-of-Three” (Διάμεσος των τριών). Επιλέγουμε ως pivot το διάμεσο στοιχείο του πρώτου, του τελευταίου και του μεσαίου στην αταξινόμητη λίστα.
  • Πλεονέκτημα: Αυτό αυξάνει σημαντικά τις πιθανότητες το pivot να βρίσκεται κοντά στο κέντρο των τιμών του πίνακα, βοηθώντας στον ισομερή διαχωρισμό του σε δύο ίσα μέρη, που είναι και το μυστικό της ταχύτητας της Quick Sort.
  1. Επιλογή του Μεσαίου στοιχείου. Η επιλογή του στοιχείου στη θέση (αρχή + τέλος) / 2.
  • Υπέρ/κατά: Λειτουργεί καλά για ήδη ταξινομημένους πίνακες, αλλά μπορεί να παγιδευτεί από άλλα συγκεκριμένα μοτίβα δεδομένων.

Ας ξεκινήσουμε με την αταξινόμητη λίστα \((4, 10, 3, 5, 1)\). Επιλέγουμε το τελευταίο στοιχείο της ως pivot:

Επιλογή pivot 📌

(4, 10, 3, 5, [1])
  1. Αναδιοργανώνουμε τη λίστα έτσι ώστε:
  • όλα τα στοιχεία μικρότερα από το pivot να είναι αριστερά του και
  • όλα τα στοιχεία μεγαλύτερα από το pivot να είναι δεξιά του.

Στην περίπτωση της \((4, 10, 3, 5, 1)\) το επιλεγμένο στοιχείο (\(1\)) θα πάει στην αρχή, διότι δεν υπάρχει κάτι μικρότερο από αυτό. Το \(4\) που ήταν ήδη στην αρχή πάει στη θέση του \(1\).

Διαμερίζουμε τη λίστα σε μικρότερα/μεγαλύτερα του pivot 💔

(< > | 1 | <10, 3, 5, 4>)
  1. Εφαρμόζουμε αναδρομικά την ίδια διαδικασία στα αριστερά και δεξιά υπο-τμήματα.
Επιλογή pivot (αριστερής λίστας της (< > | 1 | <10, 3, 5, 4>)) 📌

( < > ) # Κενή, άρα ταξινομημένη - Τέλος ⛔

Επιλογή pivot (δεξιάς λίστας της (< > | 1 | <10, 3, 5, 4>)) 📌

(10, 3, 5, [4])

Διαμερίζουμε τη λίστα σε μικρότερα/μεγαλύτερα του pivot 💔

(<3> |4| <5, 10>)

Επιλογή pivot (αριστερής λίστας της (<3> |4| <5, 10>) 📌

( <3> ) # Ένα μόνο στοιχείο, άρα ταξινομημένη - Τέλος ⛔

Επιλογή pivot (δεξιάς λίστας της (<3> |4| <5, 10>) 📌

(<5, [10]> )

Διαμερίζουμε τη λίστα σε μικρότερα/μεγαλύτερα του pivot 💔

(<5> |10| < >)

Επιλογή pivot (αριστερής λίστας της (<5> |10| < >) 📌

( <5> ) # Ένα μόνο στοιχείο, άρα ταξινομημένη - Τέλος ⛔

Επιλογή pivot (δεξιάς λίστας της (<5> |10| < >) 📌

( < > ) # Κενή, άρα ταξινομημένη - Τέλος ⛔
TipΕν συντομία

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

# Βοηθητική συνάρτηση για διαμερισμό
partition <- function(arr, low, high) {
  # Επιλέγουμε το τελευταίο στοιχείο ως pivot
  pivot <- arr[high]
  
  # Δείκτης για τη θέση όπου θα τοποθετηθεί το επόμενο μικρό στοιχείο
  # Ξεκινάει μία θέση πριν από το low
  i <- low - 1
  
  # Διατρέχουμε όλα τα στοιχεία εκτός από το pivot
  for (j in low:(high-1)) {
    
    # Αν το τρέχον στοιχείο είναι μικρότερο ή ίσο με το pivot
    if (arr[j] <= pivot) {
      # Αυξάνουμε τον δείκτη i
      i <- i + 1
      
      # Αντιμεταθέτουμε arr[i] με arr[j]
      # (βάζουμε το μικρό στοιχείο στο αριστερό μέρος)
      temp <- arr[i]
      arr[i] <- arr[j]
      arr[j] <- temp
    }
  }
  
  # Βάζουμε το pivot στη σωστή του θέση
  # (ανάμεσα στα μικρά και τα μεγάλα στοιχεία)
  temp <- arr[i + 1]
  arr[i + 1] <- arr[high]
  arr[high] <- temp
  
  # Επιστρέφουμε τη θέση του pivot
  return(list(arr = arr, pivot_index = i + 1))
}
 
# Κύρια αναδρομική συνάρτηση Quick Sort
quickSort_helper <- function(arr, low, high) {
  # Βασική περίπτωση: αν έχουμε 0 ή 1 στοιχείο, δεν χρειάζεται ταξινόμηση
  if (low < high) {
    
    # Κάνουμε διαμερισμό και παίρνουμε τη θέση του pivot
    result <- partition(arr, low, high)
    arr <- result$arr
    pi <- result$pivot_index
    
    # Ταξινομούμε αναδρομικά το αριστερό υπο-τμήμα
    # (στοιχεία μικρότερα από το pivot)
    arr <- quickSort_helper(arr, low, pi - 1)
    
    # Ταξινομούμε αναδρομικά το δεξί υπο-τμήμα
    # (στοιχεία μεγαλύτερα από το pivot)
    arr <- quickSort_helper(arr, pi + 1, high)
  }
  
  # Επιστρέφουμε το (μερικώς ή πλήρως) ταξινομημένο τμήμα
  return(arr)
}
 
# Συνάρτηση-περιτύλιγμα για τον χρήστη
quickSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Καλούμε τη βοηθητική συνάρτηση για ολόκληρη τη λίστα
  # (από θέση 1 μέχρι θέση n)
  return(quickSort_helper(arr, 1, n))
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# QUICK SORT
print(quickSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

6 Merge Sort - Ταξινόμηση με συγχώνευση

Η Merge Sort επίσης χρησιμοποιεί «διαίρει και βασίλευε» χρησιμοποιώντας συγχρόνως μια αναδρομική λογική:

  1. Χωρίζουμε τη λίστα στη μέση σε δύο μισά (L και R). Το κάθε μισό θεωρείται ταξινομημένο, αν είναι μονοσύνολο ή αν έχει ταξινομηθεί ήδη από τη Merge Sort.

  2. Αν δεν είναι ταξινομημένα, πηγαίνουμε ξανά στο βήμα 1.

  3. Αν είναι ταξινομημένα, τότε φτιάχνουμε μια νέα λίστα όπου:

  • το 1ο στοιχείο της θα είναι το μικρότερο του 1ου της L και του 1ου της R (το επιλεγμένο αποσύρεται από την αρχική του λίστα),
  • το 2ο στοιχείο της θα είναι το μικρότερο του 1ου της (νεοδιαμορφωθείσας) L και του 1ου της (νεοδιαμορφωθείσας) R (το επιλεγμένο αποσύρεται από την αρχική του λίστα),
  • το 3ο στοιχείο της θα είναι το μικρότερο του 1ου της (νεοδιαμορφωθείσας) L και του 1ου της (νεοδιαμορφωθείσας) R (το επιλεγμένο αποσύρεται από την αρχική του λίστα),
  • κ.ο.κ. μέχρις εξαντλήσεως των L και R.

Ξεκινάμε για άλλη μια φορά με τη λίστα \((4, 10, 3, 5, 1)\). Αρχίζουμε κόβοντας σε L και R κομματάκια όλη τη λίστα, αφού αρχικά τίποτα δεν θεωρείται ταξινομημένο, πέραν των μονοσυνόλων.

                  (4, 10, 3, 5, 1)
                  /              \
              (4, 10, 3)         (5, 1)
              /       \        /       \
        (4, 10)       (3)    (5)       (1)
       /       \
     (4)      (10)

Τα \((4)\), \((10)\), \((3)\), \((5)\) και \((1)\) θεωρούνται ταξινομημένα και αρχίζουμε τη συγχόνευσή τους με στόχο να φτάσουμε στις αμέσως επόμενες ρίζες, δηλαδή τις \((4, 10)\) και \((5,1)\). Έτσι, έχουμε:

Σύγκριση 🆚      | Σύγκριση 🆚
                 |
4 < 10           | 5 > 1
                 |
Συγχόνευση 🔗    | Συγχόνευση 🔗
                 |
(4, 10)          | (1, 5)

Έχουμε πλέον:

                  (4, 10, 3, 5, 1)
                  /              \
              (4, 10, 3)         (1, 5)
              /       \              
        (4, 10)       (3)

Συγχονεύουμε τις \((4, 10)\) και \((3)\).

Σύγκριση το 1ο της L με το 1ο της R 🆚

3 < 4

Συγχώνευση 🔗

(3, ...)

Η R άδειασε, άρα τέλος ⛔

Συγχώνευση 🔗

(3, 4, 10)

Έχουμε πλέον:

                  (4, 10, 3, 5, 1)
                  /              \
              (3, 4, 10)         (1, 5)

Συγχονεύουμε τις \((3, 4, 10)\) και \((1, 5)\).

Σύγκριση το 1ο της L με το 1ο της R 🆚

3 > 1

Συγχώνευση 🔗

(1, ...)

Σύγκριση το 1ο της L με το 1ο της νεοδιαμορφοθείσας R=(5) 🆚

3 < 5

Συγχώνευση 🔗

(1, 3, ...)

Σύγκριση το 1ο της νεοδιαμορφοθελισας L=(4,10) με το 1ο της νεοδιαμορφοθείσας R=(5) 🆚

4 < 5

Συγχώνευση 🔗

(1, 3, 4, ...)

Σύγκριση το 1ο της νεοδιαμορφοθελισας L=(10) με το 1ο της νεοδιαμορφοθείσας R=(5) 🆚

10 > 5

Συγχώνευση 🔗

(1, 3, 4, 5, ...)

Η L άδειασε, άρα τέλος ⛔

Συγχώνευση 🔗

(1, 3, 4, 5, 10)
TipΕν συντομία

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

# Βοηθητική συνάρτηση για συγχώνευση δύο ταξινομημένων υπο-λιστών
merge <- function(arr, left, mid, right) {
  # Υπολογίζουμε τα μεγέθη των δύο υπο-λιστών
  n1 <- mid - left + 1    # Μέγεθος αριστερής υπο-λίστας
  n2 <- right - mid       # Μέγεθος δεξιάς υπο-λίστας
  
  # Δημιουργούμε προσωρινούς πίνακες για τις δύο υπο-λίστες
  L <- arr[left:mid]              # Αριστερή υπο-λίστα
  R <- arr[(mid+1):right]         # Δεξιά υπο-λίστα
  
  # Δείκτες για τις δύο υπο-λίστες και την κύρια λίστα
  i <- 1    # Δείκτης για την αριστερή υπο-λίστα (L)
  j <- 1    # Δείκτης για τη δεξιά υπο-λίστα (R)
  k <- left # Δείκτης για την κύρια λίστα (arr)
  
  # Συγχωνεύουμε τις δύο υπο-λίστες πίσω στην arr
  # Συγκρίνουμε το πρώτο στοιχείο από κάθε υπο-λίστα
  while (i <= n1 && j <= n2) {
    # Αν το στοιχείο από την αριστερή είναι μικρότερο ή ίσο
    if (L[i] <= R[j]) {
      # Το βάζουμε στην κύρια λίστα
      arr[k] <- L[i]
      # Προχωράμε στο επόμενο στοιχείο της αριστερής
      i <- i + 1
    } else {
      # Αλλιώς, βάζουμε το στοιχείο από τη δεξιά
      arr[k] <- R[j]
      # Προχωράμε στο επόμενο στοιχείο της δεξιάς
      j <- j + 1
    }
    # Προχωράμε στην επόμενη θέση της κύριας λίστας
    k <- k + 1
  }
  
  # Αντιγράφουμε τα υπόλοιπα στοιχεία από την L (αν υπάρχουν)
  while (i <= n1) {
    arr[k] <- L[i]
    i <- i + 1
    k <- k + 1
  }
  
  # Αντιγράφουμε τα υπόλοιπα στοιχεία από την R (αν υπάρχουν)
  while (j <= n2) {
    arr[k] <- R[j]
    j <- j + 1
    k <- k + 1
  }
  
  # Επιστρέφουμε τη συγχωνευμένη λίστα
  return(arr)
}
 
# Κύρια αναδρομική συνάρτηση Merge Sort
mergeSort_helper <- function(arr, left, right) {
  # Βασική περίπτωση: αν έχουμε περισσότερα από 1 στοιχεία
  if (left < right) {
    
    # Βρίσκουμε το μεσαίο σημείο για να χωρίσουμε τη λίστα στα δύο
    mid <- floor((left + right) / 2)
    
    # Ταξινομούμε αναδρομικά το αριστερό μισό
    arr <- mergeSort_helper(arr, left, mid)
    
    # Ταξινομούμε αναδρομικά το δεξί μισό
    arr <- mergeSort_helper(arr, mid + 1, right)
    
    # Συγχωνεύουμε τα δύο ταξινομημένα μισά
    arr <- merge(arr, left, mid, right)
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}
 
# Συνάρτηση-περιτύλιγμα για τον χρήστη
mergeSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # Καλούμε τη βοηθητική συνάρτηση για ολόκληρη τη λίστα
  return(mergeSort_helper(arr, 1, n))
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# MERGE SORT 
print(mergeSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

7 Heap Sort - Ταξινόμηση με σωρό

Η Heap Sort χρησιμοποιεί τη λογική των δυαδικών δέντρων:

  1. Φτιάχνουμε ένα δυαδικό δέντρο έτσι όπως βλέπουμε τη λίστα πηγαίνοντας αριστερά, δεξιά, πάνω,κάτω, όπως διαβάζουμε μια σελίδα.

Αν έχουμε την \((4, 10, 3, 5, 1)\), τότε το δέντρο είναι:

      4
     / \
   10   3
  / \
 5   1
  1. Στο δέντρο θα πρέπει κάθε «γονέας» να είναι μεγαλύτερος από τα «παιδιά» του. Ο έλεγχος αρχίζει από κάτω προς τα πάνω και οποτεδήποτε βρεθεί «γονέας» μικρότερος από κάποιο «παιδί», το «παιδί» παίρνει τη θέση του γονέα.
A' έλεγχος ✅
       4
      / \
  [10]   3
   / \
  5   1
  
B' έλεγχος ❌
      [4]
      / \
    10   3
   / \
  5   1

Διόρθωση 🛠️  
       10
      /  \
    4    3
   / \
  5   1
  1. Ξαναρχίζουμε τη διαδικασία από το πιο κάτω κλαδί, μέχρι να γίνει το δέντρο όπως θέλουμε («γονείς» μεγαλύτεροι από «παιδιά»).
Α' έλεγχος ❌
       10
      /  \
   [4]    3
   / \
  5   1
  
Διόρθωση 🛠️ 
       10
      /  \
    5    3
   / \
  4   1
  1. Όταν στο δέντρο οι «γονείς» είναι μεγαλύτεροι από τα «παιδιά»:
  • πετάμε εκτός δέντρου τη ρίζα,
  • στη θέση του βάζουμε το πιο κάτω-δεξιά παιδί,
  • τον αριθμό που αποσύρθηκε τον βάζουμε στο τέλος της προς ταξινόμησιν λίστας όπως αυτή περιγράφεται από το παραγόμενο δέντρο.

Εν προκειμένω:

  • πετάμε εκτός δέντρου το \(10\),
  • στη θέση του βάζουμε το \(1\),
  • έχουμε την ημι-ταξινομημένη λίστα \((1, 5, 3, 4, | 10)\).
       1   
      / \
    5   3
   /
  4
  1. Επαναλαμβάνουμε τη διαδικασία «φυσιολογικοποίησης» του δέντρου βάζοντας όπως πριν τους γονείς πάνω από τα παιδιά.
A' έλεγχος ✅
       1   
      / \
    [5]   3
   /
  4
  
B' έλεγχος ❌
      [1]   
      / \
     5   3
    /
   4
  
Διόρθωση 🛠️ 
      [5]   
      / \
    1    3
   /
  4
  
A2' έλεγχος ❌
       5   
      / \
   [1]   3
   /
  4

Διόρθωση 🛠️ 
      5   
     / \
    4   3
   /
  1
  1. Όταν το δέντρο γίνει πάλι «σωστό»:
  • πετάμε εκτός δέντρου τη ρίζα,
  • στη θέση του βάζουμε το πιο κάτω παιδί,
  • τον αριθμό που αποσύρθηκε τον βάζουμε στο τέλος της προς ταξινόμησιν λίστας όπως αυτή περιγράφεται από το παραγόμενο δέντρο.

Εν προκειμένω:

  • πετάμε εκτός δέντρου το \(5\),
  • στη θέση του βάζουμε το \(1\),
  • έχουμε την ημι-ταξινομημένη λίστα \((1, 4, 3 | 5, 10)\).
   1
  / \
 4   3
  1. Επαναλαμβάνουμε τη διαδικασία «φυσιολογικοποίησης» του δέντρου, απόσυρσης της ρίζας του «φυσιολογικού δέντρου» και αντικατάστασής της με τον μικρότερο μέχρι να χαθεί το δέντρο (να του μείνει ένα μόνο στοιχείο).
Α' έλεγχος ❌

   [1]
   / \
  4   3
  
Διόρθωση 🛠️ 
    4
   / \
  1   3
  
Απόσυρση ρίζας 💥 
Ημι-ταξινομημένη λίστα: (3, 1 | 4, 5, 10)

  3
 /
1

A' έλεγχος ✅
 [3]
 /
1

Απόσυρση ρίζας 💥 
Ημι-ταξινομημένη λίστα: (1 | 3, 4, 5, 10)

1

ΤΕΛΟΣ ⛔

Ταξινομημένη λίστα: (1, 3, 4, 5, 10)
TipΕν συντομία

Η Heap Sort μετατρέπει τη προς ταξινόμησιν λίστα σε διαδικό δέντρο και μετά με συγκρίσεις από «κλαδί» σε «κλαδί» φτιάχνει την ταξινομημένη λίστα.

# Βοηθητική συνάρτηση για να διατηρήσουμε την ιδιότητα του heap
heapify <- function(arr, n, i) {
  # Υποθέτουμε ότι ο τρέχων κόμβος (i) είναι ο μεγαλύτερος
  largest <- i
  
  # Υπολογίζουμε τις θέσεις των παιδιών
  # Σε έναν heap που αναπαρίσταται σε πίνακα:
  # - Αριστερό παιδί του i: 2*i
  # - Δεξί παιδί του i: 2*i + 1
  left <- 2 * i      # Θέση αριστερού παιδιού
  right <- 2 * i + 1 # Θέση δεξιού παιδιού
  
  # Ελέγχουμε αν το αριστερό παιδί υπάρχει και είναι μεγαλύτερο από τον γονέα
  if (left <= n && arr[left] > arr[largest]) {
    # Το αριστερό παιδί είναι το μεγαλύτερο
    largest <- left
  }
  
  # Ελέγχουμε αν το δεξί παιδί υπάρχει και είναι μεγαλύτερο από το τρέχον μεγαλύτερο
  if (right <= n && arr[right] > arr[largest]) {
    # Το δεξί παιδί είναι το μεγαλύτερο
    largest <- right
  }
  
  # Αν το μεγαλύτερο στοιχείο δεν είναι ο γονέας
  if (largest != i) {
    # Αντιμεταθέτουμε τον γονέα με το μεγαλύτερο παιδί
    temp <- arr[i]
    arr[i] <- arr[largest]
    arr[largest] <- temp
    
    # Αναδρομικά εφαρμόζουμε heapify στο υπο-δέντρο που επηρεάστηκε
    # (για να διασφαλίσουμε ότι όλο το υπο-δέντρο διατηρεί την ιδιότητα heap)
    arr <- heapify(arr, n, largest)
  }
  
  # Επιστρέφουμε τον τροποποιημένο πίνακα
  return(arr)
}
 
# Κύρια συνάρτηση Heap Sort
heapSort <- function(arr) {
  # Παίρνουμε το μήκος της λίστας
  n <- length(arr)
  
  # ΦΑΣΗ 1: Κατασκευή του max-heap
  # Ξεκινάμε από τον τελευταίο κόμβο που έχει παιδιά
  # (που είναι στη θέση n/2) και πηγαίνουμε προς την αρχή
  for (i in floor(n/2):1) {
    # Εφαρμόζουμε heapify σε κάθε υπο-δέντρο
    arr <- heapify(arr, n, i)
  }
  
  # ΦΑΣΗ 2: Εξαγωγή στοιχείων από τον heap ένα-ένα
  for (i in n:2) {
    # Μετακινούμε την τρέχουσα ρίζα (μεγαλύτερο στοιχείο) στο τέλος
    temp <- arr[1]
    arr[1] <- arr[i]
    arr[i] <- temp
    
    # Εφαρμόζουμε heapify στον μειωμένο heap
    # (χωρίς τα στοιχεία που έχουν ήδη τοποθετηθεί στο τέλος)
    arr <- heapify(arr, i - 1, 1)
  }
  
  # Επιστρέφουμε την ταξινομημένη λίστα
  return(arr)
}

Ελέγχουμε τη λειτουργικότητα του κώδικα:

# Αρχική λίστα η κάτωθι (από πριν)
# (64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 17, 78)
print(test_array)
 [1] 64 34 25 12 22 11 90 88 45 50 33 17 78
# HEAP SORT
print(heapSort(test_array))
 [1] 11 12 17 22 25 33 34 45 50 64 78 88 90

8 Πολυπλοκότητες χρόνου

Στο σημείο αυτό θα κάνουμε μια συνοπτική παρουσίαση της πολυπλοκότητας των αλγορίθμων που εξετάσαμε. Σχετική μελέτη είχε γίνει και σε παλαιότερη εργασία σε γλώσσα Python, η επανάληψή της όμως στην δεν ήταν εφικτή. Προς τούτο έγινε σχετική ερώτηση στο LLM claude.ai:

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

Όμως, αν την υλοποιήσω σε κώδικα R, αργεί πάρα πολύ, ακόμα και σε σχετικά μικρό πλήθος δοκιμών και με μικρά σύνολα αριθμών. Πού οφείλεται αυτό;

Η απάντηση που δώθηκε ήταν η κάτωθι:

1. Εμφωλευμένοι Βρόχοι με In-Place Τροποποιήσεις

Οι αλγόριθμοι ταξινόμησης (Selection, Insertion, Bubble, Shell Sort) έχουν εμφωλευμένους βρόχους με συνεχείς αντιμεταθέσεις στοιχείων. Στην Python αυτό είναι σχετικά γρήγορο, αλλά στην R είναι καταστροφικά αργό λόγω του μηχανισμού Copy-on-Modify.

2. Copy-on-Modify (Αντιγραφή κατά την Τροποποίηση)

Στην R, κάθε φορά που τροποποιείται ένα στοιχείο vector (π.χ. l[i] <- value), ολόκληρο το vector αντιγράφεται στη μνήμη. Αυτό προκαλεί: - Τεράστια χρήση μνήμης - Πολλαπλές αντιγραφές μεγάλων δομών - Overhead από garbage collection

Για παράδειγμα, στον bubble sort με n=1000 στοιχεία, εκτελούνται ~500,000 συγκρίσεις, που σημαίνει 500,000 πλήρεις αντιγραφές του vector στην R!

3. Το Πρόβλημα με τις Σύνθετες Δομές (structs/classes)

Το entryClass με 4 πεδία (int + 3 strings) κάνει το πρόβλημα ακόμα χειρότερο. Στην R, κάθε αντικείμενο (list ή S3/S4 class) που τροποποιείται αντιγράφεται ολόκληρο. Για λίστα με 1000 τέτοια objects, κάθε swap αντιγράφει 1000 structs πλήρως.

4. Αναδρομικές Κλήσεις (QuickSort, MergeSort)

Οι αναδρομικές συναρτήσεις στην R είναι πιο αργές από την Python λόγω: - Μεγαλύτερο overhead για function calls - Αντιγραφή παραμέτρων σε κάθε κλήση - Έλλειψη tail-call optimization

5. Interpreted vs Compiled Execution

Η R είναι διερμηνευόμενη γλώσσα (interpreted), ενώ η Python χρησιμοποιεί bytecode compilation και οι βιβλιοθήκες όπως το NumPy είναι γραμμένες σε C. Αυτό σημαίνει ότι: - Κάθε εντολή στην R ερμηνεύεται runtime - Δεν υπάρχει Just-In-Time (JIT) compilation για loops στην base R - Η Python με NumPy χρησιμοποιεί optimized, compiled C libraries

6. Έλλειψη Διανυσματοποίησης (Vectorization)

Οι αλγόριθμοι ταξινόμησης με εμφωλευμένους βρόχους δεν μπορούν να διανυσματοποιηθούν. Η R είναι βελτιστοποιημένη για διανυσματικές πράξεις (π.χ. x + y), όχι για imperative loops με conditionals και swaps.

Αναμενόμενη Διαφορά Απόδοσης

Για 1000 στοιχεία: - Bubble Sort: Python ~50 ms, R ~5-10 sec (100-200x πιο αργό) - Selection Sort: Python ~30 ms, R ~3-6 sec (100-200x πιο αργό) - Quick Sort: Python ~2 ms, R ~50-100 ms (25-50x πιο αργό) - Merge Sort: Python ~3 ms, R ~100-200 ms (30-60x πιο αργό)

Οι εναλλακτικές ήταν:

  • ή να χρησιμοποιηθεί C++ μέσα στην μέσω του πακέτου Rcpp,
  • ή να αρκεστούμε σε πολύ λιγότερες δοκιμές και με πολύ φτωχότερα σύνολα αριθμών.

Καμία από τις δύο λύσεις δεν χρησημοποιείται εδώ:

  • Η πρώτη λύση απορρίφθηκε, διότι δεν έχει νόημα να γράφει κανείς μια εργασία της σε γλώσσα C++…
  • Η δεύτερη λύση επίσης απορρίφθηκε, καθόσον η δοκιμή της, αν και διήρκησε ώρες, στηριζόταν σε τόσο λίγα στοιχεία που:
    • οι πειραματικοί χρόνοι δεν επαρκούσαν για να ανιχθευθεί μια στατιστική συμπεριφορά και
    • απέκλειναν τελείως από τα θεωρητικά δεδομένα (βλ. πίνακα Table 1).

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

Table 1: Σύγκριση Χρονικής και Χωρικής Πολυπλοκότητας Αλγορίθμων Ταξινόμησης
Αλγόριθμος Best Case Average Case Worst Case Space
Selection Sort \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\)
Insertion Sort \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\)
Bubble Sort \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\)
Shell Sort \(O(n \log n)\) \(O(n \log^2 n)\) \(O(n^2)\) \(O(1)\)
Quick Sort \(O(n \log n)\) \(O(n \log n)\) \(O(n^2)\) \(O(\log n)\)
Merge Sort \(O(n \log n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(n)\)
Heap Sort \(O(n \log n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(1)\)

Όπου:

  1. Best Case (Καλύτερη Περίπτωση): Πόσο γρήγορα τρέχει ο αλγόριθμος αν η λίστα είναι ήδη ταξινομημένη (ή σχεδόν ταξινομημένη).
  2. Average Case (Μέση Περίπτωση): Η αναμενόμενη ταχύτητα για μια τυχαία λίστα δεδομένων.
  3. Worst Case (Χειρότερη Περίπτωση): Το “άνω όριο” του χρόνου εκτέλεσης. Εγγυάται ότι ο αλγόριθμος δεν θα πάρει περισσότερο χρόνο από αυτόν, ακόμα και στην πιο “δύσκολη” λίστα (π.χ. εντελώς ανάποδα ταξινομημένη).
  4. Space (Πολυπλοκότητα Χώρου): Πόση επιπλέον μνήμη (RAM) χρειάζεται ο αλγόριθμος για να λειτουργήσει, πέρα από την ίδια τη λίστα. Το \(O(1)\) σημαίνει ότι η ταξινόμηση γίνεται “επί τόπου” (in-place) χωρίς επιπλέον μνήμη.