diff options
| author | herbelin | 2009-12-13 21:23:17 +0000 |
|---|---|---|
| committer | herbelin | 2009-12-13 21:23:17 +0000 |
| commit | f698148f6aee01a207ce5ddd4bebf19da2108bff (patch) | |
| tree | 54a1ddbec7c5cd5fe326e2e90d6a45317270aad8 /theories/Sorting/vo.itarget | |
| parent | ebc3fe11bc68ac517ff6203504c3d1d4640f8259 (diff) | |
Addition of mergesort + cleaning of the Sorting library
- New (modular) mergesort purely using structural recursion
- Move of the (complex) notion of permutation up to setoid equality
formerly defined in Permutation.v to file PermutSetoid.v
- Re-use of the file Permutation.v for making the canonical notion
of permutation that was in List.v more visible
- New file Sorted.v that contains two definitions of sorted:
"Sorted" is a renaming of "sort" that was defined in file
Sorting.v and "StronglySorted" is the intuitive notion of sorted
(there is also LocallySorted which is a variant of Sorted)
- File Sorting.v is replaced by a call to the main Require of the directory
- The merge function whose specification rely on counting elements is moved
to Heap.v and both are stamped deprecated (the sort defined in
Heap.v has complexity n^2 in worst case)
- Added some new naming conventions
- Removed uselessly-maximal implicit arguments of Forall2 predicate
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@12585 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'theories/Sorting/vo.itarget')
| -rw-r--r-- | theories/Sorting/vo.itarget | 4 |
1 files changed, 3 insertions, 1 deletions
diff --git a/theories/Sorting/vo.itarget b/theories/Sorting/vo.itarget index b14f8f7437..079eaad180 100644 --- a/theories/Sorting/vo.itarget +++ b/theories/Sorting/vo.itarget @@ -1,5 +1,7 @@ Heap.vo Permutation.vo -PermutEq.vo PermutSetoid.vo +PermutEq.vo +Sorted.vo Sorting.vo +Mergesort.vo |