qsortを再帰を使わずに書く

そういうお題が某所で提供されたので、せっかくだから解いてみる。
ちなみに出題者の方は僕より数日早く自分で解かれたようだった。。。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define ARR_SIZE     (20)
#define SHUFFLE_NUM  (1000)

typedef struct jobs {
  struct jobs* prevjob;
  int* start;
  size_t size;
} job_t;

void testqs(size_t size);
void printarr(int* arr, size_t size);
void myqsort(int* arr, size_t size);
int getpivot(int a0, int a1, int a2);

int getpivot(int a0, int a1, int a2)
{
  int retval = 0;
  if(a0 > a1) {
    if(a1 > a2) {
      retval = a1;
    }
    else if(a0 > a2) {
      retval = a2;
    }
    else {
      retval = a0;
    }
  }
  else if(a0 > a2) {
    retval = a0;
  }
  else if(a1 > a2) {
    retval = a2;
  }
  else {
    retval = a1;
  }
  return retval;
}

void myqsort(int* arr, size_t size)
{
  int* head;
  int* bottom;
  int sortsize;
  int pivot;
  int tmp;

  int* sav_head;
  int* sav_bottom;
  
  job_t* nowjob;
  job_t* addjob;
  job_t* lastjob;

  addjob = (job_t*)malloc(sizeof(job_t));
  addjob->prevjob = NULL;
  addjob->start = arr;
  addjob->size = size;
  lastjob = addjob;

  while(lastjob != NULL) {
    nowjob = lastjob;

    head = nowjob->start;
    sortsize = nowjob->size;
    bottom = head + sortsize - 1;
    
    sav_head = head;
    sav_bottom = bottom;

    lastjob = lastjob->prevjob;
    free(nowjob);

    if(sortsize < 2) {
    }
    else if(sortsize == 2) {
      if(*head > *bottom) {
        tmp = *head;
        *head = *bottom;
        *bottom = tmp;
      }
    }
    else {
      pivot = getpivot(*head, *(head+1), *(head+2));
      while(head < bottom) {
        if(*head > pivot) {
          while(head < bottom) {
            if(*bottom <= pivot) {
              tmp = *head;
              *head = *bottom;
              *bottom = tmp;
              bottom --;
              head++;
              break;
            }
            else {
              bottom --;
            }
          }
        }
        else {
          head++;
        }
      }
      while(head <= sav_bottom) {
        if( *head> pivot) {
          break;
        }
        head++;
      }
      if(head > sav_head) {
        addjob = (job_t*)malloc(sizeof(job_t));
        addjob->prevjob = lastjob;
        addjob->start = sav_head;
        addjob->size = head - sav_head;
        lastjob = addjob;
      }
      if(head < sav_bottom) {
        addjob = (job_t*)malloc(sizeof(job_t));
        addjob->prevjob = lastjob;
        addjob->start = head;
        addjob->size = sav_bottom - head + 1;
        lastjob = addjob;
      }
    }
  }
}
    
void testqs(size_t size)
{
  int* arr;
  int i;
  int a, b;
  int tmp;
  
  arr = (int*)malloc(sizeof(int) * size);
  memset(arr, 0, sizeof(int) * size);
  
  for(i = 0; i < size; i++) {
    arr[i] = i;
  }
  
  for(i = 0; i < SHUFFLE_NUM; i++) {
    a = rand() % size;
    b = rand() % size;
    tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
  }
  printarr(arr, size);
  myqsort(arr, ARR_SIZE);
  printarr(arr, size);
  free(arr);
}

void printarr(int* arr, size_t size)
{
  int i;
  
  for(i = 0; i < size -1; i++) {
    printf("%d, ", arr[i]) ;
    if ( i % 20 == 19 ) {
      printf("\n");
    }
  }
  printf("%d\n", arr[size - 1]);
}

int main(int argc, char** argv)
{
  int i;
  for(i=0; i< 10; i++) {
    testqs(ARR_SIZE);
  }
  return 0;
}

即席で作ったからコメント一切なし、
即席で作ったからmallocの返り値チェックなし、
作者の腕が悪いからコードは汚い

まあ、(たぶん(※))動いたからよしとしよう。

(※)適当なテストプログラム組んでみたらちゃんとソートされた。