# What is Selection Sort - Median

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from an unsorted list and placing it at the beginning of the list. The algorithm maintains two sublists: the sorted sublist and the unsorted sublist.

The algorithm works by iterating through the unsorted sublist, finding the smallest element, and swapping it with the first element of the unsorted sublist. This places the smallest element in the correct position in the sorted sublist. Then, the algorithm repeats this process with the remaining unsorted sublist until the entire list is sorted.

Median finding selection sort is another variation of the selection sort algorithm that is designed to find the median of a list of elements. It works by repeatedly selecting a pivot element from the unsorted sublist, partitioning the list into two sublists, and then recursively applying the same process to the appropriate sublist that contains the median element.

The algorithm starts by selecting a pivot element from the unsorted sublist, and then partitioning the list into two sublists: one containing elements smaller than the pivot and one containing elements greater than the pivot. If the pivot element happens to be the median of the list, the algorithm returns it as the median. Otherwise, the algorithm continues recursively on the appropriate sublist that contains the median element.

The median finding selection sort algorithm has a worst-case time complexity of O(n^2), but in practice, it often performs better than other algorithms that are designed specifically to find the median, such as the quickselect algorithm. This is because the median finding selection sort algorithm has a simpler implementation and requires less memory overhead.

However, like other selection sort algorithms, the median finding selection sort algorithm is still relatively inefficient for large lists and is typically not used in production systems.

## Who invented it?

The median selection sort algorithm was invented by C.A.R. Hoare, a British computer scientist who is also known for inventing the Quicksort algorithm. Hoare introduced the median finding algorithm in a 1961 paper titled "Algorithm 64: Quicksort," where he described how to use a similar partitioning approach to find the median of a list of elements.

Hoare's median finding algorithm works by selecting a pivot element from the unsorted sublist, partitioning the list into two sublists, and then recursively applying the same process to the appropriate sublist that contains the median element. This algorithm is sometimes referred to as "QuickSelect," as it is a variant of the Quicksort algorithm.

## Pseudocode

```
function median_selection_sort(A, left, right, k):
if left = right:
return A[left]
pivot_index = randomized_partition(A, left, right)
length = pivot_index - left + 1
if k = length:
return A[pivot_index]
else if k < length:
return median_selection_sort(A, left, pivot_index - 1, k)
else:
return median_selection_sort(A, pivot_index + 1, right, k - length)
function randomized_partition(A, left, right):
i = random(left, right)
swap(A[i], A[right])
return partition(A, left, right)
function partition(A, left, right):
pivot_value = A[right]
i = left - 1
for j from left to right - 1:
if A[j] < pivot_value:
i++
swap(A[i], A[j])
swap(A[i+1], A[right])
return i+1
```

- In this algorithm, A is the input array to be sorted, left and right are the left and right indices of the sublist to be sorted, and k is the index of the median element to be found.
- The median_selection_sort function is a recursive function that repeatedly partitions the array around a randomly selected pivot element, and then recursively applies the same process to the appropriate sublist that contains the median element. The algorithm first selects a random pivot element using the randomized_partition function, and then partitions the array into two subarrays: one containing elements smaller than the pivot and one containing elements greater than the pivot. It then compares the length of the left subarray with the desired index k and continues recursively on the appropriate subarray that contains the median element.
- The randomized_partition function selects a random pivot element from the sublist and partitions the array into two subarrays using the partition function. The partition function selects the last element of the sublist as the pivot element and partitions the array into two subarrays: one containing elements smaller than the pivot and one containing elements greater than the pivot.

## Sample Code

```
// C++ code snippet
int median_selection(int arr[], int l, int r, int k) {
if (l == r) {
return arr[l];
}
int pivot = arr[l + rand() % (r - l + 1)]; // choose a random pivot
int i = l, j = r;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
if (k <= j) {
return median_selection(arr, l, j, k);
}
else if (k >= i) {
return median_selection(arr, i, r, k);
}
else {
return arr[k];
}
}
void median_selection_sort(int arr[], int n) {
int mid = n / 2;
int median = median_selection(arr, 0, n-1, mid);
// partition the array into elements <= median and elements > median
int i = 0, j = n-1;
while (i < j) {
while (arr[i] < median) {
i++;
}
while (arr[j] > median) {
j--;
}
if (i < j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
// recursively sort the two partitions
if (j > 0) {
median_selection_sort(arr, j+1);
}
if (i < n-1) {
median_selection_sort(arr+i, n-i);
}
}
int main() {
int arr[] = {4, 2, 6, 1, 7, 3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
median_selection_sort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```

```
# Python code snippet
import random
def median_selection(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr) # choose a random pivot
left = [x for x in arr if x < pivot]
right = [x for x in arr if x > pivot]
mid = [x for x in arr if x == pivot]
if k < len(left):
return median_selection(left, k)
elif k < len(left) + len(mid):
return mid[0]
else:
return median_selection(right, k - len(left) - len(mid))
def median_selection_sort(arr):
mid = len(arr) // 2
median = median_selection(arr, mid)
# partition the array into elements <= median and elements > median
i, j = 0, len(arr)-1
while i <= j:
while arr[i] < median:
i += 1
while arr[j] > median:
j -= 1
if i <= j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
# recursively sort the two partitions
if j > 0:
median_selection_sort(arr[:j+1])
if i < len(arr)-1:
median_selection_sort(arr[i:])
arr = [4, 2, 6, 1, 7, 3, 5]
median_selection_sort(arr)
print(arr)
```

```
import java.util.Random;
public class MedianSelectionSort {
public static int medianSelection(int[] arr, int k) {
if (arr.length == 1) {
return arr[0];
}
Random rand = new Random();
int pivot = arr[rand.nextInt(arr.length)]; // choose a random pivot
int[] left = new int[arr.length];
int[] right = new int[arr.length];
int[] mid = new int[arr.length];
int leftCount = 0, rightCount = 0, midCount = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left[leftCount++] = arr[i];
}
else if (arr[i] > pivot) {
right[rightCount++] = arr[i];
}
else {
mid[midCount++] = arr[i];
}
}
if (k < leftCount) {
return medianSelection(left, k);
}
else if (k < leftCount + midCount) {
return mid[0];
}
else {
return medianSelection(right, k - leftCount - midCount);
}
}
public static void medianSelectionSort(int[] arr) {
int mid = arr.length / 2;
int median = medianSelection(arr, mid);
// partition the array into elements <= median and elements > median
int i = 0, j = arr.length-1;
while (i <= j) {
while (arr[i] < median) {
i++;
}
while (arr[j] > median) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// recursively sort the two partitions
if (j > 0) {
int[] left = new int[j+1];
System.arraycopy(arr, 0, left, 0, j+1);
medianSelectionSort(left);
}
if (i < arr.length-1) {
int[] right = new int[arr.length-i];
System.arraycopy(arr, i, right, 0, arr.length-i);
medianSelectionSort(right);
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 6, 1, 7, 3, 5};
medianSelectionSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
```

## Time and Space Complexity

The time complexity of median selection is O(n), where n is the number of elements in the input array. This is because algorithm use a partitioning step to split the array into two parts based on a pivot element, and the partitioning step takes O(n) time in the worst case.

The space complexity of median selection is O(n) in the worst case, since the algorithm creates three auxiliary arrays to store the elements less than, equal to, and greater than the pivot. In practice, the space complexity is usually less than O(n) since the algorithm only recurses on one of the two partitions.

## Advantages

- The main advantage of median selection is that it has a worst-case time complexity of O(n), which is faster than many other sorting and selection algorithms that have worst-case time complexity of O(nlogn). Median selection also has a relatively low space complexity, especially compared to some divide-and-conquer algorithms like merge sort and quicksort that require O(n) additional memory.
- Another advantage of median selection is that it can be used as a subroutine in other algorithms, such as quicksort, to improve their worst-case performance. By using median selection to choose the pivot element, quicksort can achieve an average-case time complexity of O(nlogn) while still maintaining a worst-case time complexity of O(n^2) in rare cases.

## Disadvantages

- The main disadvantage of median selection is that it can be relatively slow in practice compared to simpler algorithms like quicksort and heapsort, especially for small input sizes. This is because the overhead of the partitioning step and the recursive calls can add up, and the algorithm requires more comparisons and memory accesses than simpler algorithms. Additionally, the worst-case time complexity of median selection is only guaranteed to be O(n) if the pivot element is chosen optimally at each step, which can be difficult to achieve in practice.