Python Program to Find ith Smallest Element from List in Linear Time

This is a Python program to select the ith smallest element from a list in expected linear time.

Problem Description

The program takes a list and i as input and prints the ith smallest element in the list.

Problem Solution

1. Create a function select which takes a list and variables start, end, i as arguments.
2. The function will return the ith smallest element in the range alist[start… end – 1].
3. The base case consists of checking whether there is only one element in the list and if so, alist[start] is returned.
4. Otherwise, the list is partitioned using Hoare’s partitioning scheme.
5. If i is equal to the number of elements in alist[start… pivot], call it k, then the pivot is the ith smallest element.
6. Otherwise, depending on whether i is greater or smaller than k, select is called on the appropriate half of the list.

Program/Source Code

Here is the source code of a Python program to select the ith smallest element from a list in expected linear time. The program output is shown below.

def select(alist, start, end, i):
    """Find ith smallest element in alist[start... end-1]."""
    if end - start <= 1:
        return alist[start]
    pivot = partition(alist, start, end)
 
    # number of elements in alist[start... pivot]
    k = pivot - start + 1
 
    if i < k:
        return select(alist, start, pivot, i)
    elif i > k:
        return select(alist, pivot + 1, end, i - k)
 
    return alist[pivot]
 
def partition(alist, start, end):
    pivot = alist[start]
    i = start + 1
    j = end - 1
 
    while True:
        while (i <= j and alist[i] <= pivot):
            i = i + 1
        while (i <= j and alist[j] >= pivot):
            j = j - 1
 
        if i <= j:
            alist[i], alist[j] = alist[j], alist[i]
        else:
            alist[start], alist[j] = alist[j], alist[start]
            return j
 
 
alist = input('Enter the list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
i = int(input('The ith smallest element will be found. Enter i: '))
 
ith_smallest_item = select(alist, 0, len(alist), i)
print('Result: {}.'.format(ith_smallest_item))
Program Explanation

1. The user is prompted to enter a list of numbers.
2. The user is then asked to enter i.
3. The ith smallest element is found by calling select.
4. The result is displayed.

advertisement
advertisement
Runtime Test Cases
Case 1:
Enter the list of numbers: 3 5 10 2 -1 0 2
The ith smallest element will be found. Enter i: 2
Result: 0.
 
Case 2:
Enter the list of numbers: 7
The ith smallest element will be found. Enter i: 1
Result: 7.
 
Case 3:
Enter the list of numbers: 5 4 3 2 1
The ith smallest element will be found. Enter i: 5
Result: 5.

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.