CODEWITHSUNDEEP
pythonalgorithmsorting
Michael Ogorkovyi
Michael Ogorkovyi

Reputation: 11

Bubble sort with optimization in Python

I am quite new in Python and I am starting my journey with sorting algorithms, PEP8 and the Zen of Python. I just wrote a post on CodeReview. I made fixes and i would like to ask about the Optimizing Bubble Sort : Second option. I implemnted the First option of Optimizing the Bubble Sort but i have a problem with the second options. The one which "allows us to skip over a lot of the elements, resulting in about a worst case 50% improvement in comparison count" in Wikipedia. So my code for first option looks like and works:

def bubble_sort(container):
    """
        Bubble sort with optimization.

        Description
        ----------
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        data_container : Mutable structure with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.

        Returns
        -------
        None

        Examples
        ----------
        >>> bubble_sort([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    length = len(container)
    changed = True

    while changed:
        changed = False
        for i in range(length - 1):
            if container[i] > container[i + 1]:
                container[i], container[i + 1] = container[i + 1], container[i]
                changed = True
        length -= 1

And the question is what changes i have to make to implement the second option of optimization. In addition, I have tried to act like in pseudocode so far. My code didnt work ( didnt sort ) and looked like:

# setting up variables
length = len(container)

while length >= 1:
    number_of_changed = 0
    for i in range(1, length - 1):
        if container[i-1] > container[i]:
            container[i-1], container[i] = container[i], container[i-1]
            number_of_changed = i
    length = number_of_changed

Upvotes: 0

Views: 625

Answers (1)

Xion
Xion

Reputation: 374

container = [7,1,2,6,4,2,3]
length = len(container)

while length >= 1:
    num = 0
    for i in range(1, length):
        if container[i-1] > container[i]:
            container[i-1], container[i] = container[i], container[i-1]
            num = i
            print(num,'\n')
    length = num
    print(container)

The problem I see is that you set the range from 1 to (length - 1) -> (7-1) which is 6 so it will go to the 6th element in the array. So take off the minus 1 from the length in your for loop and it should fix the problem. Try placing print at places you think that might cause the problem, it will help you debug your program and tell you information you need. Hope this helps.

Upvotes: 1

Related Questions