NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commit904e8b6

committed

Replace insertion sort in contrib/intarray with qsort().

It's all very well to claim that a simplistic sort is fast in easycases, but O(N^2) in the worst case is not good ... especially if theworst case is as easy to hit as "descending order input". Replace thatbit with our standard qsort.Per bug #12866 from Maksym Boguk. Back-patch to all active branches.

1 parent837eb08 commit904e8b6Copy full SHA for 904e8b6

File tree

1 file changed

+23

-29

lines changed

contrib/intarray
- _int_tool.c

1 file changed

+23

-29

lines changed

`‎contrib/intarray/_int_tool.c‎`

Lines changed: 23 additions & 29 deletions

Original file line number	Diff line number	Diff line change
`@@ -184,40 +184,34 @@ rt__int_size(ArrayType a, float size)`
`184`	`184`	`*size= (float)ARRNELEMS(a);`
`185`	`185`	`}`
`186`	`186`
	`187`	`+/* qsort_arg comparison function for isort() */`
	`188`	`+staticint`
	`189`	`+isort_cmp(constvoida,constvoidb,void*arg)`
	`190`	`+{`
	`191`	`+int32aval=((constint32)a);`
	`192`	`+int32bval=((constint32)b);`
	`193`	`+`
	`194`	`+if (aval<bval)`
	`195`	`+return-1;`
	`196`	`+if (aval>bval)`
	`197`	`+return1;`
	`198`	`+`
	`199`	`+/*`
	`200`	`+ * Report if we have any duplicates. If there are equal keys, qsort must`
	`201`	`+ * compare them at some point, else it wouldn't know whether one should go`
	`202`	`+ * before or after the other.`
	`203`	`+ */`
	`204`	`+((bool)arg)= true;`
	`205`	`+return0;`
	`206`	`+}`
	`207`	`+`
`187`	`208`	`/* Sort the given data (len >= 2). Return true if any duplicates found */`
`188`	`209`	`bool`
`189`	`210`	`isort(int32*a,intlen)`
`190`	`211`	`{`
`191`		`-int32cur,`
`192`		`-prev;`
`193`		`-int32*pcur,`
`194`		`-*pprev,`
`195`		`-*end;`
`196`		`-boolr= FALSE;`
	`212`	`+boolr= false;`
`197`	`213`
`198`		`-/*`
`199`		`- * We use a simple insertion sort. While this is O(N^2) in the worst`
`200`		`- * case, it's quite fast if the input is already sorted or nearly so.`
`201`		`- * Also, for not-too-large inputs it's faster than more complex methods`
`202`		`- * anyhow.`
`203`		`- */`
`204`		`-end=a+len;`
`205`		`-for (pcur=a+1;pcur<end;pcur++)`
`206`		`-{`
`207`		`-cur=*pcur;`
`208`		`-for (pprev=pcur-1;pprev >=a;pprev--)`
`209`		`-{`
`210`		`-prev=*pprev;`
`211`		`-if (prev <=cur)`
`212`		`-{`
`213`		`-if (prev==cur)`
`214`		`-r= TRUE;`
`215`		`-break;`
`216`		`-}`
`217`		`-pprev[1]=prev;`
`218`		`-}`
`219`		`-pprev[1]=cur;`
`220`		`-}`
	`214`	`+qsort_arg(a,len,sizeof(int32),isort_cmp, (void*)&r);`
`221`	`215`	`returnr;`
`222`	`216`	`}`
`223`	`217`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit904e8b6

File tree

1 file changed

1 file changed

`‎contrib/intarray/_int_tool.c‎`

0 commit comments