** QuickSort algorithm (recursive function) */
| 359 | ** QuickSort algorithm (recursive function) |
| 360 | */ |
| 361 | static void auxsort (lua_State *L, IdxT lo, IdxT up, |
| 362 | unsigned int rnd) { |
| 363 | while (lo < up) { /* loop for tail recursion */ |
| 364 | IdxT p; /* Pivot index */ |
| 365 | IdxT n; /* to be used later */ |
| 366 | /* sort elements 'lo', 'p', and 'up' */ |
| 367 | lua_geti(L, 1, lo); |
| 368 | lua_geti(L, 1, up); |
| 369 | if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ |
| 370 | set2(L, lo, up); /* swap a[lo] - a[up] */ |
| 371 | else |
| 372 | lua_pop(L, 2); /* remove both values */ |
| 373 | if (up - lo == 1) /* only 2 elements? */ |
| 374 | return; /* already sorted */ |
| 375 | if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ |
| 376 | p = (lo + up)/2; /* middle element is a good pivot */ |
| 377 | else /* for larger intervals, it is worth a random pivot */ |
| 378 | p = choosePivot(lo, up, rnd); |
| 379 | lua_geti(L, 1, p); |
| 380 | lua_geti(L, 1, lo); |
| 381 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ |
| 382 | set2(L, p, lo); /* swap a[p] - a[lo] */ |
| 383 | else { |
| 384 | lua_pop(L, 1); /* remove a[lo] */ |
| 385 | lua_geti(L, 1, up); |
| 386 | if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ |
| 387 | set2(L, p, up); /* swap a[up] - a[p] */ |
| 388 | else |
| 389 | lua_pop(L, 2); |
| 390 | } |
| 391 | if (up - lo == 2) /* only 3 elements? */ |
| 392 | return; /* already sorted */ |
| 393 | lua_geti(L, 1, p); /* get middle element (Pivot) */ |
| 394 | lua_pushvalue(L, -1); /* push Pivot */ |
| 395 | lua_geti(L, 1, up - 1); /* push a[up - 1] */ |
| 396 | set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ |
| 397 | p = partition(L, lo, up); |
| 398 | /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ |
| 399 | if (p - lo < up - p) { /* lower interval is smaller? */ |
| 400 | auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ |
| 401 | n = p - lo; /* size of smaller interval */ |
| 402 | lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ |
| 403 | } |
| 404 | else { |
| 405 | auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ |
| 406 | n = up - p; /* size of smaller interval */ |
| 407 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ |
| 408 | } |
| 409 | if ((up - lo) / 128 > n) /* partition too imbalanced? */ |
| 410 | rnd = l_randomizePivot(); /* try a new randomization */ |
| 411 | } /* tail call auxsort(L, lo, up, rnd) */ |
| 412 | } |
| 413 | |
| 414 | |
| 415 | static int sort (lua_State *L) { |
no test coverage detected