Last post we wrote a heap sort routine.
Let's now take it for a road test:
[<Fact>]
let HeapSortTest() =
let testArray = [|11.5; 8.5; 9.5; 28.0; 25.5; 15.0; 12.0; 11.0; 9.0; 7.5|]
let xArray = MathMod.heapSort testArray testArray.Length
let yArray = Array.sort testArray
for i = 0 to testArray.Length-1 do
Assert.InRange(xArray.[i],(yArray.[i]-0.0001),(yArray.[i]+0.0001))
Again, I use xUnit to test whether the array is being sorted properly. I use the Array method '.sort' to build a comparison array, against which I can compare my results. Of course, I could just used the built-in sort method in F# for this task, but then I would never have learned how the Heap Sort algorithm actually worked. I think it's kind of cool.
A sorting digression
While I was pawing through the Array module, I found two other very cool sorting functions: Array.sortBy and Array.sortWith
Array.sortBy takes an anonymous function and an array as arguments. It then sorts your array using your function to transform your data.
Here's an example. Suppose we have the following array and we want to sort it by absolute value.
let xArray0 = [|11.5; 8.5; -9.5; 28.0; 25.5; -15.0; 12.0; -11.0; 9.0; 7.5|]
let xArray1 = Array.sortBy (fun (x : float) -> Math.Abs x ) xArray0
We just pass the array into the sortBy function along with the anonymous function takes takes the absolute value of each element.
This is the result:
[|7.5; 8.5; 9.0; -9.5; -11.0; 11.5; 12.0; -15.0; 25.5; 28.0|]
Here's another example:
let yArray0 = [|"01/07/2009"; "07/04/2009"; "11/17/2009"; "12/25/2009"; "01/07/2008"; "11/13/2008"; "07/01/2007"; "9/1/2009"; "01/07/2009"; "01/07/2009"|]
We have an array of strings, but we don't want a string sort; rather we want a date sort. We just pass in an anonymous function that transforms the strings to dates; the sortBy function then sorts by date.
let yArray1 = Array.sortBy (fun (x : string) -> Convert.ToDateTime x ) yArray0
Here's the result::
[|"07/01/2007"; "01/07/2008"; "11/13/2008"; "01/07/2009"; "01/07/2009"; "01/07/2009"; "07/04/2009"; "9/1/2009"; "11/17/2009"; "12/25/2009"|]
The Array.sortWith function allows you to sort an array, whereby you specify the sorting rule. A simple example would be a descending sort:
let xArray0 = [|11.5; 8.5; -9.5; 28.0; 25.5; -15.0; 12.0; -11.0; 9.0; 7.5|]
let xArray2 = Array.sortWith (fun (x : float) (y : float) -> if y = x then 0 elif y > x then 1 else -1 ) xArray0
The result is:
[|28.0; 25.5; 12.0; 11.5; 9.0; 8.5; 7.5; -9.5; -11.0; -15.0|]
Now, let's try our car array:
type auto = {model : string; year : int; color : string; mpg : float }
let cars = [|{model = "Mustang"; year = 1969; color = "Black"; mpg = 11.5};
{model = "GTO"; year = 1966; color = "Primer Gray"; mpg = 8.5};
{model = "Cougar"; year = 1968; color = "Red"; mpg = 9.5};
{model = "VW Bug"; year = 1971; color = "Lime"; mpg = 28.0};
{model = "Camry"; year = 2004; color = "Tan"; mpg = 25.5};
{model = "Nova"; year = 1974; color = "White"; mpg = 15.0};
{model = "Charger"; year = 1971; color = "Red"; mpg = 12.0};
{model = "Dart"; year = 1963; color = "Light Green"; mpg = 11.0};
{model = "Comet"; year = 1964; color = "Black"; mpg = 9.0};
{model = "Mark IV"; year = 1970; color = "Silver"; mpg = 7.5} |]
let carsSorted = Array.sortWith (fun (x : auto) (y : auto) -> if x.mpg = y.mpg then 0 elif x.mpg > y.mpg then 1 else -1 ) cars
My sortWith function applies an anonymous function that compares each car's mpg. Obviously, I could use any characteristic of a car to use as my sorting criteria. Here's the result:
carsSorted = [|{model = "Mark IV"; year = 1970; color = "Silver"; mpg = 7.5} };
{model = "GTO"; year = 1966; color = "Primer Gray"; mpg = 8.5};
{model = "Comet"; year = 1964; color = "Black"; mpg = 9.0};
{model = "Cougar"; year = 1968; color = "Red"; mpg = 9.5};
{model = "Dart"; year = 1963; color = "Light Green"; mpg = 11.0};
{model = "Mustang"; year = 1969; color = "Black"; mpg = 11.5};
{model = "Charger"; year = 1971; color = "Red"; mpg = 12.0};
{model = "Nova"; year = 1974; color = "White"; mpg = 15.0};
{model = "Camry"; year = 2004; color = "Tan"; mpg = 25.5};
{model = "VW Bug"; year = 1971; color = "Lime"; mpg = 28.0} |]
This is excellent!