1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML3.2 EN">
<HTML>
<HEAD> <link rel="canonical" href="http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Sys/PetscTimSort.html" />
<META NAME="GENERATOR" CONTENT="DOCTEXT">
<TITLE>PetscTimSort</TITLE>
</HEAD>
<BODY BGCOLOR="FFFFFF">
<div id="version" align=right><b>petsc-3.14.5 2021-03-03</b></div>
<div id="bugreport" align=right><a href="mailto:petsc-maint@mcs.anl.gov?subject=Typo or Error in Documentation &body=Please describe the typo or error in the documentation: petsc-3.14.5 v3.14.5 docs/manualpages/Sys/PetscTimSort.html "><small>Report Typos and Errors</small></a></div>
<A NAME="PetscTimSort"><H1>PetscTimSort</H1></A>
Sorts an array in place in increasing order using Tim Peters adaptive sorting algorithm.
<H3><FONT COLOR="#CC3333">Synopsis</FONT></H3>
<PRE>
#include "petscsys.h"
<A HREF="../Sys/PetscErrorCode.html#PetscErrorCode">PetscErrorCode</A> <A HREF="../Sys/PetscTimSort.html#PetscTimSort">PetscTimSort</A>(<A HREF="../Sys/PetscInt.html#PetscInt">PetscInt</A> n, void *arr, size_t size, int (*cmp)(const void *, const void *, void *), void *ctx)
</PRE>
Not Collective
<P>
<H3><FONT COLOR="#CC3333">Input Parameters</FONT></H3>
<TABLE border="0" cellpadding="0" cellspacing="0">
<TR><TD WIDTH=40></TD><TD ALIGN=LEFT VALIGN=TOP><B>n </B></TD><TD>- number of values
</TD></TR>
<TR><TD WIDTH=40></TD><TD ALIGN=LEFT VALIGN=TOP><B>arr </B></TD><TD>- array to be sorted
</TD></TR>
<TR><TD WIDTH=40></TD><TD ALIGN=LEFT VALIGN=TOP><B>size </B></TD><TD>- size in bytes of the datatype held in arr
</TD></TR>
<TR><TD WIDTH=40></TD><TD ALIGN=LEFT VALIGN=TOP><B>cmp </B></TD><TD>- function pointer to comparison function
</TD></TR>
<TR><TD WIDTH=40></TD><TD ALIGN=LEFT VALIGN=TOP><B>ctx </B></TD><TD>- optional context to be passed to comparison function, NULL if not needed
</TD></TR></TABLE>
<P>
<H3><FONT COLOR="#CC3333">Output Parameters</FONT></H3>
<TABLE border="0" cellpadding="0" cellspacing="0">
<TR><TD WIDTH=40></TD><TD ALIGN=LEFT VALIGN=TOP><B>arr </B></TD><TD>- sorted array
</TD></TR></TABLE>
<P>
<H3><FONT COLOR="#CC3333">Notes</FONT></H3>
Timsort makes the assumption that input data is already likely partially ordered, or that it contains contiguous
sections (termed 'runs') where the data is locally ordered (but not necessarily globally ordered). It therefore aims to
select slices of the array in such a way that resulting mergesorts operate on near perfectly length-balanced arrays. To
do so it repeatedly triggers attempts throughout to merge adjacent runs.
<P>
Should one run continuously "win" a comparison the algorithm begins the "gallop" phase. It will aggressively search
the "winner" for the location of the "losers" next entry (and vice versa) to copy all preceding elements into place in
bulk. However if the data is truly unordered (as is the case with random data) the immense gains possible from these
searches are expected __not__ to repay their costs. While adjacent arrays are almost all nearly the same size, they
likely all contain similar data.
<P>
<H3><FONT COLOR="#CC3333">Sample usage</FONT></H3>
The comparison function must follow the qsort() comparison function paradigm, returning the sign of the difference
between its arguments. If left < right : return -1, if left == right : return 0, if left > right : return 1. The user
may also
change or reverse the order of the sort by flipping the above. Note that stability of the sort is only guaranteed if
the comparison function forms a valid trigraph. For example when sorting an array of type "my_type" in increasing
order
<P>
<PRE>
int my_increasing_comparison_function(const void *left, const void *right, void *ctx) {
my_type l = *(my_type *) left, r = *(my_type *) right;
return (l < r) ? -1 : (l > r);
}
</PRE>
Note the context is unused here but you may use it to pass and subsequently access whatever information required
inside the comparison function. The context pointer will unaltered except for any changes made inside the comparison function.
Then pass the function
<PRE>
<A HREF="../Sys/PetscTimSort.html#PetscTimSort">PetscTimSort</A>(n, arr, sizeof(arr[0]), my_increasing_comparison_function, ctx)
</PRE>
<P>
<H3><FONT COLOR="#CC3333">Fortran Notes</FONT></H3>
To use this from fortran you must write a comparison subroutine with 4 arguments which accepts left, right, ctx and
returns result. For example
<PRE>
subroutine CompareIntegers(left,right,ctx,result)
implicit none
<A HREF="../Sys/PetscInt.html#PetscInt">PetscInt</A>,intent(in) :: left, right
type(UserCtx) :: ctx
integer,intent(out) :: result
if (left < right) then
result = -1
else if (left == right) then
result = 0
else
result = 1
end if
return
end subroutine CompareIntegers
</PRE>
<P>
<H3><FONT COLOR="#CC3333">References</FONT></H3>
1. - Tim Peters. https://bugs.python.org/file4451/timsort.txt
<P>
<P>
<H3><FONT COLOR="#CC3333">See Also</FONT></H3>
<A HREF="../Sys/PetscTimSortWithArray.html#PetscTimSortWithArray">PetscTimSortWithArray</A>(), <A HREF="../Sys/PetscIntSortSemiOrdered.html#PetscIntSortSemiOrdered">PetscIntSortSemiOrdered</A>(), <A HREF="../Sys/PetscRealSortSemiOrdered.html#PetscRealSortSemiOrdered">PetscRealSortSemiOrdered</A>(), <A HREF="../Sys/PetscMPIIntSortSemiOrdered.html#PetscMPIIntSortSemiOrdered">PetscMPIIntSortSemiOrdered</A>()
<BR><P><B></B><H3><FONT COLOR="#CC3333">Level</FONT></H3>developer<BR>
<H3><FONT COLOR="#CC3333">Location</FONT></H3>
</B><A HREF="../../../src/sys/utils/sortso.c.html#PetscTimSort">src/sys/utils/sortso.c</A>
<BR><A HREF="./index.html">Index of all Sys routines</A>
<BR><A HREF="../../index.html">Table of Contents for all manual pages</A>
<BR><A HREF="../singleindex.html">Index of all manual pages</A>
</BODY></HTML>
|
