C# Learning

Ψευδογλώσσα

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

Διαδικασία Τυχαία_Ταξινόμηση(πίνακας, αρχή, τέλος)
    Αν αρχή >= τέλος τότε
        Επιστροφή
    Τέλος_αν
    
    πιλότος <- Τυχαία_Επιλογή(πίνακας, αρχή, τέλος)
    Ανταλλαγή(πίνακας, πιλότος, τέλος)
    
    διαχωρισμένο_δείκτη <- Διαχωρισμός(πίνακας, αρχή, τέλος)
    
    Τυχαία_Ταξινόμηση(πίνακας, αρχή, διαχωρισμένο_δείκτη - 1)
    Τυχαία_Ταξινόμηση(πίνακας, διαχωρισμένο_δείκτη + 1, τέλος)
Τέλος_Διαδικασίας

C#

Ακολουθεί η υλοποίηση του Randomized QuickSort σε C#.

using System;

class Program
{
    static void Main()
    {
        int[] array = { 38, 27, 43, 3, 9, 82, 10 };
        RandomizedQuickSort(array, 0, array.Length - 1);
        
        Console.WriteLine("Sorted array: " + string.Join(", ", array));
    }

    static void RandomizedQuickSort(int[] array, int left, int right)
    {
        if (left >= right) return;

        int pivotIndex = RandomizedPartition(array, left, right);
        RandomizedQuickSort(array, left, pivotIndex - 1);
        RandomizedQuickSort(array, pivotIndex + 1, right);
    }

    static int RandomizedPartition(int[] array, int left, int right)
    {
        Random rand = new Random();
        int pivotIndex = rand.Next(left, right + 1);
        Swap(array, pivotIndex, right); // Move pivot to end

        int pivot = array[right];
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                Swap(array, i, j);
            }
        }
        Swap(array, i + 1, right); // Move pivot to its final place
        return i + 1;
    }

    static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Συναρτήσεις

• Τυχαία_Επιλογή(πίνακας, αρχή, τέλος): Επιστρέφει έναν τυχαίο δείκτη μεταξύ αρχής και τέλους.
• Ανταλλαγή(πίνακας, i, j): Ανταλλάσσει τα στοιχεία i και j στον πίνακα.
• Διαχωρισμός(πίνακας, αρχή, τέλος): Διαιρεί τον πίνακα με βάση τον πιλότο και επιστρέφει τη θέση του.

Συμπέρασμα

Οι αλγόριθμοι τυχαίοποίησης είναι ισχυρά εργαλεία για την επίλυση προβλημάτων και χρησιμοποιούνται ευρέως σε διάφορες εφαρμογές. Με την κατανόηση της λογικής τους και την ικανότητα υλοποίησής τους σε γλώσσες προγραμματισμού όπως η C#, μπορείς να δημιουργήσεις αποδοτικούς και ευέλικτους αλγόριθμους για πολλά προβλήματα

Επεξήγηση

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

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

• Πλεονεκτήματα:
  • Συχνά πιο αποδοτικοί και απλοί από τους καθοριστικούς αλγορίθμους.
  • Καλή απόδοση κατά μέσο όρο.
• Μειονεκτήματα:
  • Δεν εγγυώνται πάντα την καλύτερη απόδοση (π.χ. μπορεί να έχουν χειρότερη περίπτωση).
  • Μπορεί να απαιτούν επιπλέον υπολογιστικούς πόρους (π.χ. τυχαίους αριθμούς).