Nth Largest Element in the list using Bubble Sort

Bubble sort algorithm is very slow sorting algorithm if we think about its running time O(n2), but it can be very useful in finding the nth largest element in the list. There are several ways to find the largest and smallest elements in an array/list, but if it is asked to find the nth largest element (e.g. 5th largest) in the array/list, it can be a bit tricky. Using bubble sort, the desired result can be achieved very easily.

We know that the bubble sort pushes the larger elements towards the end of the array/list in each iteration i.e. after 1st iteration, the largest element goes to the last position, after 2nd iteration, the second largest element is placed before the last element and so on. This feature of the bubble sort can help us in determining the nth largest element in the list. Check out the modified python code for bubble sort that I wrote for finding the nth largest element in the list. The function takes list and the position (like 1st, 2nd etc.) as arguments and returns the element.

def swap(a1,a2):
	x = a1
	a1 = a2
	a2 = x
def nth_largest(a,e):
	n = len(a)
	loop = 0
#iterate the loop only e times as e is the position
	while (loop <= e): for i in xrange(1,n): if(a[i-1] > a[i]):
				(a[i-1],a[i]) = swap(a[i-1],a[i])
		loop = loop+1
	return a[n+1-loop]  

l = [13,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
e = 8
s = nth_largest(l,e)
print e, "th largest element is" , s

The output of the above code looks like this…

4 th largest element is 14
6 th largest element is 13
8 th largest element is 11

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.