Median-of-3 Method

The median-of-3 method is a pivot selection strategy used by some sorting algorithms such as quicksort. It helps avoid poor pivots by choosing the median of the first, middle, and last elements as the pivot.

The algorithm is:

1. Consider first, middle and last elements of array

2. Sort them and pick median value as pivot

3. Proceed with partitioning algorithm using chosen pivot

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int partition(int[] arr, int low, int high) {
  
  int mid = low + (high - low) / 2;

  // Median of 3 pivot selection
  int pivot = medianOf3(arr[low], arr[mid], arr[high]);  

  while (low <= high) {
    // Partitioning logic
  }
  return partitionIndex;
}

int medianOf3(int a, int b, int c) {
  // Return median of 3 values
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int partition(vector<int>& arr, int low, int high) {

  int mid = low + (high - low) / 2;

  // Median of 3 pivot selection
  int pivot = medianOf3(arr[low], arr[mid], arr[high]);

  while (low <= high) {
    // Partitioning logic
  }

  return partitionIndex;
}

int medianOf3(int a, int b, int c) {
  // Return median of 3 values  
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def partition(arr, low, high):

  mid = (low + high) // 2
  
  pivot = median_of_3(arr[low], arr[mid], arr[high])

  while low <= high: 
    # Partitioning logic

  return partition_index

def median_of_3(a, b, c):
  # Return median of 3 values

Median-of-3 helps improve pivot selection and performance of quicksort, especially on nearly sorted data.

The median-of-3 method is a technique commonly used to improve the efficiency of sorting algorithms, notably Quicksort. The idea is to select a pivot by taking the median of the first, middle, and last elements of the array. This approach aims to minimize the chances of choosing a bad pivot, thus reducing the likelihood of experiencing the worst-case time complexity. The key takeaway is that the median-of-3 method improves the average case performance by making a more informed choice of the pivot.

Java Code for Median-of-3 Method

In Java, you can implement the median-of-3 method like this:

1
2
3
4
5
6
7

public class MedianOfThree {
    public static int median(int a, int b, int c) {
        int max = Math.max(Math.max(a, b), c);
        int min = Math.min(Math.min(a, b), c);
        return a + b + c - max - min;
    }
}

1. The median function takes three integers a, b, and c, and returns the median among them.

C++ Code for Median-of-3 Method

In C++, the implementation could look something like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <algorithm>

class MedianOfThree {
public:
    static int median(int a, int b, int c) {
        int maxVal = std::max({a, b, c});
        int minVal = std::min({a, b, c});
        return a + b + c - maxVal - minVal;
    }
};

1. The median function uses the <algorithm> header to find the maximum and minimum among a, b, and c and then calculates the median.

Python Code for Median-of-3 Method

In Python, you can implement the median-of-3 method as follows:

1
2

def median(a, b, c):
    return a + b + c - max(a, b, c) - min(a, b, c)

1. The median function uses Python’s built-in max and min functions to find the maximum and minimum values among a, b, and c.

In each implementation, the function calculates the median by summing the three numbers and subtracting the maximum and minimum. This leaves the median, which is then returned. This operation is often used as a pre-step in sorting algorithms like Quicksort to choose a better pivot.