DNA Sorting Contest Problem

DNASorting.c

/*
 * Mohamed Ennahdi El Idrissi
 */
#include <stdio.h>

/*
 * M is the length of the string ( 0 < M <= 100 )
 */
#define M 100
/*
 * N is the length of the string ( 0 < N <= 50 )
 */
#define N 50
/*
 * str is where we store DNA strings.
 */
char str[M][N];
/*
 * str2 is similar to str, its role is to save the original state of str.
 */
char str2[M][N];
/*
 * swappingNumberArray parallelly stores the number of swaps for each DNA string.
 */
int swappingNumberArray[M];
/*
 * function that swaps two characters.
 */
void swap(char *a, char *b) {
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
/*
 * This function counts the number of swaps in a DNA sequence
 * (n(n - 1)) / 2 => O(n²)
 */
int sort(char ch[], int m, int n) {
	int i, j, k, counter = 0;
	for (i = 0; i < n - 1; i++) {
		for (j = i + 1; j < n; j++) {
			if (ch[i] > ch[j]) {
				swap(&ch[i], &ch[j]);
				counter++;
			}
		}
	}
	return counter++;
}

int main() {
	/*
	 * n: string length
	 * m: number of strings
	 * i: loop index
	 * j: loop index
	 * temp: temporary value (used for swaps).
	 */
	unsigned int n, m, i, j, temp;
	char ch[N];
	
	scanf("%d %d", &n, &m);	
	/*
	 *	O(m  * n)
	 *	Reads m DNA strings
	 */
	for (i = 0; i < m; i++) {
		scanf("%s", str[i]);
		/*
		 *	strncpy => O(n)
		 */
		strncpy(str2[i], str[i], n);
		//strcpy(str2[i], str[i]);
		printf("\n %s %s\n", str[i], str2[i]);
	}
	/*
	 * 	swappingNumberArray stores the number of swaps for each DNA string.
	 *		- Browsing all strings is O(m)
	 *		- Counting the number of swaps is O(n²).
	 *	O( m * n² )
 	 */
	for (i = 0; i < m; i++) {
		swappingNumberArray[i] = sort(str[i], m, n);
	}

	/*
	 *	This fragment sorts the DNA strings according to the number of 
	 * 	swaps using the Insertion sort.
	 *
	 *	Insertion Sort O(n²):
	 *		O(n²) assignments	-	No swaps
	 *		O(n²) comparisons
	 */
	for (i = 1; i < m; i++) {
		temp = swappingNumberArray[i];
		/*
		 * strcpy() is O(n)
		 */
		strcpy(ch, str2[i]);
		j = i;
		/*
		 * W(n) = O(n)
		 * B(n) = O(1)
		 */
		while ((j > 0) && (swappingNumberArray[j - 1] > temp)) {
			swappingNumberArray[j] = swappingNumberArray[j - 1];
			strcpy(str2[j], str2[j - 1]);
			j--;
		}
		swappingNumberArray[j] = temp;
		/*
		 * strcpy() is O(n)
		 */
		strcpy(str2[j], ch);
	}
	printf("\n");
	/*
	 *	Displaying the strings.
	 *	For loop is O(m)
	 *	printf() is O(n)
	 *	=>	O( m * n)
	 */
	for (i = 0; i < m; i++) {
		printf("\n%s", str2[i]);
	}
	printf("\n");
	return 0;
}