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

«
»

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

Problem Description

The program takes a list and i as input and prints the ith largest 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 largest 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[pivot… end – 1], call it k, then the pivot is the ith largest 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 largest element from a list in expected linear time. The program output is shown below.

def select(alist, start, end, i):
    """Find ith largest element in alist[start... end-1]."""
    if end - start <= 1:
        return alist[start]
    pivot = partition(alist, start, end)
 
    # number of elements in alist[pivot... end - 1]
    k = end - pivot
 
    if i < k:
        return select(alist, pivot + 1, end, i)
    elif i > k:
        return select(alist, start, pivot, 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 largest element is found by calling select.
4. The result is displayed.

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

Sanfoundry Global Education & Learning Series – Python Programs.

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

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 & technical discussions at Telegram SanfoundryClasses.