Haskell-cafe - Bubble sort algorithm implementations (Haskell vs. C)

Hello. I have written 2 implementation of bubble sort algorithm in C
and Haskell. Haskell implementation:
module Main where
main = do
contents x2 = sort (x1:xs) (x2:acc) True
sort (x1:xs) acc flag = sort xs (x1:acc) flag
sort [] acc True = sort (rev acc) [] False
sort - acc - = rev2 acc
I've compared these two implementations having run both on file with
size of 20 KiB.
C implementation took about a second, Haskell — about 1 min 10 sec.
I have also profiled the Haskell application:
Compile for profiling:
C:Temp
and got these http://hpaste.org/fastcgi/hpaste.fcgi/view?id=24190#a24190
This is a pseudocode of the algorithm:
procedure bubbleSort( A : list of sortable items ) defined as:
do
swapped := false
for each i in 0 to length(A) - 2 inclusive do:
if A[i] swap( A[i], A[i+1] )
swapped := true
end if
end for
while swapped
end procedure
The performance may suffer from the memory allocation for the list. I
wonder if it's possible to make Haskell implementation work faster
without changing the algorithm (there's are actually a few tricks to
make it work faster, but neither implementations have these
optimizations).
I'm interested not in particular algorithm performance but rather in
performance of its implementations in various languages. I compiled
the Haskell implementation in GHC (Haskell Platform 2009.2.0.2), which
is the latest available from the site.

You may want to use a mutable array.
If you are interested in its performance in various languages you may
want to implement the Bubble Sort the "best" way in each language.

You might express the algorithm more directly in Haskell, without the reverse calls:
bubblesort :: (Ord a) =bubblesort [] = []
bubblesort (x0:xs) = case bubble x0 xs of
(xs', True) - (xs', False) - where bubble x1 (x2:xs) | x1

On Sun, Mar 21, 2010 at 03:39:08PM +1000, Yasir Arsanukaev wrote:
Is your C program using lists or arrays? These are different
algorithms.

Felipe Lessa writes:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id$191#a24191

On Mon, Mar 22, 2010 at 01:08:39AM +0000, kingping wrote:
I don't know how much difference in time there would be, but you
should use lists in C and/or mutable arrays in Haskell, otherwise
you are comparing apples to oranges. Comparision of algorithms
should use the same data structures, unless you're asking for a
comparision of "idiomatic" implementations.
Cheers,

Felipe Lessa writes:

Yes, you're right. However then I'd like to ask what would suit my needs better
Data.Vector, Data.Array or something other.