Haskell - Sorting P29040


Statement
 

pdf   zip

html

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