← Back to branch summary

~eda-qa/leaflang/cpp

« back to all changes in this revision

Viewing changes to share/std_library/std/quicksort.leaf

  • Committer: edA-qa mort-ora-y
  • Date: 2017-08-19 06:03:00 UTC
  • mfrom: (100.1.22 misc)
  • Revision ID: eda-qa@disemia.com-20170819060300-209dwd5884343mi0
merging miscelaneous changes, mainly platform improvements

Show diffs side-by-side

added added

removed removed

Lines of Context:
share/std_library/std/quicksort.leaf
 
1
@export
 
2
defn quicksort = ( a : vector｢any｣ shared, i : integer, k : integer ) -> () {
 
3
        quicksort_comp( a, i, k, (x,y) -> {
 
4
                return x < y
 
5
        })
 
6
}
 
7
 
 
8
//TODO: shouldn't need name quicksort_comp, overload with above should be okay
 
9
@export
 
10
defn quicksort_comp = ( list : vector｢any｣ shared, i : integer, k : integer, 
 
11
        compare : (:type_infer(list.data#0), :type_infer(list.data#0))->(:boolean) ) -> () {
 
12
        do i < k ? {
 
13
                var p = quicksort_partition( list, i, k, compare )
 
14
                quicksort_comp( list, i, p -1, compare )
 
15
                quicksort_comp( list, p + 1, k, compare )
 
16
        }
 
17
}
 
18
 
 
19
//TODO: These rest are exported due to a limitation, see mod_tests/parametric/forward_hide
 
20
@export defn quicksort_swap = (x : value_ptr, y : value_ptr ) -> {
 
21
        var z : value = x
 
22
        x := y
 
23
        y := z
 
24
}
 
25
 
 
26
@export defn quicksort_partition = ( list : vector｢any｣ shared, left : integer, right : integer,
 
27
        compare : (:type_infer(list.data#0), :type_infer(list.data#0))->(:boolean) ) -> {
 
28
        
 
29
        var pivot_index = quicksort_choose_pivot( left, right )
 
30
        var pivot_value = list.data#pivot_index
 
31
        quicksort_swap( list.data#pivot_index, list.data#right )
 
32
        
 
33
        var store_index = left
 
34
        for i in range(left,right) {
 
35
                do compare(list.data#i, pivot_value) ? {
 
36
                        quicksort_swap( list.data#i, list.data#store_index )
 
37
                        store_index = store_index + 1
 
38
                }
 
39
        }
 
40
        
 
41
        quicksort_swap( list.data#store_index, list.data#right )
 
42
        return store_index
 
43
}
 
44
 
 
45
@export defn quicksort_choose_pivot = ( left : integer, right : integer ) -> {
 
46
        return(left + right)/2
 
47
}
 
48