Η κατανόηση της απόδοσης του περιλαμβάνει την ανάλυση του αναμενόμενου αριθμού συγκρίσεων και swaps κατά τη διάρκεια της εκτέλεσης. Αυτό το άρθρο διερευνά τις μαθηματικές αρχές πίσω από αυτές τις προσδοκίες, εστιάζοντας στην προβαμπιλιστική ανάλυση του Quicksort.

Αναμενόμενος αριθμός συγκρίσεων

Ο αναμενόμενος αριθμός συγκρίσεων στην Quicksort εξαρτάται από την επιλογή του στροφέα και τη διαδικασία κατατμήσεως. Υποθέτοντας ότι όλες οι μετατροπές είναι εξίσου πιθανές, η μέση περίπτωση μπορεί να αναλυθεί με τη χρήση αναδρομικών εξισώσεων. Για μια σειρά μεγέθους n, οι αναμενόμενες συγκρίσεις, που υποδηλώνονται ως [C(n), ικανοποιούν την επανάληψη:

C(n) = n - 1 + frac {1}{n} sum {k=0} {n-1} [C(k) + C(n - 1 - k]

Αυτή η επανάληψη απλοποιείται σε ένα γνωστό αποτέλεσμα: C(n) ⁇ 2n Inn n για μεγάλα n. Η παραγωγή περιλαμβάνει συσπείρωση όλων των πιθανών θέσεων περιστροφής και εφαρμογή ιδιοτήτων αρμονικών αριθμών.

Αναμενόμενος αριθμός ανταλλακτικών

Οι εναλλαγή σε Quicksort συμβαίνουν κατά τη διαδικασία κατατμήσεως. Ο αναμενόμενος αριθμός των swaps σχετίζεται με τον αριθμό των συγκρίσεων και την κατανομή των επιλογών στροφών. Υπό ομοιόμορφη τυχαία εξέλιξη, οι αναμενόμενες swaps, που υποδηλώνονται ως S(n), μπορούν να προσεγγιστούν αναλύοντας τα βήματα κατατμήσεως.

Κάθε βήμα κατάτμησης περιλαμβάνει την ανταλλαγή στοιχείων για να εξασφαλιστεί η σωστή τοποθέτηση του άξονα. Οι αναμενόμενες ανταλλαγές ανά κατάτμηση είναι ανάλογες με το μέγεθος των υποενοτήτων. Συνδυάζοντας όλες τις αναδρομικές κλήσεις δίνει μια προσέγγιση: S(n) ⁇ nIn n.

Περίληψη των προσδοκιών

  • Συνδυασμοί: Περίπου 2n Inn n for large n.
  • Κράματα: Περίπου n Inn n για μεγάλα n.
  • Και οι δύο μετρήσεις αναπτύσσονται λογαριθμικά με μέγεθος συστοιχίας, αντανακλώντας την απόδοση της Quicksort.