** Quicksort algorithm (recursive function) */
| 339 | ** Quicksort algorithm (recursive function) |
| 340 | */ |
| 341 | static void auxsort (lua_State *L, IdxT lo, IdxT up, unsigned rnd) { |
| 342 | while (lo < up) { /* loop for tail recursion */ |
| 343 | IdxT p; /* Pivot index */ |
| 344 | IdxT n; /* to be used later */ |
| 345 | /* sort elements 'lo', 'p', and 'up' */ |
| 346 | geti(L, 1, lo); |
| 347 | geti(L, 1, up); |
| 348 | if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ |
| 349 | set2(L, lo, up); /* swap a[lo] - a[up] */ |
| 350 | else |
| 351 | lua_pop(L, 2); /* remove both values */ |
| 352 | if (up - lo == 1) /* only 2 elements? */ |
| 353 | return; /* already sorted */ |
| 354 | if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ |
| 355 | p = (lo + up)/2; /* middle element is a good pivot */ |
| 356 | else /* for larger intervals, it is worth a random pivot */ |
| 357 | p = choosePivot(lo, up, rnd); |
| 358 | geti(L, 1, p); |
| 359 | geti(L, 1, lo); |
| 360 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ |
| 361 | set2(L, p, lo); /* swap a[p] - a[lo] */ |
| 362 | else { |
| 363 | lua_pop(L, 1); /* remove a[lo] */ |
| 364 | geti(L, 1, up); |
| 365 | if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ |
| 366 | set2(L, p, up); /* swap a[up] - a[p] */ |
| 367 | else |
| 368 | lua_pop(L, 2); |
| 369 | } |
| 370 | if (up - lo == 2) /* only 3 elements? */ |
| 371 | return; /* already sorted */ |
| 372 | geti(L, 1, p); /* get middle element (Pivot) */ |
| 373 | lua_pushvalue(L, -1); /* push Pivot */ |
| 374 | geti(L, 1, up - 1); /* push a[up - 1] */ |
| 375 | set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ |
| 376 | p = partition(L, lo, up); |
| 377 | /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ |
| 378 | if (p - lo < up - p) { /* lower interval is smaller? */ |
| 379 | auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ |
| 380 | n = p - lo; /* size of smaller interval */ |
| 381 | lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ |
| 382 | } |
| 383 | else { |
| 384 | auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ |
| 385 | n = up - p; /* size of smaller interval */ |
| 386 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ |
| 387 | } |
| 388 | if ((up - lo) / 128 > n) /* partition too imbalanced? */ |
| 389 | rnd = l_randomizePivot(L); /* try a new randomization */ |
| 390 | } /* tail call auxsort(L, lo, up, rnd) */ |
| 391 | } |
| 392 | |
| 393 | |
| 394 | static int sort (lua_State *L) { |
no test coverage detected