kata-2013-09-30

sort.c

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

void print   (int *, int);
void swap    (int *, int, int);
void sort    (int *, int, int);
int  compare (int, int);
int  search  (int *, int, int);

int main(int argc, char const *argv[])
{
	int v[] = { 2, 5, 4, 1, 3, 0 };
	int len = sizeof(v) / sizeof(*v);

	printf("Before: ");
	print(v, len);

	sort(v, 0, len - 1);

	printf("After : ");
	print(v, len);

	printf("Search: %d\n", search(v, 3, len));

	return 0;
}

void print(int *v, int len)
{
	int i;

	i = 0;
	while(len-- > 0) {
		printf("%d ", *(v+i++));
	}
	printf("\n");
}

void swap(int *v, int i, int j)
{
	int temp = *(v+i);
	*(v+i) = *(v+j);
	*(v+j) = temp;
}

void sort(int *v, int left, int right)
{
	int i, last;

	if (left >= right) return;
	
	swap(v, left, (left + right) / 2);
	last = left;

	for(i = left + 1; i <= right; i++) {
		if (*(v+i) < *(v+left)) {
			swap(v, ++last, i);
		}
	}

	swap(v, left, last);
	sort(v, left, last - 1);
	sort(v, last + 1, right);
}

int compare(int a, int b)
{
	return a - b;
}

int search(int *v, int key, int len)
{
	int low, high, mid, comp;

	low  = 0;
	high = len - 1;

	while (low <= high) {
		mid = (low + high) / 2;
		if ((comp = compare(key, *(v+mid))) > 0) {
			low = mid + 1;
		} else if (comp < 0) {
			high = mid - 1;
		} else {
			return mid;
		}
	}

	return -1;
}