5 Best Ways to Find the Second Largest Number in a List Using Bubble Sort in Python

Rate this post

πŸ’‘ Problem Formulation: Finding the second-largest number in a list is a common task in algorithm practice. Given an input list [3, 1, 4, 1, 5, 9, 2, 6, 5], the desired output for this task would be 6, as it’s the second-largest number in the sorted list.

Method 1: Standard Bubble Sort

This method involves running bubble sort on the entire list to get the list in ascending order and then returning the second last element. Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process repeats until the list is sorted.

Here’s an example:

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n-i-1):
            if lst[j] > lst[j+1] :
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_numbers = bubble_sort(numbers)
print("The second largest number is:", sorted_numbers[-2])

The output will be:

The second largest number is: 6

In the given code, the bubble_sort function takes a list and sorts it in ascending order. After sorting, the second-to-last element of the list (sorted_numbers[-2]) is the second-largest number, which is printed as output.

Method 2: Bubble Sort with Early Stopping

This method adds an optimization to the standard bubble sort. It stops sorting when the second largest element is in the correct position, thus potentially reducing the number of passes.

Here’s an example:

def bubble_sort_stop_early(lst):
    n = len(lst)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                swapped = True
        # If no two elements were swapped by inner loop, break
        if not swapped:
            break
    return lst

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_numbers = bubble_sort_stop_early(numbers)
print("The second largest number is:", sorted_numbers[-2])

The output will be:

The second largest number is: 6

The function bubble_sort_stop_early modifies bubble sort to stop when there are no swaps in a pass, indicating that the list is sorted up to that point. In this case, sorting can stop once the second largest number has reached its correct position.

Method 3: Modified Bubble Sort to Find Only Second Largest Number

This method alters bubble sort to focus solely on finding the second largest number by making at most two complete passes through the list.

Here’s an example:

def find_second_largest(lst):
    n = len(lst)
    for i in range(2):  # only two passes needed
        for j in range(n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst[-2]

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
second_largest = find_second_largest(numbers)
print("The second largest number is:", second_largest)

The output will be:

The second largest number is: 6

In this code, the find_second_largest function makes sure that after two passes, the two largest numbers are in the correct position at the end of the list. The function immediately returns the second-last element of the list without fully sorting it.

Method 4: Bubble Sort Highest Elements to End

This variation on bubble sort specifically bubbles only the two highest elements to the end of the list, avoiding the need to sort the entire list.

Here’s an example:

def bubble_sort_two_highest(lst):
    n = len(lst)
    for i in range(2):  # only moving two highest to the end
        for j in range(0, n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst[-2]

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
second_largest = bubble_sort_two_highest(numbers)
print("The second largest number is:", second_largest)

The output will be:

The second largest number is: 6

The function bubble_sort_two_highest iterates only twice, each time pushing the current largest element in the unsorted part of the list rightward, effectively placing the two largest elements at the end of the list after two iterations.

Bonus One-Liner Method 5: List Comprehension with Bubble Sort Logic

This one-liner combines list comprehension with bubble sort principles to arrive at the second largest element. It’s not the most efficient, but it demonstrates Python’s ability to condense logic into a single line.

Here’s an example:

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
second_largest = sorted((numbers[n] for i in range(2) for n in range(len(numbers)-i-1) if numbers[n] > numbers[n+1]), reverse=True)[1]
print("The second largest number is:", second_largest)

The output will be:

The second largest number is: 6

The one-liner creates a sorted list of all elements that move during the first two passes of a bubble sort run and then takes the second element from the reversed list.

Summary/Discussion

Method 1: Standard Bubble Sort. Straightforward but not efficient as it sorts the entire list. Weakness: takes O(n^2) time even when not necessary.

Method 2: Bubble Sort with Early Stopping. Adds efficiency by halting early. Strength: possibly less than O(n^2) time if the list partially sorted. Weakness: still slow on average.

Method 3: Modified Bubble Sort for Second Largest Number. Targets the solution directly by making minimal passes. Strength: efficient for the specific problem. Weakness: not a general sorting method.

Method 4: Bubble Sort Highest Elements to End. Similar to Method 3 but explicitly moves the highest elements. Strength: slightly more intuitive than Method 3. Weakness: still limited to finding the second largest element only.

Method 5: One-liner with List Comprehension. Clever use of Python list comprehension. Strength: concise code. Weakness: readability and performance are not ideal.