जब रैखिक समय जटिलता में सूची से 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('संख्याओं की सूची दर्ज करें.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('i के लिए मान दर्ज करें.. '))
ith_smallest = select_smallest(my_list, 0, len(my_list), i)
print('परिणाम {} है।'.format(ith_smallest))
आउटपुट
संख्याओं की सूची दर्ज करें.. 43 12 67 89 99 0 i के लिए मान दर्ज करें.. 3 परिणाम 43 है।
व्याख्या
'select_smallest' नामक एक विधि परिभाषित की गई है, जो सूची, शुरुआत, अंत और एक 'i' मान को पैरामीटर के रूप में लेती है।
'start_partition' नामक एक अन्य विधि परिभाषित की गई है जो 'i' के मान के आधार पर सूची को दो भागों में विभाजित करती है।
यह विधि 'select_smallest' विधि में कॉल की जाती है।
'select_smallest' को उसी फ़ंक्शन के अंदर फिर से कॉल किया जाता है - इस तरह पुनरावृत्ति काम करती है।
संख्याओं को उपयोगकर्ता से इनपुट के रूप में लिया जाता है।
इसे डिफ़ॉल्ट मान के आधार पर विभाजित किया जाता है।
इस पर पुनरावृत्ति की जाती है।
'i' के लिए एक मान उपयोगकर्ता से लिया जाता है।
इस 'i' मान के आधार पर, सूची दो भागों में विभाजित होती है।
सूची में से एक पर 'select_smallest' विधि कॉल की जाती है।
आउटपुट कंसोल पर प्रदर्शित किया जाता है।
