Feature #6256 » rubyqisort4.patch
| util.c (working copy) | ||
|---|---|---|
|
((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))
|
||
|
typedef int (cmpfunc_t)(const void*, const void*, void*);
|
||
|
static void
|
||
|
ruby_isort(char *l, char *r, cmpfunc_t *cmp, void *d, const size_t size)
|
||
|
{
|
||
|
char *p, *q, *v;
|
||
|
size_t i;
|
||
|
v = ALLOCA_N(char, size);
|
||
|
for(p = l + size; p <= r; p += size) {
|
||
|
if (cmp(p - size, p, d) <= 0)
|
||
|
continue;
|
||
|
memcpy(v, p, size);
|
||
|
i = 1;
|
||
|
for (q = p - 2 * size; q >= l && cmp(q, v, d) > 0; q -= size) {
|
||
|
i++;
|
||
|
}
|
||
|
memmove(q + 2 * size, q + size, i * size);
|
||
|
memcpy(q + size, v, size);
|
||
|
}
|
||
|
}
|
||
|
void
|
||
|
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
|
||
|
{
|
||
| ... | ... | |
|
register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */
|
||
|
char *L = base; /* left end of current region */
|
||
|
char *R = (char*)base + size*(nel-1); /* right end of current region */
|
||
|
size_t chklim = 63; /* threshold of ordering element check */
|
||
|
size_t chklim = 9; /* threshold of ordering element check */
|
||
|
stack_node stack[32], *top = stack; /* 32 is enough for 32bit CPU */
|
||
|
int mmkind;
|
||
|
size_t high, low, n;
|
||
| ... | ... | |
|
if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;
|
||
|
}
|
||
|
n = (R - L + size) / size; /* number of elements */
|
||
|
if (n < chklim) { /* Sort small sub problems (9 is empirical) with insertion sort */
|
||
|
ruby_isort(L, R, cmp, d, size);
|
||
|
goto nxt;
|
||
|
}
|
||
|
l = L; r = R;
|
||
|
n = (r - l + size) / size; /* number of elements */
|
||
|
m = l + size * (n >> 1); /* calculate median value */
|
||
|
if (n >= 60) {
|
||
| ... | ... | |
|
fail: goto loopA; /*3-5-7*/
|
||
|
}
|
||
|
if (t > 0) {
|
||
|
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/
|
||
|
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/
|
||
|
mmrot3(r,m,l); goto loopA; /*3-5-2*/
|
||
|
}
|
||
|
goto loopB; /*3-5-5*/
|
||
| ... | ... | |
|
if (t > 0) { /*7-5-?*/
|
||
|
if ((t = (*cmp)(m,r,d)) > 0) { /*7-5-3*/
|
||
|
if (chklim && nel >= chklim) { /* check if already ascending order */
|
||
|
if (chklim && nel >= chklim) { /* check if already descending order */
|
||
|
char *p;
|
||
|
chklim = 0;
|
||
|
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
|
||
| benchmark/bm_sort_int.rb (revision 0) | ||
|---|---|---|
|
Array.new(1000000) { |i| i }.shuffle!.sort!
|
||
| benchmark/bm_sort_int_custom.rb (revision 0) | ||
|---|---|---|
|
ary = Array.new(100000) { |i| i }.shuffle!
|
||
|
ary.sort { |x, y| -(x <=> y) }
|
||
| benchmark/bm_sort_int_sorted.rb (revision 0) | ||
|---|---|---|
|
Array.new(1000000) { |i| i }.sort!
|
||
| benchmark/bm_sort_str_rnd.rb (revision 0) | ||
|---|---|---|
|
prng = Random.new(42)
|
||
|
Array.new(100000) { prng.bytes(15) }.sort!
|
||