Haskell - Ordenació P29040


Statement
 

pdf   zip

html

Es vol implementar diversos algorismes d’ordenació de llistes.

  1. Feu una funció insert :: [Int] -> Int -> [Int] que, donada una llista ordenada i un element, insereixi ordenadament el nou element a la llista.

    Feu una funció isort :: [Int] -> [Int] que implementi l’algorisme d’ordenació per inserció utilitzant la funció anterior.

  2. Feu una funció remove :: [Int] -> Int -> [Int] que, donada una llista i un element x, elimini la primera ocurrència de x de la llista. Podeu assumir que l’element sempre és a la llista.

    Feu una funció ssort :: [Int] -> [Int] que implementi l’algorisme d’ordenació per selecció utilitzant la funció anterior.

  3. Feu una funció merge :: [Int] -> [Int] -> [Int] que, donades dues llistes ordenades, les fusioni per obtenir una llista amb tots els seus elements ordenats.

    Feu una funció msort :: [Int] -> [Int] que implementi l’algorisme d’ordenació per fusió utilitzant la funció anterior.

  4. Feu una funció qsort :: [Int] -> [Int] que implementi l’algorisme d’ordenació ràpida.
  5. Generalitzeu la funció anterior per fer ara una funció genQsort :: Ord a => [a] -> [a] que ordeni llistes de qualsevol tipus.

Puntuació

Cada mètode d’ordenació puntua 20 punts.

Public test cases
  • Input

    insert [10,20,30,40] 25
    insert [10,20,30,40] 20
    isort [6,5,2,5,6,8]
    remove [6,4,3,5,2,3] 2
    remove [6,4,3,5,2,3] 6
    ssort [6,5,2,5,6,8]
    merge [1,2,5,7,8] [2,4,7,9]
    msort [6,5,2,5,6,8]
    qsort [6,5,2,5,6,8]
    genQsort [5.0,3.0,2.5]
    genQsort ["jordi", "albert", "josep"]
    genQsort "antaviana"
    

    Output

    [10,20,25,30,40]
    [10,20,20,30,40]
    [2,5,5,6,6,8]
    [6,4,3,5,3]
    [4,3,5,2,3]
    [2,5,5,6,6,8]
    [1,2,2,4,5,7,7,8,9]
    [2,5,5,6,6,8]
    [2,5,5,6,6,8]
    [2.5,3.0,5.0]
    ["albert","jordi","josep"]
    "aaaainntv"
    
  • Information
    Author
    Albert Rubio / Jordi Petit
    Language
    Catalan
    Other languages
    English
    Official solutions
    Haskell
    User solutions
    Haskell