I have screwed something up in my selection sort


I have made some mad mistakes in my smalltofront inorder for the selectionsort function to work, what have I done wrong?

a = the array
s = start of the unsorted subarray
i = the index which will move through the elements
j = the right most array index
k = current index to the smallest entry?

 let swap (a,i,j) =
    let temp = a.(i)
    in (a.(i)<-a.(j);

let rec smalltofront (a,s,i,j,k) =
if i>j
then swap (a,s,k)
else (if a.(k) < a.(s)
then smalltofront (a,s,i+1,j,k)
else smalltofront (a,s,i+1,j,k));;

let rec selectionsort (a,i,j) = 
if i>j
then ()
else smalltofront (a,i,i,j,i); selectionsort (a,i+1,j);;

One thing which jumps out at me:

The two branches of the conditional are identical.

I think the first place people should go for help with their homework is the teaching assistant for their class, or their professor. They’re better equipped to help students in such a way that they still get maximum learning value from their homework.

Perry, there is no one available during the summer.
I am studying for my next course.
Stop being such a wise ass and how about you contribute a little bit instead.

I’d like to kindly remind you that no one is obligated to help you in the open source community. While people are generally helpful, in general, no one’s time is paid to contribute to projects or answer anyone’s question. I can understand your frustration w.r.t. the school’s arrangement, but please do not vent your frustration on unrelated people.

Academic honesty is something taken very seriously by universities and by most(if not all) of us here, thus people tend to be very cautious when it comes to homework questions.

It is best that you state you’re not actually doing this for a specific assignment, but instead as practice next time you ask something that looks like a homework question. Either that, or make an alternative example or ask for a more general case instead of a very specific one.

In general people would also recommend what @perry suggested as we have no idea what the context is in general, unless you have provided sufficient details in the question.

I am still combing through your code, and will post a reply later if no one gets to it by then.


Okay, thank you very much!

Some feedback:

  1. Function definitions are different in OCaml(and most other functional programming languages) compared to some of the more commonly used languages, specifically commas mean tuple in OCaml.
    For example,
(* this has a type signature of int -> int -> int*)
let f x y = x + y;;

(* while this has a type signature of int * int -> int *)
let f' (x, y) = x + y;;

let x = (1, 2, 3);; (* this has type signature of int * int * int *)

In f, you have a function that takes two separate arguments.
In f', which is what you wrote, you had a function that takes a single argument of a tuple type, and you pattern match x, y to the tuple argument.

  1. In general, people add type annotations/signatures to make code self-documenting to some extent

  2. Naming convention. AFAIK people tend to go with underscores in OCaml code, though in practice as long as your project is consistent with a certain style, no one complains really.

  3. Make your names more descriptive.

  4. Arrays in OCaml know their lengths, and you can retrieve the length in O(1), so you don’t need to pass the last index around in all function calls.

  5. Always add begin .. end or () when you put multiple statements in the else clause. When you have a if ... then ... else expr1; expr2, only expr1 belongs in the else part, else2 will always be executed.

Here’s a version that’s polished according to above points, but not completely fixed:

let swap (a : int array) (i : int) (j : int) =
  let temp = a.(i) in
  a.(i) <- a.(j);
  a.(j) <- temp

(* Took a while to understand what you're trying to do in this function,
 * add comments in future whenever you have a non-trivial piece of code *)
let rec small_to_front (arr : int array) (start_unsorted : int) (i : int) (index_smallest : int) =
  let last_index = (Array.length arr) - 1 in
  if i > last_index
  then swap arr start_unsorted index_smallest
  else (
    if arr.(index_smallest) < arr.(start_unsorted)
    then small_to_front arr start_unsorted (i+1) index_smallest
    else small_to_front arr start_unsorted (i+1) index_smallest

let rec selection_sort (arr : int array) (i : int) =
  let last_index = (Array.length arr) - 1 in
  if i > last_index
  then ()
  else (small_to_front arr i i i; selection_sort arr (i+1))

let print_arr (arr : int array) : unit =
  Printf.printf "[|";
  Array.iter (Printf.printf "%d, ") arr;
  Printf.printf "|]\n"

let () =
  let arr = [|3; 2; 1; 0|] in
  selection_sort arr 0;
  print_string "Raw :";
  print_arr arr;
  print_string "Sorted :";
  selection_sort arr 0;
  print_arr arr;

Please give it a shot at fixing above code before looking at the fixed version.

My fixed and slightly improved version as gist


IMO it is in your best interest to apologise to @perry in some way, if you have not done so already. I absolutely don’t think perry’s response warranted any harshness. But obviously what you decide to do is beyond my control.