Ο Quick Sort είναι ένας αλγόριθμος διαίρεσης και κατάκτησης. Η βασική ιδέα είναι να διαλέξουμε ένα στοιχείο από τον πίνακα ως “pivot” και να τοποθετήσουμε όλα τα στοιχεία μικρότερα από το pivot στα αριστερά του και όλα τα μεγαλύτερα στα δεξιά του. Στη συνέχεια, εφαρμόζουμε αναδρομικά την ίδια διαδικασία στους δύο υποπίνακες (αριστερό και δεξιό).

Βήματα:

  1. Επιλέγουμε ένα στοιχείο ως pivot.
  2. Χωρίζουμε τον πίνακα σε δύο μέρη: αριστερά από το pivot (στοιχεία μικρότερα από το pivot) και δεξιά από το pivot (στοιχεία μεγαλύτερα από το pivot).
  3. Επαναλαμβάνουμε αναδρομικά την ίδια διαδικασία για τους δύο υποπίνακες.

Ψευδογλώσσα για Quick Sort

ΣΥΝΑΡΤΗΣΗ QuickSort(ΠΙΝΑΚΑΣ, αρχή, τέλος)
    ΑΝ αρχή < τέλος ΤΟΤΕ
        pivotIndex <- Διαχωρισμός(ΠΙΝΑΚΑΣ, αρχή, τέλος)
        QuickSort(ΠΙΝΑΚΑΣ, αρχή, pivotIndex - 1)
        QuickSort(ΠΙΝΑΚΑΣ, pivotIndex + 1, τέλος)
    ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

ΣΥΝΑΡΤΗΣΗ Διαχωρισμός(ΠΙΝΑΚΑΣ, αρχή, τέλος)
    pivot <- ΠΙΝΑΚΑΣ[τέλος]
    i <- αρχή - 1
    ΓΙΑ j ΑΠΟ αρχή ΜΕΧΡΙ τέλος - 1
        ΑΝ ΠΙΝΑΚΑΣ[j] <= pivot ΤΟΤΕ
            i <- i + 1
            ΑΝΤΑΛΛΑΓΗ(ΠΙΝΑΚΑΣ[i], ΠΙΝΑΚΑΣ[j])
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΓΙΑ
    ΑΝΤΑΛΛΑΓΗ(ΠΙΝΑΚΑΣ[i + 1], ΠΙΝΑΚΑΣ[τέλος])
    ΕΠΙΣΤΡΟΦΗ i + 1
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Επεξήγηση του κώδικα σε C#

  1. QuickSort Μέθοδος: Η QuickSort μέθοδος καλείται αναδρομικά για να ταξινομήσει τον πίνακα. Χωρίζει τον πίνακα σε δύο υποπίνακες και εφαρμόζει τον αλγόριθμο σε καθέναν από αυτούς.

  2. Partition Μέθοδος: Η Partition μέθοδος διαχωρίζει τον πίνακα γύρω από ένα pivot. Το pivot επιλέγεται ως το τελευταίο στοιχείο του υποπίνακα. Ο αλγόριθμος τοποθετεί όλα τα στοιχεία μικρότερα από το pivot στα αριστερά του και τα μεγαλύτερα στα δεξιά του.

  3. Swap Μέθοδος: Η Swap μέθοδος ανταλλάσσει δύο στοιχεία στον πίνακα.

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

Quick-SortDownload

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

using System;

class Program
{
    static void Main()
    {
        int[] array = { 34, 7, 23, 32, 5, 62 };
        QuickSort(array, 0, array.Length - 1);
        
        Console.WriteLine("Ταξινομημένος Πίνακας:");
        foreach (var item in array)
        {
            Console.Write(item + " ");
        }
    }

    static void QuickSort(int[] array, int low, int high)
    {
        if (low < high)
        {
            int pivotIndex = Partition(array, low, high);
            QuickSort(array, low, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, high);
        }
    }

    static int Partition(int[] array, int low, int high)
    {
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                Swap(ref array[i], ref array[j]);
            }
        }
        Swap(ref array[i + 1], ref array[high]);
        return i + 1;
    }

    static void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
}