Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 56

Write a C program for Binary Search.

Algorithm
Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure
Figure: Binary Search
C Programming Code

#include <stdio.h>
int binarySearch(int [], int, int, int);

int main()
{
    //!showArray(array)
  int array[10], c, first, last, n, search,  index;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  printf("Enter value to find\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;

  index = binarySearch(array, first, last, search);
 
  if (index == -1)
    printf("Not found! %d isn't present in the list.\n", search);
  else
    printf("%d is present at location %d.\n", search, index + 1);
 
  return 0;
} 

int binarySearch(int a[], int s, int e, int f) {
  int m;
 
  if (s > e) // Not found
     return -1;

  m = (s + e)/2;

  if (a[m] == f)  // element found
    return m;
  else if (f > a[m])  
    return binarySearch(a, m+1, e, f);
  else
    return binarySearch(a, s, m-1, f);
}

Output

Enter number of elements
5
Enter 5 integers
1
2
3
4
5
Enter value to find
5
5 is present at location 5.

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 55

Write a C program for Linear Search.

Algorithm

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure
Figure: Linear Search
C Programming Code

#include <stdio.h>
 
int linear_search(int [], int, int);
 
int main()
{
    //!showArray(array)
int array[10], search, c, n, position;
 
   printf("Input number of elements in array\n");
   scanf("%d", &n);
 
   printf("Input %d numbers\n", n);
 
   for (c = 0; c < n; c++)
      scanf("%d", &array[c]);
 
   printf("Input a number to search\n");
   scanf("%d", &search);
 
   position = linear_search(array, n, search);
 
   if (position == -1)
      printf("%d isn't present in the array.\n", search);
   else
      printf("%d is present at location %d.\n", search, position+1);
 
   return 0;
}
 
int linear_search(int a[], int n, int find) {
int c;
 
   for (c = 0 ;c < n ; c++ ) {
      if (a[c] == find)
         return c;
   }
 
   return -1;
}

Output

Input number of elements in array
5
Input 5 numbers
5
4
3
2
1
Input a number to search
1
1 is present at location 5.

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 54

Write a C program for Marge Sort.

Algorithm
MergeSort(A,p,r):

	if p < r
  q = ⌊ (p+r)/2 ⌋
	 MergeSort(A,p,q)
	 MergeSort(A,q+1,r)
	 Merge(A,p,q,r)

Merge(A,p,q,r):

	n1 = q - p + 1
	n2 = r - q
	let L, R be new arrays
	for i = 1 to n1
	 L[i] = A[p+i-1]
	for j = 1 to n2
	 R[j] = A[q+j]
	L[n1+1] = ∞
	R[n2+1] = ∞
	i = 1
	j = 1
	for k = p to r
	 if L[i] ≤ R[j]
	 A[k] = L[i]
	 i = i + 1
	 else
	 A[k] = R[j]
	 j = j + 1

Figure: Marge Sort
C Programming Code

#include <stdio.h>

void merge_sort(int i, int j, int a[], int aux[]) {
    if (j <= i) {
        return;
    }
    int mid = (i + j) / 2;

    merge_sort(i, mid, a, aux);
    merge_sort(mid + 1, j, a, aux);
    int pointer_left = i;
    int pointer_right = mid + 1;
    int k;

    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }

    for (k = i; k <= j; k++) {
        a[k] = aux[k];
    }
}

int main() {
    //!showSort(a)
    int a[5], aux[5], n, i;
    printf("Enter number of elements in the array:\n");
    scanf("%d", &n);
    printf("Enter %d integers\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    merge_sort(0, n - 1, a, aux);

    printf("Printing the sorted array:\n");
    for (i = 0; i < n; i++)
        printf("\t%d", a[i]);

    return 0;
}

Output

Enter number of elements in the array:
5
Enter 5 integers
5
4
3
2
1
Printing the sorted array:
	1	2	3	4	5

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 53

Write a C program for Quick Sort.

Algorithm

Quicksort(A,p,r):

	if p < r
	 q = Partition(A,p,r)
	 Quicksort(A,p,q - 1)
	 Quicksort(A,q + 1,r)

Partition(A,p,r):
	i = p-1
	for j = p to r-1
	 if A[j] ≤ A[r]
	 i = i + 1

	 exchange A[i] with A[j]
	exchange A[i+1] with A[r]
	return i+1

Figure: Quick Sort
C Programming Code

#include <stdio.h>
 
void print_array(int size, int array[]) {
    for (int pos = 0; pos < size; pos += 1) {
        printf("%d%s", array[pos], pos + 1 == size ? "" : " ");
    }
    printf("\n");
}
 
void quick_sort (int size, int array[], int left, int right) {
    //! quicksort = showSort(array, cursors=[left, right, i, j], dim=size, thresholds=[pivot])
    if (right <= left)
        return;
    int pivot = array[right];
    int i = left;
    int j = right;
    while (1) {
        while (array[i] < pivot)
            i += 1;
        while (pivot < array[j])
            j -= 1;
        if (i >= j) {
            break;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i += 1;
        j -= 1;
    }
    quick_sort(size, array, left, i - 1);
    quick_sort(size, array, i, right);
}
 
int main() {
    //! quicksort = showSort(array, dim=n)
    int array[] = {4, 2, 1, 2, 3, 2, 1, 0, 1};
    int n = sizeof array / sizeof *array;
    quick_sort(n, array, 0, n - 1);
    print_array(n, array);
    return 0;
}

Output

0 1 1 1 2 2 2 3 4

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 52

Write a C program for Insertion Sort.

Algorithm
for j = 2 to A.length
	 key = A[j]
	 i = j - 1
	 while i > 0 and A[i] > key
  A[i + 1] = A[i]
	 i = i - 1
	 A[i + 1] = key
Figure: Insertion Sort
C Programming Code

#include <stdio.h>

int main()
{
//!showSort(array)
  int n, array[5], c, d, t, flag = 0;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 1 ; c <= n - 1; c++) {
    t = array[c];

    for (d = c - 1 ; d >= 0; d--) {
      if (array[d] > t) {
        array[d+1] = array[d];
        flag = 1;
      }
      else
        break;
    }
    if (flag)
      array[d+1] = t;
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }

  return 0;
}

Output

Enter number of elements
5
Enter 5 integers
5
4
3
2
1
Sorted list in ascending order:
1
2
3
4
5

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 51

Write a C program for Selection Sort.

Algorithm
for i = 0 to A.length-2
 # find smallest item in A[i..]
	    m = i
	    for j = i+1 to A.length-1
        if A[j] < A[m]
	       m = j
 swap A[i] and A[m]
Figure: Selection Sort
C Programming Code

#include <stdio.h>
int main()
{
    //!showSort(array)
  int array[5], n, c, d, position, t;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 0; c < (n - 1); c++) // finding minimum element (n-1) times
  {
    position = c;

    for (d = c + 1; d < n; d++)
    {
      if (array[position] > array[d])
        position = d;
    }
    if (position != c)
    {
      t = array[c];
      array[c] = array[position];
      array[position] = t;
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c < n; c++)
    printf("%d\n", array[c]);

  return 0;
}

Output

Enter number of elements
5
Enter 5 integers
5
4
3
2
1
Sorted list in ascending order:
1
2
3
4
5

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 50

Write a C program for Bubble Sort.

Algorithm
procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            { if this pair is out of order }
            if A[i-1] > A[i] then
                { swap them and remember something changed }
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure
Figure: Bubble Sort

C Programming Code

#include <stdio.h>

int main()
{
    //!showSort(array)
  int array[5], n, c, d, swap;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 0 ; c < n - 1; c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (array[d] > array[d+1]) /* For decreasing order use '<' instead of '>' */
      {
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
      }
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c < n; c++)
     printf("%d\n", array[c]);

  return 0;
}

Output

Enter number of elements
5
Enter 5 integers
5
4
3
2
1
Sorted list in ascending order:
1
2
3
4
5

Md. Anisur Rahman C Programming Lab Manual

C Programming Lab Manual – 49

Write a C program for File input-output with a Pointer Using Recursion.

Algorithm

recursiveToThree(n)
    print n + 1, "th"
    if n < 3
        r = recursiveToThree(n + 1)
        n = r
    return n

Function Main()
    n = 0
    n = recursiveToThree(0)

    arr = [1, 2, 3]

    ptr = address of arr[2]
    set value at ptr to 5

    d_arry = allocate memory for 3 integers

    pd_arr[0] = allocate memory for 2 integers
    pd_arr[1] = allocate memory for 2 integers

    print "Hello, world!"

    free memory at pd_arr[0]

    open file "PLIVET.txt" for writing as fp
    write "PLIVET" to fp
    close fp

    open file "PLIVET.txt" for reading as fp
    buf = create buffer with size 7
    while read up to 10 characters from fp into buf is not NULL
        print buf
    close fp
End

Flow Chart

C Programming Code

#include<stdio.h>
int recursiveToThree(int n){
  printf("%d th\n", n + 1);
  if(n < 3){
      int r = recursiveToThree(n + 1);
      n = r;
  }
  return n;
}
int main(){
  int n = 0;//variable declaration

  n = recursiveToThree(0);//recursive function

  int arr[5] = {1, 2, 3};//array variable

  int* ptr = &arr[2];//pointer variable
  *ptr = 5;

  //dynamic memory allocation
  int* d_arry = malloc(sizeof(int) * 3);

  //two-dimensional dynamic array
  int* pd_arr[2];
  pd_arr[0] = malloc(sizeof(int) * 2);
  pd_arr[1] = malloc(sizeof(int) * 2);

  printf("Hello,world!\n");//standard output

  free(pd_arr[0]);//memory leak

  //File Output
  {
    FILE* fp=NULL;
    fp = fopen("PLIVET.txt", "w");
    fputs("PLIVET", fp);
    fclose(fp);
  }

  //File Input
  {
    FILE* fp=NULL;
    char buf[7];
    fp = fopen("PLIVET.txt", "r");
    while(fgets(buf,10,fp) != NULL) {
      printf("%s",buf);
    }
    fclose(fp);
  }
  return 0;
}

output

1 th
2 th
3 th
4 th
Hello,world!
PLIVET

Run this code in PLIVET or Others.

Md. Anisur Rahman C Programming Lab Manual

C Programming Lab Manual – 48

Write a C program for Variable with Pointer.

Algorithm

Function Main
Declare variables i, j as integers
Declare variable k as a pointer to integer

Read values for i and j from input

Print the values of i and j

If i is equal to 1 and j is equal to 2, then
    Print the product of i and j
Else
    Print the sum of i and j

Print the value pointed to by k (which is the value of j)

End

Flow Chart

C Programming Code

#include <stdio.h>
int main() {
//!showMemory()
  int i,j, *k= &j;
 
  scanf("%d%d", &i,&j);
  printf("i = %i, j = %i\n", i, j);
  if(i==1&&j==2)
  {
    printf("%d\n", i*j);
  }
  else{
  printf("%d\n",i+j);}
  printf("%d  //the values of Address of j",*k); //print the values of Address of j
}

output

1 2                                                                             
i = 1, j = 2                                                                    
2                                                                               
2  //the values of Address of j

Md. Anisur Rahman C Programming Lab Manual

C Programming Lab Manual – 47

Write a C program for Dynamic Memory Allocation(malloc).

Algorithm

Function Main
Declare N, sum, i as integers
Declare iptr, tmp as integer pointers
Print "Enter value of N [1-10]: "
Read N from user
Allocate memory for iptr with size N * sizeof(int)
If iptr is NULL
    Print "Unable to allocate memory space. Program terminated."
    Return -1
Print "Enter N integer number(s)"
For i from 0 to N-1
    Print "Enter #(i+1): "
    Read input and store it in tmp
   Add the value of tmp to sum
Print "Sum: ", sum
Free the memory allocated for iptr
End

Flow Chart

C Programming Code

#include <stdio.h>


int main(void) {
//!ShowMemory(start=1000)
    
  // integer variables
  int N = 0;
  int sum = 0;
  int i;
  
  // integer pointer variables
  int *iptr, *tmp;
  
  // take user input
  printf("Enter value of N [1-10]: ");
  scanf("%d", &N);
  
  // allocate memory
  iptr = (int *) malloc (N * sizeof(int));
  
  // check if memory allocated
  if (iptr == NULL) {
    printf("Unable to allocate memory space. Program terminated.\n");
    return -1;
  }
  
  // take integers
  printf("Enter %d integer number(s)\n", N);
  for (i = 0, tmp = iptr; i < N; i++, tmp++) {
    printf("Enter #%d: ", (i+1));
    scanf("%d", tmp);
    
    // compute the sum
    sum += *tmp;
  }
  
  // display result
  printf("Sum: %d\n", sum);
  
  // free memory location
  free(iptr);

  return 0;
}

output

Enter value of N [1-10]: 5
Enter 5 integer number(s)
Enter #1: 10
Enter #2: 20
Enter #3: 30
Enter #4: 40
Enter #5: 50
Sum: 150

More Example:

//Example: 02
#include <stdlib.h>
int main() {
    //! showMemory(start=1000)
    int * p = malloc(4 * sizeof(int));
    int * q = malloc(1 * sizeof(int));
    free(q);
    int * r = malloc(2 * sizeof(int));
    return 0;
}
//Run this code in C Programming Manual Tracing