Recursion is stupid and wasteful

There is nothing that recursion can do that can't be done simpler and more elegantly with a plain for loop.

>>32
#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;
}

That's so you can run it and see if it works.  If you remove the explicit partition code (which everyone always does when they try to show off how sexy and ELEGANT qsort is), it's


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);
    }
  }
}

I think it's a little less elegant than recursive qsort (I'm not OP), but it's not a horrible monster.