जब रैखिक समय जटिलता में सूची से 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' के मान के आधार पर सूची को दो भागों में विभाजित करती है।
-
इस विधि को 'select_smallest' विधि में कहा जाता है।
-
उसी फ़ंक्शन के अंदर 'select_smallest' को फिर से कहा जाता है- इस तरह से रिकर्सन काम करता है।
-
नंबर उपयोगकर्ता से इनपुट के रूप में लिए जाते हैं।
-
यह डिफ़ॉल्ट मान के आधार पर विभाजित होता है।
-
इसे पुनरावृत्त किया गया है।
-
'i' के लिए एक मान उपयोगकर्ता से लिया जाता है।
-
इस 'i' मान के आधार पर सूची को दो भागों में बांटा गया है।
-
सूची में से किसी एक पर 'select_smallest' विधि को कॉल किया जाता है।
-
आउटपुट कंसोल पर प्रदर्शित होता है।