Haskell - Sorting P29040


Statement
 

pdf   zip

thehtml

Implement some algorithms to sort lists.

  1. Define a function insert :: [Int] -> Int -> [Int] that, given a sorted list and an element, correctly inserts the new element in the list.

    Define a function isort :: [Int] -> [Int] that implements insertion sort using the previous function.

  2. Define a function remove :: [Int] -> Int -> [Int] that, given a list and an element x, erases the first occurrence of x from the list. You can assume that the element is always in the list.

    Define a function ssort :: [Int] -> [Int] that implements selection sort using the previous function.

  3. Define a function merge :: [Int] -> [Int] -> [Int] that, given two sorted lists, merges them to get a list with all the elements in sorted order.

    Define a function msort :: [Int] -> [Int] that implements merge sort using the previous function.

  4. Define a function qsort :: [Int] -> [Int] that implements quick sort.
  5. Generalize the previous function into genQsort :: Ord a => [a] -> [a] that sorts elements of any type.

Scoring

Each sorting algorithm scores 20 points.

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
    English
    Translator
    Jordi Petit
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell