ভূমিকা
একটি আনসোর্টেড লিস্ট থেকে k-তম বড় এলিমেন্ট (k-th largest) বের করার জন্য কুইকসিলেক্ট (Quickselect) অ্যালগরিদম ব্যবহার করা হয়, যার এভারেজ টাইম কমপ্লেক্সিটি O(n)। এটি কুইকসোর্টের পার্টিশন লজিকের সাদৃশ্য।
উদাহরণ কোড
def select_largest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = end - pivot_val
if i < k:
return select_largest(my_list, pivot_val + 1, end, i)
elif i > k:
return select_largest(my_list, beg, pivot_val, 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_largest = select_largest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_largest))
আউটপুট
Enter the list of numbers.. 34 67 12 0 999 Enter the value for i.. 1 The result is 999.
ব্যাখ্যা
select_largest: রিকার্সিভ ফাংশন।i= k-তম বড় (1-বেসড)।start_partition: হোয়ারের পার্টিশন স্কিম (Hoare's partition)। পিভট = প্রথম এলিমেন্ট। دو পয়েন্টারi(বাম) এবংj(ডান) থেকে স্ক্যান করে পিভটের সঠিক পজিশন বের করে।k = end - pivot_val: পিভটের ডান পাশে (বড় মানগুলোর পাশে) কতগুলো এলিমেন্ট আছে।যদি
i < k: কাঙ্ক্ষিত এলিমেন্ট ডান পাশে, সেখানে রিকার্সন।যদি
i > k: বাম পাশে, এডজাস্টেডiদিয়ে রিকার্সন।যদি
i == k: পিভটই কাঙ্ক্ষিত এলিমেন্ট।
দ্রষ্টব্য
ইনপুট
i=1মানে সবচেয়ে বড় (1st largest)।i=2মানে ২য় বড়।ওয়ার্স্ট কেস O(n²) (পিভট খারাপ হলে)। র্যান্ডোমাইজড পিভট ব্যবহার করলে এভারেজ O(n) নিশ্চিত।
পাইথনে বিল্ট-ইন:
heapq.nlargest(k, lst)[-1]বাsorted(lst, reverse=True)[k-1](O(n log n))।
