CODEWITHSUNDEEP
f#functional-programming
SuperCell
SuperCell

Reputation: 241

F# sorting issue

Whats wrong with this code? Why wont it sort?

let rec sort = function
  | []         -> []
  | [x]        -> [x]
  | x1::x2::xs -> if x1 <= x2 then x1 :: sort (x2::xs)
                              else x2 :: sort (x1::xs)

Suppost to take sort [3;1;4;1;5;9;2;6;5];;

and return: val it : int list = [1; 1; 2; 3; 4; 5; 5; 6; 9]

Upvotes: 2

Views: 102

Answers (3)

fractal
fractal

Reputation: 105

let rec ssort = function
    [] -> []
    | x::xs -> 
        let min, rest =
            List.fold_left (fun (min,acc) x ->
                             if h<min then (h, min::acc)
                             else (min, h::acc))
              (x, []) xs
        in min::ssort rest

Upvotes: 1

Bartek Kobyłecki
Bartek Kobyłecki

Reputation: 2395

Your code is like one bubble cycle in bubble sort. It will take max element to the last position and some other bigger elements to the right.

Note that you are only traversing original list only once. It has linear complexity and we all know that sorting using only comparison has to be O(n*log n).

You can repeat that cycle more times if you want to sort this list.

Upvotes: 2

Random Dev
Random Dev

Reputation: 52280

think about what can end up in the first position ... right now it can only be the first or the second position in your list (the if inside the last case)

Upvotes: 1

Related Questions