Workaround to append attaching elements in reverse order when sorting-CodePudding

I want to sort so that odd numbers in a list appeart first and evens appear last, but i need evens to be the same position to how they were pre sort, is there a simple workaround to this?

let rec first_odd list = match list with
| [] -> []
| h::t when h mod 2==0 -> first_odd t@[h]
| h::t -> h::first_odd t;;

first_odd[3;1;7;3;4;5;4;3;6;-1;0;3];;
first_odd[1;0;1;5;6;6;1;10;-8;4; -9];;

CodePudding user response：

You can just use List.stable_sort, which implements a merge sort, with a function that compares whether or not each element is odd or even:

let first_odd =
  List.stable_sort
    (fun a b -> compare (a mod 2 = 0) (b mod 2 = 0))

first_odd[3;1;7;3;4;5;4;3;6;-1;0;3];;
- : int list = [3; 1; 7; 3; 5; 3; -1; 3; 4; 4; 6; 0]

first_odd[1;0;1;5;6;6;1;10;-8;4; -9];;
- : int list = [1; 1; 5; 1; -9; 0; 6; 6; 10; -8; 4]

CodePudding user response：

This looks like a homework assignment, so I'll just make a few comments.

First, the expression list @ [elt] has a very bad look to it. If you repeat this for n elements of a list, it has complexity of n^2, because it takes linear time to add to the end of a list. Furthermore, it's necessary to replicate the whole list to add an element to the end. So it's definitely something to avoid.

Second, you can just use List.stable_sort if you write a comparison function that gives the order you desire. This will be a lot faster than your current solution (because it will be n log n rather than n^2).

Third, if you want to work with your current method, I would keep two lists and combine them at the end.

CodePudding user response：

As an academic exercise, it may help to see this implemented in terms of a fold. When using a fold, the initial state is crucial. Let's use two lists in a tuple. One for odds, and one for evens.

Each iteration we consider the initial value and the first element in the list. The function we provide uses that information to provide an updated initial value for the next iteration, which considers the next element in the list.

let list1 = [3; 1; 7; 3; 4; 5; 4; 3; 6; -1; 0; 3]
let list2 = [1; 0; 1; 5; 6; 6; 1; 10; -8; 4; -9]

let sort lst =
  List.fold_left (* function *) ([], []) lst

Now, we just need a function that updates the initial value on each iteration. If the value is even, we'll tack it into the front of the evens list. Otherwise, onto the front of the odds list.

let sort lst =
  List.fold_left 
    (fun (odds, evens) x -> 
       if x mod 2 = 0 then (odds, x :: evens)
       else (x :: odds, evens)) 
  ([], []) lst

If we test this with list2:

utop # sort list2;;
- : int list * int list = ([-9; 1; 5; 1; 1], [4; -8; 10; 6; 6; 0])

The two lists are backwards. We can fix this with List.rev.

let sort lst =
  let odds, evens = 
    List.fold_left 
      (fun (odds, evens) x -> 
         if x mod 2 = 0 then (odds, x :: evens)
         else (x :: odds, evens)) 
      ([], []) lst
    in
    (List.rev odds, List.rev evens)

utop # sort list2;;
- : int list * int list = ([1; 1; 5; 1; -9], [0; 6; 6; 10; -8; 4])

Essentially we've now reinvented List.partition.

Now, we just need to concatenate those two lists.

let sort lst =
  let odds, evens = 
    List.fold_left 
      (fun (odds, evens) x -> 
         if x mod 2 = 0 then (odds, x :: evens)
         else (x :: odds, evens)) 
      ([], []) lst
    in
    List.rev odds @ List.rev evens

utop # sort list2;;
- : int list = [1; 1; 5; 1; -9; 0; 6; 6; 10; -8; 4]