Name: Anonymous 2013-05-23 4:36
There is nothing that recursion can do that can't be done simpler and more elegantly with a plain
for loop.
for loop.
def R(t, f)
if t
f[t]
R(t.l, f)
R(t.r, f)
end
end
recurse root, lambda {|t| print t}
L = [root]
while not L.empty?
t = L.pop
if t
f(t)
L.push(t.r)
L.push(t.l)
end
end#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define LEN 200
#define SUB_LIMIT 8
static void print_arr(const int *data, const int n)
{
int i;
printf("[%d", data[0]);
for (i = 1; i < n; ++i)
printf(", %d", data[i]);
printf("]\n");
}
/* explicit stack */
static int *explicit_stack;
static int stacklen = 0, stackpos = 0;
static void push(int i)
{
if (stackpos >= stacklen) {
stacklen *= 2;
explicit_stack = realloc(explicit_stack, stacklen * sizeof (int));
}
explicit_stack[stackpos++] = i;
}
static int pop(){
if (stackpos >= 0)
return explicit_stack[--stackpos];
return -1;
}
/* explicit stack */
/* like hell will I implement qsort down to width 1 */
static void subsort(int *data, int from, int to)
{
int *curr, temp_val, *temp, *min;
if (from < 0) from = 0;
if (to >= LEN) to = LEN - 1;
if (from >= to) return;
for (curr = data + from; curr <= data + to; ++curr) {
for (min = curr, temp = min + 1; temp <= data + to; ++temp)
if (*temp < *min)
min = temp;
temp_val = *curr;
*curr = *min;
*min = temp_val;
}
}
static int mid(const int a, const int b, const int c)
{
if (a < b)
return (b < c) ? b : c;
return (a < c) ? a : c;
}
/******************************************************************************
* vvv THIS IS THE FUNCTION YOU ASKED FOR vvv *
******************************************************************************/
void nonrec_qsort(int *data, const int o_from, const int o_to, int *holding) {
int midval, *lside, *rside, *curr, from, to;
from = o_from;
to = o_to;
i_bet_youd_rather_i_used_while_well_fuck_YOU:
if ((to - from) <= SUB_LIMIT) {
/* if set is small enough, use an n^2 sort */
subsort(data, from, to);
/* qsort always ends with subsorting the last sub-interval */
if (to == o_to) {
return;
}
from = to + 1;
to = pop();
} else {
/* partition and resize to leftmost side, storing rightmost index */
lside = holding + from;
rside = holding + to;
curr = data + from;
midval = mid(data[(from + to)/2], data[from], data[to]);
while (curr <= data + to) {
if (*curr < midval)
*lside++ = *curr;
else if (*curr > midval)
*rside-- = *curr;
curr++;
}
/* all values >, < midval have been taken care of, = must now be handled */
for (curr = lside; curr <= rside; ++curr)
*curr = midval;
memcpy(data + from, holding + from, (to - from + 1) * sizeof(int));
push(to);
to = curr - holding - 1;
}
goto i_bet_youd_rather_i_used_while_well_fuck_YOU;
}
/******************************************************************************
* ^^^ THIS IS THE FUNCTION YOU ASKED FOR ^^^ *
******************************************************************************/
int main()
{
int i, *data_to_sort, *holding;
/* this should be set up inside nonrec_qsort, but here for clarity */
stacklen = 1;
explicit_stack = (int *)calloc(stacklen, sizeof(int));
data_to_sort = (int *)calloc(LEN, sizeof(int));
holding = (int *)calloc(LEN, sizeof(int));
srand(time(NULL));
for (i = 0; i < LEN; ++i)
data_to_sort[i] = (rand() % 900) + 100;
print_arr(data_to_sort, LEN);
nonrec_qsort(data_to_sort, 0, LEN - 1, holding);
print_arr(data_to_sort, LEN);
free(data_to_sort);
free(holding);
free(explicit_stack);
return 0;
}
void nonrec_qsort(int *data, const int o_from, const int o_to, int *holding) {
int from = o_from, to = o_to;
stack *explicit_stack = make_stack();
while(true) {
if ((to - from) <= SUB_LIMIT) {
subsort(data, from, to);
if (to == o_to) {
free_stack(explicit_stack);
return;
}
from = to + 1;
to = pop(explicit_stack);
} else {
push(explicit_stack, to);
to = partition(data, from, to);
}
}
}int *holding parameter from the elegant version, of course, that was only used by the not-in-place implementation of partition().
+------------+
| グループ |
+------------+
グループ アドレス サイズ
===== ======= ====
DGROUP 00403000 0000a14d
+--------------+
| セグメント |
+--------------+
セグメント クラス グループ アドレス サイズ
========= ====== ========= ======== ======
_TEXT CODE AUTO 00401000 000017e6
CONST DATA DGROUP 00403000 000000cf
CONST2 DATA DGROUP 004030d0 00000000
_DATA DATA DGROUP 004030d0 00000042
_BSS BSS DGROUP 00403114 0000a039
+----------------+
| メモリ・マップ |
+----------------+
* = 参照されないシンボル
+ = シンボルはローカルでの参照のみです/* like hell will I implement qsort down to width 1 */partition() method is sufficient, the maximum depth of the stack can be calculated beforehand to remove the irritating realloc() calls (I think my version bounds it as (to-from)/2). Also, the touted multithreading of qsort can still be used, especially since the explicit stack allows forking/threading at a predetermined arbitrary level. So the non recursive version pretty much uses better than tail-recursion for both calls, and the only overhead is moving the stack from implicit to explicit representation.
goto. Furthermore, these gotos don't have to be at the very end of the function, so you don't have to rely on a magic position to make your code not suck.