On Sat, 09 Feb 2008 13:37:23 -0800, Jeff Schwab wrote: > Carl Banks wrote: >> On Feb 8, 10:09 pm, Jeff Schwab <[EMAIL PROTECTED]> wrote: >>> If you expect your data to be pretty nearly sorted already, but you >>> just want to make sure (e.g. because a small number of elements may >>> have been inserted or removed since the last sort), bubble-sort is a >>> good choice. >> >> But if you're at that stage you probably were doing something wrong in >> the first place. > > How do you figure? You don't always have control over the > insertions/replacements, or where they happen. As a silly example, > assume you have a sorted list of children, by height. Maybe you check > your list once per school semester. The new sort order for any given > semester will likely be very close to the previous order; however, a few > swaps may be in order, according to the different speeds at which > children have grown.
You check their heights once per semester, but you're worried about an extra ten or twenty microseconds to sort the data? Frankly, if we're talking about sorting at the level of Python application programming, nothing you write is going to beat the speed of the built-in list.sort() and sorted() built-ins. Here's that bubble sort from yesterday again: def bubble(A): # http://planetmath.org/encyclopedia/Bubblesort.html N = len(A)-1 done = False while not done: done = True for i in xrange(N): if A[i+1] <= A[i]: A[i], A[i+1] = A[i+1], A[i] done = False return A and some speed tests: >>> L = [1, 2, 3, 4, 6, 5, 7, 9, 8] >>> min(timeit.Timer('bubble(L)', ... 'from __main__ import bubble, L').repeat(number=1000)) 0.012052059173583984 >>> min(timeit.Timer('sorted(L)', ... 'from __main__ import L').repeat(number=1000)) 0.0055558681488037109 >>> min(timeit.Timer('bubble(L)', ... 'from __main__ import bubble; L=range(5)').repeat(number=1000)) 0.008541107177734375 >>> min(timeit.Timer('sorted(L)', ... 'L=range(5)').repeat(number=1000)) 0.0046191215515136719 If you're writing code in a low-level language, or a high-level language with no built-in sort (or a crappy one), your mileage may vary. -- Steven -- http://mail.python.org/mailman/listinfo/python-list