Answer to Question #275228 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. 8 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 <iostream>
using namespace std;

void PrintArray(int a[], int n) {
    for (int i=0; i<n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

void CountingSort(int a[], int n, int m) {
    int *count = new int[m+1];
    int i, j, k;
    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;
        }
    }
}


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[] = {3, 6, 5, 4, 7, 8, 9};
    const int n = sizeof(a) / sizeof(a[0]);


    CountingSort(a, n, 9);
    cout << "Soreted Array: ";
    PrintArray(a, n);
    
    int k = 7;
    cout << "Search item " << k;
    if (LinearSearch(a, n, k)) {
        cout << " is found" << endl;
    }
    else {
        cout << " is not found" << endl;
    }
}