CODEWITHSUNDEEP
listrecursionfunctional-programmingocaml
Teo
Teo

Reputation: 43

Workaround to append attaching elements in reverse order when sorting

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];;

Upvotes: 0

Views: 72

Answers (3)

Chris
Chris

Reputation: 36476

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:

# 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, rev evens)

# 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 @ rev evens)

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

As mentioned in another answer, a properly written comparator for a sort will achieve this effect as well. If both are even or both are false, they are equal for the purposes of this comparison. If the first is even, but the second is false, the first is greater, and otherwise we know by elimination that the first must be less.

# [3; 1; 7; 3; 4; 5; 4; 3; 6; -1; 0; 3]
  |> List.sort 
       (fun a b -> 
          let is_even x = x mod 2 == 0 in
          match is_even a, is_even b with 
          | (false, false) | (true, true) -> 0 
          | (true, false) -> 1 
          | _ -> -1);;
- : int list = [3; 1; 7; 3; 5; 3; -1; 3; 4; 4; 6; 0]

If we used this type of comparison with a basic bubblesort, we'd see a progression like:

[3; 1; 7; 3; 4; 5; 4; 3; 6; -1; 0; 3]
[3; 1; 7; 3; 5; 4; 3; 4; -1; 6; 3; 0]
[3; 1; 7; 3; 5; 3; 4; -1; 4; 3; 6; 0]
[3; 1; 7; 3; 5; 3; -1; 4; 3; 4; 6; 0]
[3; 1; 7; 3; 5; 3; -1; 3; 4; 4; 6; 0]
[3; 1; 7; 3; 5; 3; -1; 3; 4; 4; 6; 0]
(* no swaps were made, so it's sorted *)

Upvotes: 0

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66818

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.

Upvotes: 2

glennsl
glennsl

Reputation: 29106

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]

Upvotes: 2

Related Questions