Bubble sort algorithm implementations (Haskell vs. C)
- by kingping
Hello.
I have written 2 implementation of bubble sort algorithm in C and Haskell.
Haskell implementation:
module Main where
main = do
contents <- readFile "./data"
print "Data loaded. Sorting.."
let newcontents = bubblesort contents
writeFile "./data_new_ghc" newcontents
print "Sorting done"
bubblesort list = sort list [] False
rev = reverse -- separated. To see
rev2 = reverse -- who calls the routine
sort (x1:x2:xs) acc _
| x1 > 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 ghc -prof -auto-all -O --make Main
Profile:
C:\Temp Main.exe +RTS -p
and got these results. 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] > A[i+1] then
swap( A[i], A[i+1] )
swapped := true
end if
end for
while swapped
end procedure
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)
