StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POBubble sort algorithm implementations (Haskell vs. C)
text
Body
copied!<p>I have written 2 implementation of bubble sort algorithm in C and Haskell. Haskell implementation:</p> <pre><code>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 </code></pre> <p>I've compared these two implementations having run both on file with size of 20 KiB.<br> C implementation took about a second, Haskell — about 1 min 10 sec.<br> I have also profiled the Haskell application:<br> Compile for profiling: </p> <blockquote> <p>C:\Temp> ghc -prof -auto-all -O --make Main </p> </blockquote> <p>Profile: </p> <blockquote> <p>C:\Temp> Main.exe +RTS -p</p> </blockquote> <p>and got <a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=24190#a24190" rel="nofollow noreferrer">these</a> results. This is a pseudocode of the algorithm: </p> <pre><code>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 </code></pre> <p>I wonder if it's possible to make Haskell implementation work faster without changing the algorithm (there are actually a few tricks to make the algorithm work faster, but neither implementations have these optimizations).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload