Difference between revisions of "PFP Laboratory 9"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Created page with "== Arrays == == Bubble sort == * Create a function, that sorts an array using the bubble sort algorithm. <syntaxhighlight lang="Haskell">bubbleSort :: Array Int Int -> Arra...")
 
 
Line 11: Line 11:
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
−
module Main (main) where
+
import Data.Array
−
import System.Random
+
import Data.Array.ST
−
import System.Environment
+
import Control.Monad
  
−
myCycle :: Integer -> Integer -> IO Integer
+
bubbleSort :: Array Int Int -> Array Int Int
−
myCycle i c
+
bubbleSort myArray = runSTArray  $ do
−
  | i == 0 = return c
+
     stArray <- thaw myArray
−
  | otherwise = do  
+
    let end = (snd . bounds) myArray
−
     x <- randomRIO (0, 1.0) :: IO Double
+
     forM_ [1 .. end] $ \i -> do
−
     y <- randomRIO (0, 1.0) :: IO Double
+
        forM_ [0 .. (end - i)] $ \j -> do
−
    myCycle (i-1) (if sqrt (x*x + y*y) <= 1 then c+1 else c)
+
            val <- readArray stArray j
−
 
+
            nextVal <- readArray stArray (j + 1)
−
main :: IO ()
+
            let outOfOrder = val > nextVal
−
main = do  
+
            when outOfOrder $ do
−
    [arg] <- getArgs
+
                writeArray stArray j nextVal
−
    let number = read arg::Integer
+
                writeArray stArray (j + 1) val
−
    inside <- myCycle number 0
+
     return stArray
−
    let my_pi = (fromIntegral (4*inside) / fromIntegral number) :: Double
 
−
     print my_pi
 
 
</syntaxhighlight>
 
</syntaxhighlight>
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>

Latest revision as of 12:53, 4 November 2022

Arrays

Bubble sort

  • Create a function, that sorts an array using the bubble sort algorithm.
bubbleSort :: Array Int Int -> Array Int Int

ghci> elems $ bubbleSort $  listArray (0,5) [8,4,9,6,7,1] 
[1,4,6,7,8,9]

import Data.Array
import Data.Array.ST
import Control.Monad

bubbleSort :: Array Int Int -> Array Int Int
bubbleSort myArray = runSTArray  $ do
    stArray <- thaw myArray
    let end = (snd . bounds) myArray
    forM_ [1 .. end] $ \i -> do
        forM_ [0 .. (end - i)] $ \j -> do
            val <- readArray stArray j
            nextVal <- readArray stArray (j + 1)
            let outOfOrder = val > nextVal
            when outOfOrder $ do
                writeArray stArray j nextVal
                writeArray stArray (j + 1) val
    return stArray
Retrieved from "http://behalek.cs.vsb.cz/wiki/index.php?title=PFP_Laboratory_9&oldid=3296"