Η ταξινόμηση συγχώνευσης είναι ένας από τους πιο γνωστούς αλγορίθμους ταξινόμησης και βασίζεται στην προσέγγιση “Διαίρει και Βασίλευε”. Αυτή η μέθοδος επιτρέπει τη διαίρεση ενός προβλήματος σε μικρότερα υποπροβλήματα, τα οποία είναι πιο εύκολα να λυθούν. Στη συνέχεια, οι λύσεις των υποπροβλημάτων συγχωνεύονται για να παραγάγουν τη λύση του αρχικού προβλήματος.

Πώς Λειτουργεί η Ταξινόμηση Συγχώνευσης;

Βασικά Βήματα:

  1. Διαίρεση:
    • Ο αρχικός πίνακας χωρίζεται επαναληπτικά στη μέση, μέχρι να φτάσουμε σε πίνακες που περιέχουν ένα μόνο στοιχείο. Ένας πίνακας με ένα μόνο στοιχείο είναι ήδη ταξινομημένος.
  2. Συγχώνευση:
    • Οι μικρότεροι ταξινομημένοι πίνακες συγχωνεύονται για να σχηματίσουν μεγαλύτερους ταξινομημένους πίνακες. Αυτή η διαδικασία συνεχίζεται μέχρι να δημιουργηθεί ο τελικός ταξινομημένος πίνακας.

Διαδικασία

Διάγραμμα Ροής:

  1. Διαίρεση του πίνακα σε δύο υποπίνακες.
  2. Αναδρομική εφαρμογή της ταξινόμησης συγχώνευσης στους υποπίνακες.
  3. Συγχώνευση των ταξινομημένων υποπίνακων.

Παράδειγμα

Ας δούμε πώς λειτουργεί η ταξινόμηση συγχώνευσης με τον πίνακα {38, 27, 43, 3, 9, 82, 10}:

  1. Διαίρεση:
    • {38, 27, 43, 3, 9, 82, 10} → {38, 27, 43} και {3, 9, 82, 10}
    • {38, 27, 43} → {38} και {27, 43} → {27} και {43}
    • {3, 9, 82, 10} → {3, 9} και {82, 10} → {3} και {9}
  1. Συγχώνευση:
    • Συγχώνευση των στοιχείων:
      • {27} και {43} → {27, 38, 43}
      • {3} και {9} → {3, 9}
      • {82} και {10} → {10, 82}
    • Συγχώνευση των αποτελεσμάτων:
      • {27, 38, 43} και {3, 9} → {3, 9, 27, 38, 43}
      • Τέλος, {3, 9, 27, 38, 43} και {10, 82} → {3, 9, 10, 27, 38, 43, 82}

Χρονική Πολυπλοκότητα

  • Χρόνος Εκτέλεσης: Η ταξινόμηση συγχώνευσης έχει χρονική πολυπλοκότητα O(nlog⁡n)O(n \log n)O(nlogn), όπου nnn είναι ο αριθμός των στοιχείων στον πίνακα. Αυτή η πολυπλοκότητα προέρχεται από τη διαδικασία διαίρεσης (logarithmic) και τη συγχώνευση (linear).
  • Μνήμη: Χρειάζεται επιπλέον μνήμη O(n)O(n)O(n) για τον πίνακα συγχώνευσης, γεγονός που την καθιστά λιγότερο αποδοτική από πλευράς μνήμης σε σύγκριση με άλλους αλγόριθμους, όπως η ταξινόμηση με εισαγωγή.

Πλεονεκτήματα της Ταξινόμησης Συγχώνευσης

  1. Αποδοτικότητα: Είναι πιο αποδοτικός από αλγόριθμους όπως η ταξινόμηση με εισαγωγή (Insertion Sort) ή η ταξινόμηση επιλογής (Selection Sort), ειδικά για μεγάλα σύνολα δεδομένων.
  2. Σταθερότητα: Είναι ένας σταθερός αλγόριθμος, που σημαίνει ότι οι ίδιες τιμές παραμένουν στην ίδια σχετική θέση.
  3. Καλή Απόδοση σε Σταθμευμένα Δεδομένα: Λειτουργεί καλά με σχεδόν ταξινομημένα δεδομένα, καθώς η πολυπλοκότητα παραμένει O(nlog⁡n)O(n \log n)O(nlogn).

Μειονεκτήματα της Ταξινόμησης Συγχώνευσης

  1. Επιπλέον Μνήμη: Χρειάζεται επιπλέον μνήμη για τον πίνακα συγχώνευσης, που μπορεί να είναι αναποτελεσματικό σε περιβάλλοντα με περιορισμένη μνήμη.
  2. Δυσκολία Υλοποίησης: Μπορεί να είναι πιο δύσκολο να υλοποιηθεί σε σύγκριση με απλούς αλγόριθμους ταξινόμησης.

Πώς λειτουργεί;

  1. Διαίρεση: Διαιρεί τον πίνακα στα δύο μέχρι κάθε υποπίνακας να περιέχει ένα μόνο στοιχείο.
  2. Συγχώνευση: Συγχωνεύει τους υποπίνακες ταξινομώντας τους κατά τη συγχώνευση.

Ψευδογλώσσα

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

Παράδειγμα Ψευδογλώσσας

ΣΥΝΑΡΤΗΣΗ mergeSort(πίνακας)
    ΑΝ μήκος(πίνακας) <= 1 ΤΟΤΕ
        ΕΠΙΣΤΡΟΦΗ πίνακας
    ΤΕΛΟΣ_ΑΝ

    μέση = μήκος(πίνακας) / 2
    αριστερά = mergeSort(υποπίνακας(πίνακας, 0, μέση))
    δεξιά = mergeSort(υποπίνακας(πίνακας, μέση, μήκος(πίνακας)))

    ΕΠΙΣΤΡΟΦΗ συγχώνευση(αριστερά, δεξιά)
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

ΣΥΝΑΡΤΗΣΗ συγχώνευση(αριστερά, δεξιά)
    αποτελεσμα = νέος πίνακας
    όσο υπάρχουν στοιχεία στο αριστερά ή δεξιά ΤΟΤΕ
        ΑΝ αριστερά[0] <= δεξιά[0] ΤΟΤΕ
            πρόσθεσε το αριστερά[0] στο αποτελεσμα
            αφαίρεσε το πρώτο στοιχείο από το αριστερά
        ΑΛΛΙΩΣ
            πρόσθεσε το δεξιά[0] στο αποτελεσμα
            αφαίρεσε το πρώτο στοιχείο από το δεξιά
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΟΣΟ

    πρόσθεσε τα εναπομείναντα στοιχεία από το αριστερά και δεξιά στο αποτελεσμα
    ΕΠΙΣΤΡΟΦΗ αποτελεσμα
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Κώδικας σε C#

Ας δούμε πώς να υλοποιήσουμε την ταξινόμηση συγχώνευσης σε C#.

using System;

class Program
{
    static void Main()
    {
        int[] array = { 38, 27, 43, 3, 9, 82, 10 };
        MergeSort(array, 0, array.Length - 1);

        Console.WriteLine("Ταξινομημένος πίνακας: " + string.Join(", ", array));
    }

    static void MergeSort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;

            MergeSort(array, left, middle);
            MergeSort(array, middle + 1, right);

            Merge(array, left, middle, right);
        }
    }

    static void Merge(int[] array, int left, int middle, int right)
    {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        Array.Copy(array, left, leftArray, 0, n1);
        Array.Copy(array, middle + 1, rightArray, 0, n2);

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
        {
            if (leftArray[i] <= rightArray[j])
            {
                array[k] = leftArray[i];
                i++;
            }
            else
            {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1)
        {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2)
        {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

Ανάλυση Κώδικα

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

Βήματα Ενέργειας

    Αρχικοποίηση: Ξεκινήστε το πρόγραμμα με την Main μέθοδο.
    Διαίρεση: Η MergeSort διαιρεί τον πίνακα σε δύο μέρη.
    Αναδρομή: Κάθε μισό διαιρείται περαιτέρω αναδρομικά.
    Συγχώνευση: Οι υποπίνακες συγχωνεύονται με τη βοήθεια της Merge.

Συμπέρασμα

Η ταξινόμηση συγχώνευσης είναι μια ισχυρή και αποτελεσματική μέθοδος ταξινόμησης που χρησιμοποιείται συχνά λόγω της εγγυημένης χρονικής πολυπλοκότητας O(n log n). Ελπίζω η ανάλυση και τα παραδείγματα να σε βοηθήσουν να κατανοήσεις την ταξινόμηση συγχώνευσης και να την εφαρμόσεις με επιτυχία στον κώδικά σου.
Ταξινόμηση-Συγχώνευσης-Merge-SortDownload