MHB Prove Correctness of Quicksort Algorithm Partition Function

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
To prove the correctness of the Partition function in the Quicksort algorithm, it is essential to articulate a precise statement that holds true after the algorithm's execution. This involves demonstrating that the elements in the array are correctly partitioned around a chosen pivot, ensuring that all elements less than the pivot are on one side and all elements greater than or equal to it are on the other. The discussion references a version of the partition algorithm from Wikipedia and suggests that, with minor adjustments, the presented algorithm remains one of the most efficient known for partitioning. The focus is on understanding the correctness proof rather than the algorithm's efficiency, emphasizing the need for a clear and verifiable statement regarding the algorithm's outcome.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to prove the correctness of the function Partition of the Quicksort algorithm.

Code:
    begin
     i<-f
     j<-l
     while i<=j do
        begin
         while A[j]>=a and j>=f do j<-j-1;
         while A[i]<a and i<=l do i<-i+1;
         if i<j then 
            begin
              interchange A[i] and A[j];
              i<-i+1;
              j<-j-1;
            end
       end
    end

What am I supposed to do?? (Wondering)

What does it mean to prove the correctness?? (Wondering)
 
Technology news on Phys.org
To prove correctness of an algorithm, you must first state precisely a statement that is true after execution of the algorithm and then prove this statement. There are many different versions of the partition algorithm. I took the following from Wikipedia. Here's a proof of that algorithm. Now you should have a go at your algorithm. BTW, with a few tweaks I believe that the algorithm you described is still the most efficient partitioning algorithm known.

2gtq3rn.png

e0h91c.png
 
Last edited:
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Back
Top