qsort.c

#include <stdio.h>

void print_array(int begin_index, int end_index, int array[]) {
  int i;
  for(i = begin_index; i <= end_index; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
}

int find_bigger_index(int begin_index, int end_index, int pivot, int array[]) {
  int i;
  for(i = begin_index; i <= end_index; ++i) {
    if(array[i] >= pivot) {
      return i;
    }
  }
  return end_index;
}

int find_smaller_index(int begin_index, int end_index, int pivot, int array[]) {
  int i;
  for(i = begin_index; end_index <= i; --i) {
    if(array[i] <= pivot) {
      return i;
    }
  }
  return end_index;
}

void swap(int l, int r, int array[]) {
  if(l == r) {
    return ;
  }
  int buf = array[l];
  array[l] = array[r];
  array[r] = buf;
}

void qsort(int begin_index, int end_index, int array[]) {
  int bigger_index = begin_index;
  int smaller_index = end_index;
  int size = end_index - begin_index + 1;
  int pivot_index = bigger_index + (size / 2);
  int pivot = array[pivot_index];
  int boundary_index = smaller_index;

  if(size <= 1) {
    return ;
  }

  while(bigger_index < smaller_index) {
    bigger_index  = find_bigger_index(bigger_index, end_index, pivot, array);
    smaller_index = find_smaller_index(smaller_index, begin_index, pivot, array);
    if(bigger_index < smaller_index) {
      swap(bigger_index, smaller_index, array);
      boundary_index = smaller_index;
      bigger_index ++;
      smaller_index --;
    }
  }

  qsort(begin_index, boundary_index -1, array);
  qsort(boundary_index + 1, end_index, array);
}

int main() {
  int array[8] = {8,4,3,7,6,5,2,1};
  print_array(0, 7, array);
  qsort(0, 7, array);
  print_array(0, 7, array);
  return 0;
}