Selection Algorithms problems

Q1: Find kth smallest/ largest element in the data using Quickselect selection algorithm.

Ans:

import random

def partition(arr, low, high):
   # Choose a random pivot index and swap the pivot with the element at the high index
   pivot_index = random.randint(low, high)
   pivot = arr[pivot_index]
   arr[pivot_index], arr[high] = arr[high], arr[pivot_index]

   # Initialize a pointer i to keep track of the boundary between elements less than and greater than the pivot
   i = low - 1
   
   # Iterate through the array and move elements smaller than or equal to the pivot to the left side
   for j in range(low, high):
       if arr[j] <= pivot:
           i += 1
           arr[i], arr[j] = arr[j], arr[i]

   # Place the pivot in its correct position and return its index
   arr[i + 1], arr[high] = arr[high], arr[i + 1]
   return i + 1

def quickselect(arr, low, high, k):
   # Recursively select the kth smallest element using the partition function
   if low <= high:
       pivot_index = partition(arr, low, high)
       
       # If the pivot index is equal to k, return the pivot element
       if pivot_index == k:
           return arr[pivot_index]
       # If the pivot index is less than k, search the right subarray
       elif pivot_index < k:
           return quickselect(arr, pivot_index + 1, high, k)
       # If the pivot index is greater than k, search the left subarray
       else:
           return quickselect(arr, low, pivot_index - 1, k)

def kth_smallest(arr, k):
   # Check if the value of k is valid, then call quickselect with appropriate parameters
   if k > 0 and k <= len(arr):
       return quickselect(arr, 0, len(arr) - 1, k - 1)
   else:
       return "Invalid value of k"

# Example usage:
my_list = [5, 2, 9, 1, 5, 6]
k = 3
kth_smallest_number = kth_smallest(my_list, k)
print(f"{k}th smallest number:", kth_smallest_number)

Q2. Find kth smallest/largest item using median of medians algorithm.

Ans:

1. Kth smallest item:

def median_of_medians_algo(nums, k):
    
    # Partition Phase:
    
    #  Split original data into chunks of 5 items
    chunks = [nums[i:i+5] for i in range(0, len(nums), 5)]
    
    #find medians of each of these chunks
    medians = [sorted(chunk)[len(chunk)//2 ]for chunk in chunks]
    
    # pivot_val = median(medians)
    pivot_val = sorted(medians)[len(medians)//2]
    
    # Split original data into left & right lists based on comparison with pivot_val
    left_list = [val for val in nums if val < pivot_val]
    right_list = [val for val in nums if val > pivot_val]
    
    # Selection Phase
    
    pivot_idx = len(left_list)
    
    if k < pivot_idx:  # to find kth smallest number
        return median_of_medians_algo(left_list, k)
    elif k > pivot_idx:  # to find kth largest number
        return median_of_medians_algo(right_list, k-pivot_idx-1)
    else:
        return pivot_val


nums = [1, -5, 0, 10, 15, 20, 3, -1, 21, 22, 23, 24, 25, 26, 27, 28, 29]
k = 2
print(median_of_medians_algo(nums, k-1))

2. To find Kth largest item:

def median_of_medians_algo(nums, k):
    
    # Partition Phase:
    
    # Split original data into chunks of 5 items
    chunks = [nums[i:i+5] for i in range(0, len(nums), 5)]
    
    # Find medians of each of these chunks
    medians = [sorted(chunk)[len(chunk)//2] for chunk in chunks]
    
    # Pivot value is the median of medians
    pivot_val = sorted(medians)[len(medians)//2]
    
    # Split original data into left & right lists based on comparison with pivot_val
    left_list = [val for val in nums if val < pivot_val]
    right_list = [val for val in nums if val > pivot_val]
    
    # Selection Phase
    pivot_idx = len(left_list)
    
    if k < pivot_idx:  # To find kth smallest number
        return median_of_medians_algo(left_list, k)
    elif k > pivot_idx:  # To find kth largest number
        return median_of_medians_algo(right_list, k - pivot_idx - 1)
    else:
        return pivot_val

nums = [1, -5, 0, 10, 15, 20, 3, -1, 21, 22, 23, 24, 25, 26, 27, 28, 29]
k = 2
print(median_of_medians_algo(nums, len(nums) - k))  # Adjust k for 1-indexing