Re: "Sorting" assignment

user923005 wrote:
CBFalconer <cbfalco...@xxxxxxxxx> wrote:
pete wrote:

... snip ...

It can do better depending on the order. Bubble sort can sort
this: {1,0,3,2,5,4,7,6,9,8} where all of the elements are out of
place, into ascending order in one pass.

6) Bubble sort is a stable sort.

It is also O(n * n). However mergesort is also stable, and is
always O(n Log n). Bubble sort is to all practical purposes the
worst possible general sort.

That is true for a general sort. However, it is useful in rare
{special purpose} cases (e.g. when you know the data will almost
always be almost sorted).

This arises (for instance) in chess programming. There is a list
of moves that will be nearly correctly ordered because of
previous searches. For these searches, the lists will typically
be small (about 35 items on average) and at most one or two items
will be out of place. For this type of thing, bubble sort is
actually the fastest solution.

Even here I have my doubts. That list is obviously of varying
length, and thus is most easily organized as a list [1]. Lists are
easily handled by mergesort. No need to keep track of the count of
item, reorganize into an array, etc. etc. etc.

[1] Different meaning for this 'list'.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: "Sorting" assignment
    ...  However mergesort is also stable, ...  Bubble sort is to all practical purposes the ... That is true for a general sort. ... the lists will typically be small ...
    (comp.programming)
  • Re: Mergesort Vs Quicksort
    ... preference reflects the prevalence of array-based imperative thinking. ... Mergesort is much more common than quicksort in functional programming ... Note that being in a heap allows you to append a largest ... the lists in at most O) time. ...
    (comp.programming)
  • Re: Detailed explanation of how a QuickSort Works
    ... Firstly, if you consider the simple "Bubble Sort" algorithm, it works by running through the entire data set, one item at a time, comparing each item to the previous item and swapping them if they are not already in the correct order. ... by simply running through the entire list just once (and splitting it into two smaller lists) you have cut the sorting time in half. ...
    (microsoft.public.vb.general.discussion)
  • Re: Mergesort algorithm for linked lists
    ... Everyone knows how to sort arrays (e. ... For linked lists, mergesort is the typical choice. ...
    (comp.lang.c)
  • Re: Strange bug
    ... This is Chris Torek's recursive linked-list mergesort. ... A top-down mergesort splits its input into two sublists of similar ... N/2 items at the top level, four lists of N/4 items at the next, and ... A bottom-up mergesort builds up islands of sortedness. ...
    (comp.lang.c)