Programs with line-by-line explanations
Prepared by: Dr. Tojo Mathew
Warning! You are warned against blindly copying the code statements. Read the explanations given for the code statements and understand the implementation. Then, try to do it yourself. Blindly re-typing the code statements is a waste of time & effort.
Table of contents
Note: Descriptions in brown font enclosed within /* and */ or starting with // are comments for human readers to understand the program better. No need to type in comments in the actual program. Compilers ignore comments while generating executable code of the program.
4.1 Bubble Sort
Write a C program to input N integer numbers into a single dimension array. Sort them in ascending order using bubble sort technique. Print both the given array and the sorted array with suitable headings.
Input Format:
The first input consists of an integer which corresponds to the number of elements present in the single dimension array.
The next n inputs are the elements in the array.
Output Format:
First line output consists of array elements before sorting and the next line of the output consists of array elements after sorting.
Refer sample input and output for formatting specifications.
[All text in bold corresponds to input and the rest corresponds to output]
Sample Input and Output:
Enter the number elements in the array :
5
Enter the elements of the array :
9
6
7
4
5
Before sorting the array :
9 6 7 4 5
After sorting the array :
4 5 6 7 9
Solution:
General description of program: The task to sort n randomly ordered input integers in ascending order using Bubble Sort Algorithm.
Solution Idea: Bubble sort is standard sorting in Computer Science. If N numbers are there, there will be at least N-1 passes. In pass 1, the adjacent numbers are swapped/exchanged in such a way that the largest number in the list reaches the last position(Bubbling). In pass 2, the process is repeated so that the 2nd largest number reaches 2nd last position. When N-1 passes are completed, N-1 elements will be in the sorted order that will also cause the smallest element to be in 1st position. This way the entire set of numbers is sorted in ascending order.
Animated demo of bubble sort: https://www.youtube.com/watch?v=NiyEqLZmngY
4.2 Binary Search
Write a C program to input N real numbers in ascending order into a single dimension array. Conduct a binary search for a given key integer number and report success or failure in the form of a suitable message.
Input Format:
The first input consists of an integer which corresponds to the number of elements present in the single dimension array.
The next n inputs are the elements in the array.
The next input consists of an integer which corresponds to the key element to be searched.
Output Format:
Output should display whether the key is present in the array or not.
Refer sample input and output for formatting specifications.
[All text in bold corresponds to input and the rest corresponds to output]
Sample Input and Output 1:
Enter the number of elements :
5
Enter the elements :
6
3
1
7
1
Enter the key to be searched :
1
The key is present in the array
At index 2
Sample Input and Output 2:
Enter the number of elements :
5
Enter the elements :
6
2
3
7
1
Enter the key to be searched :
2
The key is not present in the array
Solution:
General description of program: Binary search is a standard algorithm in computer science to search for a record in a large collection of records. The assumption is that the records are arranged in some order E.g: If records are integers, to apply binary search, the records should be arranged in ascending or descending order. Given a random integer as input(key), the program should apply binary search to check if the number is present in the set of records or not and display an appropriate message.
Solution idea: Assume the numbers are arranged in ascending order.
1. Pick the middle number in the collection. Compare the key with the middle value (mv).
2. If the key value is matching with the middle element, we are done! The key we
search is present in the collection of numbers.
3. If key < mv, then we can restrict the search to first half of the collection of numbers,
and repeat the steps 1-4 for this subset.
4. If key > mv, then we can restrict the search to second half of collection of numbers,
and repeat the steps 1-4 for this subset.
5. When there are no more elements left in the subset (i.e., lower index > upper index), the loop will terminate and we can conclude that the key element is not present in the collection of records (array).
Animated demo of binary search: https://www.youtube.com/watch?v=sr_bR1WwcLY
4.3 Matrix Addition
Write a C program to read two matrices A(M x N) and B(P x Q) and perform addition. Output the input matrices and the resultant matrix with suitable headings and format. (Using two dimensional arrays where array size M, N, P,Q ≤ 4)
Input Format:
The first input consists of an integer which corresponds to the number of elements present in the two dimension array.
The next n inputs are the elements of the first matrix and then followed by elements of the second matrix.
Output Format:
The output consists of the first matrix and then the second matrix and then the resultant matrix which corresponds to the addition of two matrices.
Print "Matrix addition is not possible" if the size(order) of two matrices is not the same.
Refer sample input and output for formatting specifications.
[All text in bold corresponds to input and the rest corresponds to output]
Sample Input and Output:
Enter the size of first matrix :
2
2
First matrix :
8
9
6
3
Enter the size of Second matrix :
2
2
Second matrix :
1
4
5
6
First input matrix :
8 9
6 3
Second input matrix :
1 4
5 6
Resultant matrix :
9 13
11 9
Solution:
General description of program: Add two matrices inputted by the user and display the resultant matrix.
Solution Idea: Create three 2-D arrays to store input matrices and the result matrix. Check if the dimension of both input matrices are matching. Perform element-by-element addition using a nested loop.
