Question

Show the first partition of quicksort using median of three numbers technique for the pivot element. Circle the pivot. Show step by step of your work.

23     5     27   25   9   7    11   19   17    1    29      3    21      13

Answer 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 -> Index values 23 5 27 25 9 7 11 19 17 1 29 3 21 13 -> Given list Pivot - 11 [index - 6]

STEP BY STEP SOLUTION:

1. Select the leftmost index value of the 1st number which is "0" and the rightmost index value which is 13

2. Calculate the median. Sum the index values (0+13). If the sum is an odd number which is true in this case, then add 1 to the sum and divide the final number by 2.

   So, the median here would be (13+1)/2 = 7 (i.e. the 7th index value starting from the leftmost value which is 11 in this case)

3. Now We will compare the three numbers using the index values and based on the below defined conditions:
       left - 0 (value 23)
       right - 13 (value 13)
       mid - 7 (value 11)
      
       Conditions -
           1. if right < left then we will swap the values
           2. if mid < left then we will swap the values
           3. if right < mid then we will swap the values
     
4. Once the first iteration is completed then we ill return the "median" value.

5. Do the first four steps in recursive manner.

Below is the sample code -
  
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on

int mdeianofthree(arr, left, right)
{
   mid = (left + right)/2
       if (arr[right] < arr[left])
           {
               Swap(arr, left, right);
           }
       if (arr[mid] < arr[left])
           {
               Swap(arr, mid, left);
           }
       if arr[right] < arr[mid]:
           {
               Swap(arr, right, mid);
           }
       return mid;
   }
  
void Swap(arr, left, right)
{
       temp = arr[left];
       arr[left] = arr[right];
       arr[right] = temp;
      
   }