CODEWITHSUNDEEP
arrayssortingocamlml
Jonathan Engwall
Jonathan Engwall

Reputation: 59

OCaml matching in a sorting algorithm 0(n^2)

I have tried several things. Can I simply not match with less than? The exception is redundant, to enable the matching loop. I can imagine all sorts of things are wrong and this bit of code. It would be nice if the vague less-than-you-less-than-me concept worked. I admit I am frustrated. Why do I get an error at j < k every time, no matter where I improve or edit? Is that simply against the rules? I was just looking at Array Length > Array Length as my while condition, that will have to change. Also, none of the Array Sorting methods seem to me to work in the smallest upwards routine as I understand the 0(n^2). Can this code implement Array.for_all as a sorting algorithm? UPDATE

let i = Array.length arr in
let sort (arr : array) (j : int) (k : int) =
Array.make n x = unsorted(arr : array) (n : int) (x : int) 
while i > 0 
  match j < k with
    | true -> a.(n) <- j
      | false -> failwith (Printf.sprintf "Exception Found (%d)" i) 
i - 1
;;

That was a lot of questions. Thank you.

UPDATE: I appreciate the help very much. I know I need two arrays, not one. The finished code should read an array, and then give an array back. So, when k points to a smallest j the purpose of the algorithm is to kick j out of the first array, from wherever it it is, put it into the second array, and append every j after that one into the second array. The job is done when the first array is empty. I see plenty of information about lists out there but not much about arrays. How can I remove the j_n-th element of an array? This is a nice looking example of recursion used to search and delete an element from a list, can that work in an array? Thank you again

Upvotes: 1

Views: 197

Answers (3)

Lhooq
Lhooq

Reputation: 4441

You'll have a lot of problems with your code but to answer your question, there are 3 ways I can see to do what you want to do:

match j < k with
  | true -> a.(n) <- j
  | false -> failwith (Printf.sprintf "Exception Found (%d)" i) 

match j with
  | _ when j < k -> a.(n) <- j
  | _ -> failwith (Printf.sprintf "Exception Found (%d)" i) 

if j < k 
then a.(n) <- j
else failwith (Printf.sprintf "Exception Found (%d)" i)

The latter being the better. The only thing you need to remember is that pattern matching is done on patterns, it looks at what the values are, not their relations to other values. You can match an int with 1, 3 or 127 but not match this int with another one or compare it with another one.

On a side note, here are some problems in your code and some answers to your questions:

  • sort takes an array, a j, a k and a i but then

    • You use Array.make by checking if it's equal to unsorted (x = f is a boolean comparison unless you write let x = f in ...). It looks like you're trying to define an internal function but it's unclear how you're making it
    • if you want to define a randomly sorted array, you could just write Array.init 100 (fun _ -> Random.int 100)

  • you're clearly trying to sort your array between i and n (while a.(i) > a.(n) do ... done but then you're checking on j that is a parameter of your function and that never changes

  • Array.for_all checks that a predicate is true for every value in the array. If you want to apply a function with a different return type to your array you can either use Array.map:

    map f a applies function f to all the elements of a, and builds an array with the results returned by f: [| f a.(0); f a.(1); ...; f a.(length a - 1) |].

    or Array.fold_{left|right}:

    fold_left f init a computes f (... (f (f init a.(0)) a.(1)) ...) a.(n-1), where n is the length of the array a.

    fold_right f a init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init) ...)), where n is the length of the array a.

  • As for the sorting functions, what makes you think they won't run in O(n^2)? You can look at the way they're implemented here

Upvotes: 2

Shawn
Shawn

Reputation: 52579

You can use an expression in a when clause to further constrain when a pattern matches. Simple example:

let f x =
  match x with
  | _ when x < 5 -> true
  | _ -> false

In this trivial case, an if is of course better, but it can be useful in more complicated pattern matching with lots of options.

Upvotes: 2

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

The match in OCaml is restricted (in essence) to matching a value (an expression) against a set of structured constants that are known at compile time. If you want to test something like whether j < k you should just use an if expression, even if it's not as exotic and powerful seeming.

There are many other problems with your code, but this seems to answer your main question.

Upvotes: 2

Related Questions