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

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

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

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

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

Ψευδογλώσσα

Ας δούμε πώς θα μπορούσε να είναι ο αλγόριθμος στην ψευδογλώσσα:

Συνάρτηση InsertionSort(Πίνακας A)
    Για i από 1 έως το μήκος του A - 1
        key = A[i]
        j = i - 1
        
        Ενώ j >= 0 και A[j] > key
            A[j + 1] = A[j]
            j = j - 1
        
        A[j + 1] = key
    Τέλος Για
Τέλος Συνάρτησης

Συμπέρασμα

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

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

Υλοποίηση σε C#

Ας δούμε πώς θα το υλοποιήσουμε σε C#:

using System;

class Program
{
    static void Main()
    {
        int[] array = { 12, 11, 13, 5, 6 };
        InsertionSort(array);
        Console.WriteLine("Ταξινομημένος πίνακας: " + string.Join(", ", array));
    }

    static void InsertionSort(int[] array)
    {
        for (int i = 1; i < array.Length; i++)
        {
            int key = array[i];
            int j = i - 1;

            // Μετακίνηση των στοιχείων που είναι μεγαλύτερα από το key
            while (j >= 0 && array[j] > key)
            {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key; // Εισαγωγή του key στη σωστή θέση
        }
    }
}

Επεξήγηση της Υλοποίησης

Βρόχος for: Ξεκινάμε από το δεύτερο στοιχείο (i = 1) και προχωράμε μέχρι το τέλος του πίνακα.
key: Αποθηκεύουμε το στοιχείο που θέλουμε να εισαγάγουμε.
Βρόχος while: Συγκρίνουμε το key με τα προηγούμενα στοιχεία. Αν το προηγούμενο στοιχείο είναι μεγαλύτερο, το μετακινούμε ένα βήμα δεξιά.
Εισαγωγή: Όταν βρούμε τη σωστή θέση, εισάγουμε το key.

Χαρακτηριστικά του Αλγορίθμου

Χρόνος Εκτέλεσης: Ο χειρότερος και ο μέσος χρόνος εκτέλεσης είναι O(n^2), όπου n είναι ο αριθμός των στοιχείων.
Σταθερότητα: Είναι ένας σταθερός αλγόριθμος, πράγμα που σημαίνει ότι διατηρεί τη σειρά των ισοδύναμων στοιχείων.

Πλεονεκτήματα και Μειονεκτήματα

Πλεονεκτήματα:

C# Learning

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