sorting times

Matt mgr3 at aber.ac.uk
Wed Mar 24 23:50:49 CET 2004


X-No-archive: yes

Hi,
I'm a cs student, and working on an assignment using python. uber cool
except...

I have an assignment that requires me to analyse the time complexities
of bubble sort and quick sort.
I don't want any help - but would like to know if people consider the
following times to be 'normal':

I have extensively tested both algorithms on smaller sets of data, as
well as the parser class i created - quite a few test cases for such a
small app. (all tests pass)

Environment:
Running on linux 2.4 / pentium 4.2 Ghz / 1GB  RAM

Results:
File: two columns, <str>\t<float>, 
pow(10, 5) lines in file.

Bubble Sort takes 32 - 35 minutes
Quick Sort takes 8 seconds


My quick sort implementation uses random pivot selection and is
recursive,
the bubble sort is adaptive, uses a "flipped" flag to exit early if
data is already sorted.

I implemented both algorithms in C , as bubble sort used to take 8
hours.

Any comments much appriciated.

Matt
NB. I haven't posted the code in case of plagerism.



More information about the Python-list mailing list