[Solved] CS 431 Programming language concepts Homework 5 solved

Homework 5

1 Higher order ML FunctionsFor this homework, you use let expressions and pattern matching to solvethe problems. Your solution should not use top-level helper functions (i.e. anyhelper functions should be de ned locally in a let expression), should avoidredundant computation, and should have the correct types.1. Write a function merge_sort: (a * a -> bool) -> a list -> a listthat takes a comparison function and then a list, and return a sorted listin the order speci ed by the comparison function.For example, merge_sort (op >) [0, 5, 1, ~4, 9, 11] evaluates to[11,9,5,1,0,~4].2. Write a function selection_sort: (a * a -> bool) -> a list -> a listthat takes a comparison function and then a list, and return a sorted listin the order speci ed by the comparison function.Selection sort orders a list from the left to right by selecting the leastelement from the unsorted portion of the list and adds it to the partiallysorted list. Note that the least element is not necessarily the smallestor largest element { it depends on the comparison function passed toselection_sort.For example, selection_sort (op >) [0, 5, 1, ~4, 9, 11] evaluatesto [11,9,5,1,0,~4]. The computation has the following steps:[0, 5, 1, ~4, 9, 11] select 11-> 11::[0, 5, 1, ~4, 9] select 9-> 11::9::[0, 5, 1, ~4] select 5-> 11::9::5::[0, 1, ~4] select 1-> 11::9::5::1::[0, ~4] select 0-> 11::9::5::1::0::[~4] select ~4-> 11::9::5::1::0::~4::nilYou should implement a helper function select: a list -> a listas an inner function to selection_sort. The select function takes a1list and returns the list with the least element in front. For example,select [0,5,1,~4,9,11] should return [11,0,5,1,~4,9] given the or-dering function op >.3. Write a function insertion_sort: (a * a -> bool) -> a list -> a listthat takes a comparison function and then a list, and return a sorted listin the order speci ed by the comparison function.Insertion sort orders a list from left to right by inserting an element fromunsorted portion of the list into the correct position in the sorted portionof the list.For example, insertion_sort (op >) [0, 5, 1, ~4, 9, 11] evaluatesto [11,9,5,1,0,~4]. The computation has the following steps:nil [0, 5, 1, ~4, 9, 11] insert 0-> [0] [5, 1, ~4, 9, 11] insert 5-> [5, 0] [1, ~4, 9, 11] insert 1-> [5, 1, 0] [~4, 9, 11] insert ~4-> [5, 1, 0, ~4] [9, 11] insert 9-> [9, 5, 1, 0, ~4] [11] insert 11-> [11, 9, 5, 1, 0, ~4] nilYou should implement two helper functions as inner functions. The rstfunction insert:a list * a -> a list takes a sorted list l and anelement x and insert x into the right position of l so that the list remainssorted after insertion. For example, insert ([5,1,0,~4], 9) shouldevaluates to [9,5,1,0,~4]. Again the order depends on the compar-ision function passed to insertion_sort. The second helper functionsort:a list * a list -> a list takes a sorted list sofar and anunsorted list l and inserts the elements of l into sofar.4. Write a function quicksort: (int * int -> bool) -> int list -> int listthat takes a comparison function (i.e. either op > or op <), then a list ofintegers, and return a sorted list of integers in the order speci ed by thecomparison function.requirement:(a) You should implement quicksort algorithm.(b) You should have three base cases: empty list, list of one, and list oftwo elements.(c) The pivot is the average of the rst, middle, and the last element ofthe list. You should de ne an inner function get: int list * int -> intthat takes a list and return an element of the list speci ed by an in-dex. For example, get(lst, 1) returns the rst element of lst,get(lst, (length lst + 1) div 2) returns the middle elmeent,and get(lst, length lst) returns the last element.2(d) The split function should split the list into three sublists: (lower, middle, upper),where the middle list are elements that are equal to the pivot. Thelower and upper lists are elements that are either less or greaterthan the pivot (depending on the comparison function).(e) Note that you place the middle list between the sorted lower andupper list.2 SubmissionPlease write your solution in a text le by the name of hwk5.sml and submit itto the dropbox.3