main.c

/**
 * Bubble sort, insertion sort and selective sort.
 * FA lab from 2nd March 2010
 * Stas Suscov <[email protected]>
 */

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

double attrs; // stored attributions
double comps; // stored comparisons

/**
 * Function to generate randomly an array
 * params: target array, lenght of it and salt used for rand()
 */
int r_gen(int ar[], int ar_lenght, int salt)
{
	int i;
	srand(time(NULL));
	for(i = 0; i < ar_lenght; i++)
	{
		ar[i] = rand()%salt;
	}
	return 0;
}

/**
 * Function to clone arrays
 * params: from array, to target array, lenght of both
 */
int ar_cpy(int *from, int *to, int lenght)
{
	int i;
	for(i = 0; i < lenght; i++)
	{
		to[i] = from[i];
	}
	return 0;
}

/**
 * Simple fuction to write into file some data
 * params: filename of the target file and the content to be written
 * return: 0 on success
 */
int w2file(char filename[100], char *data)
{
	FILE *fh = fopen(filename, "w+");
	fwrite(data, sizeof(char), sizeof(data), fh);
	fclose(fh);
	return 0;
}

/**
 * Prints and array
 * params: array to be printed and its lenght
 */
void ar_dump(int *ar, int ar_lenght, char delim)
{
	int i;
	for(i=0; i<ar_lenght; i++)
		printf("%d%c", ar[i], delim);
}

/**
 * Swaps two elements, a with b
 */
void swaps(int *ar, int a, int b) 
{
	int tmp;
	tmp = ar[a];
	ar[a] = ar[b];
	ar[b] = tmp;
	
	attrs++; //increment nr. of attributions
}

/**
 * Compares two elements, a with b
 * @return 0, if equal
 * @return -1, if a smaller than b
 * @return 1, if a greater than b
 */
int cmp(int a, int b)
{
	int r;
	if(a == b)
		r = 0;
	else if(a < b)
		r = -1;
	else
		r = 1;

	comps++; //increment the number of comparisons

	return r;
}

/**
 * Implementation of bubble sort alg.
 * params: array to be sorted and its lenght
 */
void bb_sort(int *ar, int ar_lenght)
{
	int i, j;
	for(i=0; i<ar_lenght; i++)
		for(j=0; j<(ar_lenght - i); j++)
			if(cmp(ar[j], ar[j+1]) == 1 )
				swaps(ar, j, j+1);
}

/**
 * Implementation of insertion sort alg.
 * params: array to be sorted and its lenght
 */
void ins_sort(int *ar, int ar_lenght)
{
	int i, j, temp;
	for(i = 1; i<ar_lenght; i++)
	{
		temp = ar[i];
		for(j=i-1; j>=0 && cmp(ar[j], temp) == 1; j--)
			ar[j+1] = ar[j];
		ar[j+1] = temp;
		attrs++;
	}
}

/**
 * Implementation of selection sort alg.
 * params: array to be sorted and its lenght
 */
int sel_sort(int *ar, int ar_lenght)
{
	while(ar_lenght>0)
	{
		int j;
		int max=0;
		for(j=1; j<ar_lenght; j++)
			if(cmp(ar[j], ar[max]) == 1)
				max = j;
		swaps(ar, ar_lenght-1, max);
		ar_lenght--;
	}
}

/**
 * Main
 */
int main()
{
	char filename[100] = "rez.out"; // results data file
	int incr_size = 100;
	int incr_max_size = 500;
	int ar_lenght = incr_size;	// lenght of our arrays

	int ar_of_sizes[incr_max_size - incr_size]; // array of computed ar_lenghts
	//Bubble sort data
	int ar_of_attrs_bb[incr_max_size - incr_size]; // array of stored nr. of attributions
	int ar_of_comps_bb[incr_max_size - incr_size]; // array of stored nr. of comparisons
	//Insertion sort data
	int ar_of_attrs_ins[incr_max_size - incr_size]; // array of stored nr. of attributions
	int ar_of_comps_ins[incr_max_size - incr_size]; // array of stored nr. of comparisons
	//Selection sort data
	int ar_of_attrs_sel[incr_max_size - incr_size]; // array of stored nr. of attributions
	int ar_of_comps_sel[incr_max_size - incr_size]; // array of stored nr. of comparisons

	while(ar_lenght < incr_max_size)
	{
		//initialize vars
		attrs = 0;
		comps = 0;

		int ar_bbs[ar_lenght];		// values array for bb_sort
		int ar_ins[ar_lenght];		// values array for ins_sort
		int ar_sel[ar_lenght];		// values array for sel_sort

		int i = ar_lenght - incr_size; // compute current queue id

		r_gen(ar_bbs, ar_lenght, incr_size);	// generate initial array

		/* clone our arrays from ar_bbs */
		ar_cpy(ar_bbs, ar_ins, ar_lenght);
		ar_cpy(ar_bbs, ar_sel, ar_lenght);

		ar_of_sizes[i] = ar_lenght;

		bb_sort(ar_bbs, ar_lenght);
			ar_of_attrs_bb[i] = attrs;
			ar_of_comps_bb[i] = comps;
		ins_sort(ar_ins, ar_lenght);
			ar_of_attrs_ins[i] = attrs;
			ar_of_comps_ins[i] = comps;
		sel_sort(ar_sel, ar_lenght);
			ar_of_attrs_sel[i] = attrs;
			ar_of_comps_sel[i] = comps;
		ar_lenght++;
	}

	printf("Array lenghts,");
		ar_dump(ar_of_sizes, incr_max_size - incr_size, ',');
	printf("\nBubble sort attr,");
		ar_dump(ar_of_attrs_bb, incr_max_size - incr_size, ',');
	printf("\nBubble sort comp,");
		ar_dump(ar_of_comps_bb, incr_max_size - incr_size, ',');
	printf("\nInsertion sort attr,");
		ar_dump(ar_of_attrs_ins, incr_max_size - incr_size, ',');
	printf("\nInsertion sort comp,");
		ar_dump(ar_of_comps_ins, incr_max_size - incr_size, ',');
	printf("\nSelection sort attr,");
		ar_dump(ar_of_attrs_sel, incr_max_size - incr_size, ',');
	printf("\nSelection sort comp,");
		ar_dump(ar_of_comps_sel, incr_max_size - incr_size, ',');

	return 0;
}