Answer to Question #275253 in C for ojal

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<iostream>
#include<algorithm>
using namespace std;
void display(int *array, int size) {
   for(int i = 1; i<=size; i++)
      cout << array[i] << " ";
   cout << endl;
}
int getMax(int array[], int size) {
   int max = array[1];
   for(int i = 2; i<=size; i++) {
      if(array[i] > max)
         max = array[i];
   }
   return max;
}
void countSort(int *array, int size) {
   int output[size+1];
   int max = getMax(array, size);
   int count[max+1];  
   for(int i = 0; i<=max; i++)
      count[i] = 0;     
   for(int i = 1; i <=size; i++)
      count[array[i]]++;   
   for(int i = 1; i<=max; i++)
      count[i] += count[i-1];  
   for(int i = size; i>=1; i--) {
      output[count[array[i]]] = array[i];
      count[array[i]] -= 1;
   }
   for(int i = 1; i<=size; i++) {
      array[i] = output[i];
   }
}
int find(int *array, int target) {
 int idx = -1;
  for (int i= 0; i < sizeof(array)/sizeof(array[0]);i++)
   if (array[i] == target) { idx = i; break; }
 return idx;
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n+1];  
   cout << "Enter elements:" << endl;
   for(int i = 1; i<=n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   countSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
   int i = find(arr, 7);
   if (i == -1) cout << "Search item 7 is not found." << endl;
   else cout << "Search item 7 is found." << endl;
}