Τι είναι το Shell Sort;

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

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

  1. Αρχικοποίηση του Gap: Ξεκινάμε με έναν gap που είναι συνήθως το μισό του μήκους του πίνακα.
  2. Ταξινόμηση με Gap: Για κάθε gap, κάνουμε μια ταξινόμηση Insertion Sort σε υποπίνακες που περιέχουν στοιχεία που απέχουν μεταξύ τους κατά το gap.
  3. Μείωση του Gap: Μειώνουμε το gap (συνήθως κατά το μισό) και επαναλαμβάνουμε τη διαδικασία.
  4. Τερματισμός: Συνεχίζουμε μέχρι το gap να γίνει 1, οπότε και εκτελούμε μια τελική ταξινόμηση Insertion Sort.

Βήματα του Shell Sort

Ακολουθεί η ψευδογλώσσα για να κατανοήσεις τη διαδικασία:

ΛΕΞΗ ShellSort(A)
    n = μήκος(A)
    gap = n / 2 // Αρχικό gap

    ΕΩΣ gap > 0
        ΓΙΑ i ΑΠΟ gap ΕΩΣ n - 1
            temp = A[i]
            j = i

            ΕΩΣ j >= gap ΚΑΙ A[j - gap] > temp
                A[j] = A[j - gap]
                j = j - gap
            ΤΕΛΟΣ_ΕΩΣ

            A[j] = temp
        ΤΕΛΟΣ_ΓΙΑ

        gap = gap / 2 // Μείωση του gap
    ΤΕΛΟΣ_ΕΩΣ
ΤΕΛΟΣ

C# Υλοποίηση

Ακολουθεί η υλοποίηση του Shell Sort στην C#:

using System;

class Program
{
    public static void ShellSort(int[] arr)
    {
        int n = arr.Length;
        int gap = n / 2; // Αρχικό gap

        while (gap > 0)
        {
            for (int i = gap; i < n; i++)
            {
                int temp = arr[i];
                int j = i;

                // Ταξινόμηση με βάση το gap
                while (j >= gap && arr[j - gap] > temp)
                {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }

            gap /= 2; // Μείωση του gap
        }
    }

    static void Main()
    {
        int[] arr = { 12, 34, 54, 2, 3 };
        Console.WriteLine("Αρχικός πίνακας:");
        Console.WriteLine(string.Join(", ", arr));

        ShellSort(arr);

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

Πώς Λειτουργεί ο Κώδικας

  1. ShellSort: Υλοποιεί τον αλγόριθμο.
    • Ξεκινά με gap ίσο με το μισό του μήκους του πίνακα.
    • Επαναλαμβάνει τη διαδικασία μέχρι το gap να γίνει 0.
  2. Εσωτερικός Βρόχος: Εκτελεί την ταξινόμηση Insertion Sort με το συγκεκριμένο gap.

Παράδειγμα

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

  1. Αρχικός πίνακας: {12, 34, 54, 2, 3}
  2. Πρώτη Επανάληψη (gap = 2):
    • Ταξινομούμε: {12, 34} και {2, 3}.
    • Ο πίνακας γίνεται: {2, 3, 54, 12, 34}.
  3. Δεύτερη Επανάληψη (gap = 1): Κανονική Insertion Sort.
    • Ο τελικός πίνακας γίνεται: {2, 3, 12, 34, 54}.

Συμπέρασμα

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