Answer to Question #277948 in C for MD. Abdul Aziz

Question

we need c coding with this answer..

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 <stdio.h>


const int N = 1e5;


// count sort
void sort(int *arr, int n) {
  int count[N], x = 0;
  for (int i = 0; i < N; i++)
    count[i] = 0;
  for (int i = 0; i < n; i++)
    count[arr[i]]++;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < count[i]; i++)
      arr[x++] = i;
}


// binary searh
int find(int *arr, int n, int target) {
  int i = 0, j = n;
  while (i < j) {
    int m = (i + j) / 2;
    if (arr[m] == target) return m;
    else if (arr[m] > target) i = m + 1;
    else if (arr[m] < target) j = m - 1;
  }
  return -1;
}


int main() {
  int n; 
  scanf("%d", &n);
  int arr[n];
  for (int i = 0; i < n; i++)
    scanf("%d", &arr[i]);
    
  printf("Search Item: ");
  int item;
  scanf("%d", &item);
  sort(arr, n);
  printf("Sorted Array: ");
  for (int i = 0; i < n ; i++)
    printf("%d ", arr[i]);
  printf("\n");
  int idx = find(arr, n, item);
  if (idx == -1)
    printf("Search Item %d is not found.", item);
  else 
    printf("Search Item %d is found", item);
  return 0;
}