NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commit40b0c10

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 parent396ef6f commit40b0c10Copy full SHA for 40b0c10

File tree

1 file changed

+25

-26

lines changed

contrib/intarray
- _int_tool.c

1 file changed

+25

-26

lines changed

`‎contrib/intarray/_int_tool.c`

Lines changed: 25 additions & 26 deletions

Original file line number	Diff line number	Diff line change
`@@ -195,39 +195,38 @@ rt__int_size(ArrayType a, float size)`
`195`	`195`	`return;`
`196`	`196`	`}`
`197`	`197`
	`198`	`+/* qsort_arg comparison function for isort() */`
	`199`	`+staticint`
	`200`	`+isort_cmp(constvoida,constvoidb,void*arg)`
	`201`	`+{`
	`202`	`+int4aval=((constint4)a);`
	`203`	`+int4bval=((constint4)b);`
	`204`	`+`
	`205`	`+if (aval<bval)`
	`206`	`+return-1;`
	`207`	`+if (aval>bval)`
	`208`	`+return1;`
	`209`	`+`
	`210`	`+/*`
	`211`	`+ * Report if we have any duplicates. If there are equal keys, qsort must`
	`212`	`+ * compare them at some point, else it wouldn't know whether one should go`
	`213`	`+ * before or after the other.`
	`214`	`+ */`
	`215`	`+((bool)arg)= true;`
	`216`	`+return0;`
	`217`	`+}`
`198`	`218`
`199`		`-/* len >= 2 */`
	`219`	`+/Sort the given data (len >= 2). Return true if any duplicates found /`
`200`	`220`	`bool`
`201`	`221`	`isort(int4*a,intlen)`
`202`	`222`	`{`
`203`		`-int4tmp,`
`204`		`-index;`
`205`		`-int4*cur,`
`206`		`-*end;`
`207`		`-boolr= FALSE;`
`208`		`-`
`209`		`-end=a+len;`
`210`		`-do`
`211`		`-{`
`212`		`-index=0;`
`213`		`-cur=a+1;`
`214`		`-while (cur<end)`
`215`		`-{`
`216`		`-if ((cur-1)>cur)`
`217`		`-{`
`218`		`-tmp=*(cur-1);`
`219`		`-(cur-1)=cur;`
`220`		`-*cur=tmp;`
`221`		`-index=1;`
`222`		`-}`
`223`		`-elseif (!r&&(cur-1)==cur)`
`224`		`-r= TRUE;`
`225`		`-cur++;`
`226`		`-}`
`227`		`-}while (index);`
	`223`	`+boolr= false;`
	`224`	`+`
	`225`	`+qsort_arg(a,len,sizeof(int4),isort_cmp, (void*)&r);`
`228`	`226`	`returnr;`
`229`	`227`	`}`
`230`	`228`
	`229`	`+/* Create a new int array with room for "num" elements */`
`231`	`230`	`ArrayType*`
`232`	`231`	`new_intArrayType(intnum)`
`233`	`232`	`{`

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!

Commit40b0c10

File tree

1 file changed

1 file changed

`‎contrib/intarray/_int_tool.c`

0 commit comments