ভূমিকা
একটি আনসোর্টেড লিস্ট থেকে k-তম ছোট এলিমেন্ট (k-th smallest) বের করার জন্যও কুইকসিলেক্ট (Quickselect) অ্যালগরিদম ব্যবহার করা হয়। এটি পূর্বের "n-তম বড়" সমস্যার মিরর ইমেজ।
উদাহরণ কোড
def select_smallest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = pivot_val - beg + 1
if i < k:
return select_smallest(my_list, beg, pivot_val, i)
elif i > k:
return select_smallest(my_list, pivot_val + 1, end, i - k)
return my_list[pivot_val]
def start_partition(my_list, beg, end):
pivot_val = my_list[beg]
i = beg + 1
j = end - 1
while True:
while (i <= j and my_list[i] <= pivot_val):
i = i + 1
while (i <= j and my_list[j] >= pivot_val):
j = j - 1
if i <= j:
my_list[i], my_list[j] = my_list[j], my_list[i]
else:
my_list[beg], my_list[j] = my_list[j], my_list[beg]
return j
my_list = input('Enter the list of numbers.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('Enter the value for i.. '))
ith_smallest = select_smallest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_smallest))
আউটপুট
Enter the list of numbers.. 43 12 67 89 99 0 Enter the value for i.. 3 The result is 43.
ব্যাখ্যা
select_smallest:i= k-তম ছোট (1-বেসড)।start_partition: একই হোয়ার্স পার্টিশন।k = pivot_val - beg + 1: পিভটের বাম পাশে (ছোট মানগুলোর পাশে) কতগুলো এলিমেন্ট আছে (+১ পিভট নিজে)।যদি
i < k: বাম পাশে রিকার্সন।যদি
i > k: ডান পাশে এডজাস্টেডiদিয়ে রিকার্সন।উদাহরণে লিস্ট: [43, 12, 67, 89, 99, 0]। সর্টেড: [0, 12, 43, 67, 89, 99]। ৩য় ছোট = 43।
পাইথন বিল্ট-ইন বিকল্প
import heapq # k-th smallest kth_smallest = heapq.nsmallest(k, my_list)[-1] # k-th largest kth_largest = heapq.nlargest(k, my_list)[-1] # বা সর্ট করে kth_smallest = sorted(my_list)[k-1]
হিপ-ভিত্তিক পদ্ধতি O(n log k), সর্টিং O(n log n)। কুইকসিলেক্ট এভারেজ O(n)।
