Prove Correctness of Quicksort Algorithm Partition Function

[mathmari]

Hey!

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

    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)

 

[johng1]

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.