sort functions in python
Jeff Schwab
jeff at schwabcenter.com
Sat Feb 9 16:37:23 EST 2008
Carl Banks wrote:
> On Feb 8, 10:09 pm, Jeff Schwab <j... at schwabcenter.com> 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.
> For a list of any decent size a few insertions using a bisection
> algorithm will take fewer comparisons than a single bubblesort pass.
Do you mean that if newly inserted data are kept separate from the
already-sorted list, then they can be merged into the list in O(log N) time?
More information about the Python-list
mailing list