Answer to Question #275247 in C for pothik

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>
#include <stdlib.h>
#include <stdbool.h>

#define N 100


void PrintArray(int a[], int n) {
    for (int i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}


void CountingSort(int a[], int n, int m) {
    int *count;
    int i, j, k;


    count = malloc(sizeof(int)*(m+1));
    for (i=0; i<=m; i++) {
        count[i] = 0;
    }
    for (i=0; i<n; i++) {
        count[a[i]]++;
    }
    
    k = 0;
    for (i=0; i<=m; i++) {
        for (j=0; j<count[i]; j++) {
            a[k++] = i;
        }
    }
    free(count);
}

bool LinearSearch(int a[], int n, int k) {
    for (int i=0; i<n; i++) {
        if (a[i] == k) {
            return true;
        }
    }
    return false;
}

int main() {
    int a[N];
    int n, m, x;

    printf("Enter number of elements: ");
    scanf("%d", &n);
    if (n > N) {
        fprintf(stderr, "Error: %d is toot big\n", n);
        return 1;
    }

    printf("Input: ");
    m = 0;
    for (int i=0; i<n; i++) {
        scanf("%d", &x);
        a[i] = x;
        if (x > m) {
            m = x;
        }
    }
    printf("\nSearch Item:");
    scanf("%d", &x);

    CountingSort(a, n, 9);
    printf("Sorted Array: ");
    PrintArray(a, n);
        
    printf("Search item %d  ", x);
    if (LinearSearch(a, n, x)) {
        printf("is found\n");
    }
    else {
        printf("is not found\n");
    }

    return 0;
}