যখন রৈখিক সময় জটিলতার তালিকা থেকে nতম ক্ষুদ্রতম উপাদান নির্বাচন করার প্রয়োজন হয়, তখন দুটি পদ্ধতির প্রয়োজন হয়। ক্ষুদ্রতম উপাদান খুঁজে বের করার একটি পদ্ধতি, এবং আরেকটি পদ্ধতি যা তালিকাটিকে দুটি ভাগে ভাগ করে। এই বিভাজন ব্যবহারকারীর দেওয়া 'i' মানের উপর নির্ভর করে। এই মানের উপর ভিত্তি করে, তালিকা বিভক্ত করা হয়, এবং ক্ষুদ্রতম উপাদান নির্ধারণ করা হয়।
নীচে একই -
এর একটি প্রদর্শন রয়েছে৷উদাহরণ
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' মানকে প্যারামিটার হিসেবে নেওয়া হয়।
-
'start_partition' নামের আরেকটি পদ্ধতি সংজ্ঞায়িত করা হয়েছে যা 'i'-এর মানের উপর নির্ভর করে তালিকাটিকে দুটি ভাগে ভাগ করে।
-
এই পদ্ধতিটিকে বলা হয় 'slect_smallest' পদ্ধতিতে৷
৷ -
'select_smallest' একই ফাংশনের ভিতরে আবার বলা হয়- এইভাবে পুনরাবৃত্তি কাজ করে।
-
সংখ্যাগুলি ব্যবহারকারীর কাছ থেকে ইনপুট হিসাবে নেওয়া হয়৷
-
এটি ডিফল্ট মানের উপর ভিত্তি করে বিভক্ত।
-
এটা আবার পুনরাবৃত্তি করা হয়।
-
'i'-এর একটি মান ব্যবহারকারীর কাছ থেকে নেওয়া হয়।
-
এই 'i' মানের উপর ভিত্তি করে, তালিকাটি দুটি ভাগে বিভক্ত।
-
তালিকার একটিতে 'slect_smallest' পদ্ধতি বলা হয়।
-
আউটপুট কনসোলে প্রদর্শিত হয়।
