Question

1.)What are the major properties of quicksort?

2.)Is quicksort considered stable and adaptive?

3.)What is the worst case number of comparisons and number of swaps for quicksort? Provide the Big-O notation for the mathematical function for quicksort worst case.

4.)What is the average case number of comparisons and number of swaps for quicksort? Provide the Big-O notation for the mathematical function for quicksort average cases.

Answer 1

1)

. Invented in 1960 by Tony Hoare, and in the top 10 algorithms of all time Best/ average performance is O(n log n) Worst can be O(n2) .Space efficient Data can be sorted in-place Does not require additional auxiliary arrays for temporary storage (*c.f. merge sort) Fragile/sensitive Care must be taken to avoid worst case situations

Divide Call Quicksort on an array - Decide where to divide by choosing a pivot value - Partition array into two sub-arrays - All values of 1st sub-array are < pivot value All values of 2nd sub-array are > pivot value Calculate position of pivot Conquer sort both sub-arrays by independent recursive calls to Quicksort (see above)

2)

No, quicksort is considered an unstable algorithm.

3)

Worst Case input for maximum number of swaps will be already sorted array in decreasing order.

Recurrence for Total number of swaps in this case :
T(n) = T(n-1) + O(n) // O(n) swaps will occur in alternate calls to partition algorithm.
= O(n²)

Similarly, the worst case of comparisons takes place when the array is sorted in the reverse order.

Number of comparisons = O(n²)

NOTE: As per HOMEWORKLIB POLICY, I am allowed to answer only 3 questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.