1

please help. I need to optimize my Bubble Sort algorithm in order to get less total comparisons than the non-optimised bubbleSort. I managed to create just the 'Normal Bubble sort (only travels from left to right):

def bubbleSort(values):
    n = len(values) - 1
    swap = True
    ncomp = 0 # My total comparisons counter
    while swap:
        swap = False
        for i in range(n): # i = 0, 1, 2, ..., n-1
            ncomp += 1
            if values[i] > values[i+1]:
                temp = values[i]
                values[i] = values[i+1]
                values[i+1] =  temp
                swap = True
    return values, ncomp

So basically i dont know how to create an 'optimised bubbleSort', a bubbleSortPlus function in which bubbles travel in both directions: from left to right, immediately followed by a travel from right to left. In theory, in each pass the travel of the bubbles should be shortened (saving in a variable the position of the last swap in a travel, and make the next travel start at that position. I tried so hard but i'm just a python newbie, please help.

Anderson
  • 25
  • 6
  • see [How to debug my Bubble Sort code?](http://stackoverflow.com/a/36932606/2521214) there you will find the optimization that changes the inner loop count with time. The optimization you are talking about will not help at all as the 2 passes will interract with each other. Not to mention the overhead so the result will be either wrong (if not coded properly) or slower then before. – Spektre May 18 '16 at 07:02

2 Answers2

0

I guess it has been optimized... The naive Bubble sort does not include the swap flag. So it will not return until finish all O(n^2) comparisons in any cases. But with swap flag, the number of comparison will be almost linear if the input sequence has been "almost sorted".

Lifu Huang
  • 11,930
  • 14
  • 55
  • 77
  • It is the normal Bubble Sort, you can test my function with any 10 values array and then compare with this link http://www.advanced-ict.info/interactive/algorithms.html – Anderson May 18 '16 at 02:12
  • Well, it is totally subjective to judge whether it is "optimized" or not. I am just telling you a kind of view that many people hold when talking about bubble sort. https://en.wikipedia.org/wiki/Bubble_sort – Lifu Huang May 18 '16 at 05:10
0

Here's some skeleton code that shows how to scan the array forwards and backwards, while shrinking the list on each iteration.

values = 100,101,102,103,104,105

start = 0
stop = len(values)-1

while stop > start:
    for i in range(start, stop):
        print i, "compare", values[i], "with", values[i+1]
    print "moved a large value to index", stop
    print

    stop = stop - 1
    if stop == start:
        break

    for i in range(stop, start, -1):
        print i, "compare", values[i], "with", values[i-1]
    print "moved a small value to index", start
    print

    start = start + 1
user3386109
  • 34,287
  • 7
  • 49
  • 68
  • Cool, but how can i add a total comparisons counter? – Anderson May 18 '16 at 02:51
  • @Anderson This is just the starting point. You need to add the code that actually does the comparison/swaps, and then you can add the comparison counter. – user3386109 May 18 '16 at 02:55
  • Well, i'll try. Thank you very much – Anderson May 18 '16 at 03:06
  • Hi, @user3386109, thank you for your solution. But just out of curiosity, how can I know whether it is indeed a optimized version? Is there a proof of it or any intuitive explanation. Because it looks to me like just doing the Bubble sort in a fancier order while neither decrease time complexity nor times of comparisons. Please correct me if I am wrong, thanks :) – Lifu Huang May 18 '16 at 04:55
  • @LifuHuang You are correct. The OP is experimenting with algorithm design. The bi-directional bubble sort is one such experiment. After the student implements the code, they discover that it has the same complexity as a normal bubble sort. So it's just a fun exercise for the student. – user3386109 May 18 '16 at 04:59
  • Got it, thanks, but since it is not optimization at all, I think it might be better if you would explicitly mark in your post in case that it misled newbies like me. – Lifu Huang May 18 '16 at 05:06
  • @LifuHuang I never said it was an optimization. I said it was skeleton code that helps the OP do what was asked. – user3386109 May 18 '16 at 05:19
  • The 'bi-directional' bubble sort is the Cocktail shaker sort right? – Anderson May 18 '16 at 05:37
  • @Anderson I had never heard that name before, but yes it is (at least if you believe wikipedia). – user3386109 May 18 '16 at 05:43
  • @Anderson to determine if optmization works you have to measure few test cases with booth approaches and compare the times on actual HW. – Spektre May 18 '16 at 07:05