Answer to Question #276194 in C for MRM

Question

Write a program that reads the numbers and sorts them by using the Counting Sort algorithm and finally search a number from that array using Linear Search Algorithm.

Input: 3 6 5 4 7 8 9

Search Item: 7

Output:

Sorted Array: 3 4 5 6 7 8 9

Search item 7 is found. 

Answer 1

#include <stdio.h>


void countingSort(int numbers[], int size) {
	int count[10];
	int outputNumbers[10];
	// Find the largest element of the numbers
	int max = numbers[0];
	int i;
	for (i = 1; i < size; i++) {
		if (numbers[i] > max)
			max = numbers[i];
	}


	// Initialize count numbers with all zeros.
	for (i = 0; i <= max; ++i) {
		count[i] = 0;
	}


	// Store the count of each element
	for (i = 0; i < size; i++) {
		count[numbers[i]]++;
	}


	// Store the cummulative count of each numbers
	for (i = 1; i <= max; i++) {
		count[i] += count[i - 1];
	}


	for ( i = size - 1; i >= 0; i--) {
		outputNumbers[count[numbers[i]] - 1] = numbers[i];
		count[numbers[i]]--;
	}


	// Copy the sorted elements into original numbers
	for ( i = 0; i < size; i++) {
		numbers[i] = outputNumbers[i];
	}
}


bool linearSearch(int numbers[], int size, int k) {
	for (int i=0; i<size; i++) {
		if (numbers[i] == k) {
			return 1;
		}
	}
	return 0;
}


// Function to print an numbers
void printArray(int numbers[], int size) {
	for (int i = 0; i < size; ++i) {
		printf("%d  ", numbers[i]);
	}
	printf("\n");
}


// Driver code
int main() {
	const int N=100;
	int numbers[100];
	int size, target;


	printf("Enter number of elements: ");
	scanf("%d", &size);
	if (size > N) {
		printf("Error: %d is too big\n", size);
		return 1;
	}
	printf("Input: ");
	for (int i=0; i<size; i++) {
		scanf("%d", &target);
		numbers[i] = target;
	}
	printf("\nSearch Item: ");
	scanf("%d", &target);
	countingSort(numbers, size);
	printf("\nSorted Array:\n");
	printArray(numbers, size);


	printf("Search item %d ", target);
	if (linearSearch(numbers,size, target)) {
		printf("is found\n");
	}
	else {
		printf("is NOT found\n");
	}




	getchar();
	getchar();
	return 0;
}