For the Quicksort algorithm below do the following

. Prove that no matter how you choose the pivot, the algorithm always outputs correctly. (Do this by induction). Write a short program (C++ code) for the following function void Pivot( int * a, int n, int p) where a is an integer array of n elements, p is an index in 10,1,.. . ,n 1. You can assume that every element in a is different from the others. This function selects alp as the pivot and would like to make the array a into the form SL