sort.c

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

#define swap(a,b)	swap_func(&a, &b)
void swap_func(int *a, int*b) {
	int t = *a;
	*a = *b;
	*b = t;
}

int binarySearch(int *a, int n, int x)
{
	if (n < 1)
		return -__INT32_MAX__;
	else if (n == 1)
		return a[n]==x ? n : -__INT32_MAX__;

	if (a[n/2] == x)
		return n/2;
	else if (a[n/2] < x)
		return n/2 + binarySearch(&a[n/2], n - n/2, x);
	else
		return binarySearch(a, n/2, x);
}

int partition(int *a, int n) {
	int part = -1;
	for(int i = 0; i < n - 1; i++) {
		if (a[i] < a[n-1])
			swap(a[++part],a[i]);
	}
	swap(a[++part], a[n-1]);
	return part;
}

void quickSort(int *a, int n)
{
	if (n <= 1)
		return;

	int p = partition(a, n);
	quickSort(a,p);
	quickSort(&a[p + 1],n-p-1);
}

void merge(int *a, int na, int nb)
{
	int *b = &a[na];
	int *c = (int*) malloc(sizeof(int)*(na + nb));

	int i = 0, j = 0;
	while(i < na && j < nb) {
		if (a[i] < b[j])
			c[i++ +j] = a[i];
		else
			c[i+ j++] = b[j];
	}

	if(i < na)
		while(i < na)
			c[i++ +j] = a[i];

	else if (j < nb)
		while(j < nb)
			c[i+ j++] = b[j];

	for(i = 0; i < na + nb; i++)
		a[i] = c[i];

	free(c);
}

void mergeSort(int *a, int n) {
	if (n < 2)
		return;
	mergeSort(a, n/2);
	mergeSort(&a[n/2], n-n/2);
	merge(a, n/2, n-n/2);
}

void heapify(int *h, int size, int index)
{
    int c1 = 2*index + 1;
    int c2 = 2*index + 2;
    int max_i = index;

    if (c2 < size)
		max_i = h[c1] > h[c2] ? c1 : c2;
    else if (c1 < size)
		max_i = c1;
    else
		return;

    if(h[index] < h[max_i]) {
		swap(h[index], h[max_i]);
		heapify(h, size, max_i);
    }
}

void heapSort(int *a, int n) {
    for (int i = (n - 2) / 2; i >= 0; i--)
		heapify(a, n, i);

	for(int i = n - 1; i > 0; i--) {
		swap(a[0],a[i]);
		heapify(a, i, 0);
	}
}

void insert(int *a, int n, int x) {
	for(int i = n-1; i>=0; i--) {
		if(a[i] > x)
			swap(a[i], a[i+1]);
		else {
			a[i+1] = x;
			break;
		}
	}
}

void insertionSort(int *a, int n) {
	for(int i = 1; i < n ; i++)
		insert(a, i, a[i]);
}

void bubbleSort(int *a, int n) {
	for(int i = 0; i < n - 1 ; i++) {
		for(int j = 0; j < n - i -1; j++){
			if(a[j] > a[j+1])
				swap(a[j],a[j+1]);
		}
	}
}

void selectionSort(int *a, int n) {
	for(int i = 0; i < n; i++) {
		int min = a[i];
		int min_i = i;
		for(int j = i; j < n; j++) {
			if(a[j] < min) {
				min = a[j];
				min_i = j;
			}
		}
		swap(a[i], a[min_i]);
	}
}

int main()
{
	int a[20] = {12,54,6,4,45,2,4,5,345,6,5,345,6,5,42,4,4,1,14,10};

	// selectionSort(a, 20);
	// bubbleSort(a,20);
	// insert(a,19,33);
	// insertionSort(a,20);
	// heapSort(a,20);
	// mergeSort(a, 20);
	// partition(a,20);
	quickSort(a,20);
	for(int i= 0; i<20; i++)
		printf("%d ", a[i]);
	printf("\n");

	int f;
	scanf("%d", &f);
	int i = binarySearch(a, 20, f);
	if(i > -1)
		printf("a[%d] = %d\n", i, a[i]);
	else
		printf("Not found\n");
	return 0;
}