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
+----------------+
| メモリ・マップ |
+----------------+
* = 参照されないシンボル
+ = シンボルはローカルでの参照のみです