Question

Implement the bubble sort in ML using pattern matching and local function definitions. Show that it works with a few simple examples. A nice description of the bubble sort can be found on Wikipedia.

A helpful function for the bubble sort is:

(* General function that checks if an int list is sorted *)

fun issorted [] = true  

| issorted [x] = true

| issorted (x::y::t) = x <= y andalso issorted(y::t);

Test your solution and show that it works on the following examples:

• bubbleSort []; → []  

• bubbleSort [1]; → [1]  

• bubbleSort [1,2,3]; → [1,2,3]  

• bubbleSort [3,1,2]; → [1,2,3]  

bubbleSort [5,4,3,2,1]; → [1,2,3,4,5]

Answer 1

Answer:

SourceCode:

fun issorted [] = true | issorted [x] = true | issorted (x::y::t) = x <= y andalso issorted(y::t); 

(* swapping function *)

fun swap [] = [] | swap [x] = [x] | swap (x::y::t) = if (x>y) then y::(swap (x::t))

else x::(swap (y::t));

(*call swap to sort the given list*)

fun bubblesort [] = [] | bubblesort i = if (issorted i) then i else bubblesort (swap i);

val ex1 = bubblesort [1] = [1]
val ex2 = bubblesort [1,2,3] = [1,2,3]
val ex3 = bubblesort [3,1,2] = [1,2,3]
val ex4 = bubblesort [5,4,3,2,1] = [1,2,3,4,5]

The outputs are:

val ex1 = true:bool
val ex2 = true:bool
val ex3 = false:bool
val ex4 = false:bool

Let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please leave a +ve feedback : ) Let me know for any help with any other questions.

Thank You!
===========================================================================