Write Quicksort Algorithm using last element as pivot element. Apply this algorithm to sort the following list of array element. Show action step by step. 23, 12, -7, 16, 18, 35, 35, 28, 5

Quick Sort

• This algorithm follows the Divide and Conquer approach.
• Divide and conquer is a technique of breaking down the algorithms into subproblems, then solving the subproblems, and combining the results back together to solve the original problem.
• Quick Sort is a Recursive algorithm.
• It divides the given array into two sections using a partitioning element called a pivot.
• The division performed is such that
  • All the elements to the left side of the pivot are smaller than the pivot.
  • All the elements to the right side of the pivot are greater than the pivot.
• Picking a good pivot is necessary for the fast implementation of quicksort.
• Some of the ways of choosing a pivot are as follows:
  • Pivot can be random, i.e. select the random pivot from the given array.
  • Pivot can either be the rightmost element or the leftmost element of the given array.
  • Select median as the pivot element.

Algorithm of Quick Sort -

Step 1 − Choose the high-index Pivot.

Step 2 − Take two variables to point Left and Right of the list excluding Pivot.

Step 3 − Left points to the low index.

Step 4 − Right points to the high index.

Step 5 − If the value at the Left is less than the pivot move in the right direction.

Step 6 − If the value at the Right is greater than the pivot move in the left direction.

Step 7 − If both step 5 and step 6 do not match SWAP Left and Right.

Step 8 − If left ≥ right, the point where they met is a new pivot. Checks the value of old and new Pivots whether there is a need for Swapping or not.

Let's solve the given example using Quick Sort: