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.
7.1 Linear Search
Write C program for user-defined functions:
1. To input N integer numbers into a single dimension array.
2. To conduct a linear search.
Using these functions, write a C program to accept the N integer numbers & given key integer number and conduct a linear search. Report success or failure in the form of a suitable message.
Function Specification:
void search(int a[ ],int b,int n)
This function will search whether the element 'b' is present in an array "a" of size n. And print "The key is present in the array." if found else print "The key is not present in the array.".
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:
The 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 the 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 :
3
The key is present in the array.
At index 1
Sample Input and Output 2:
Enter the number of elements :
5
Enter the elements :
6
3
1
7
1
Enter the key to be searched :
2
The key is not present in the array.
Solution:
General description of program: Search to check the presence of a specific value (key) in an array (collection) of integers and display the output appropriately. Use user defined functions to take the input from the user and perform search.
Solution idea:
1. Given the key value and the array of numbers, use a loop to compare the key value with each element in the array, starting with the first element in the array at index 0.
2. If the key is matching with any of the array elements, display the output as the element found and exit the program.
3. After comparing with all the elements in the array, if no match is found, display output as an element not present in the array.
Note :
* Define your functions to get input from the user and to perform search.
* This algorithm is called linear search because we compare the key value with all elements in the 1-D array in a linear manner, starting with the 1st element. The search is performed until we find a match or there are no more elements left in the array to compare with.
Animated demo of linear search: https://www.youtube.com/watch?v=sr_bR1WwcLY
7.2 Sorting in Descending Order (Selection sort algorithm)
Write C program for user defined functions:
To input N integer numbers into a single dimension array.
To sort the integer numbers in descending order using selection sort technique.
To print the single dimension array elements.
Using these functions, write a C program to input N integer numbers into a single dimension array, sort them in descending order, and print both the given array & 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 the elements in descending order.
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
5
8
3
Before sorting the array :
9 6 5 8 3
After sorting the array :
9 8 6 5 3
General description of program: Selection sort is a standard algorithm in computer science to numbers (records in general) in ascending or descending order. The high level strategy of the algorithm goes this way. Assume it is an descending order sort of integers. First, the largest number in the array is located and exchanged with the first element. Hence, the largest element reaches the first position i.e., its final position when the array is sorted. From the remaining elements, largest is taken & placed at second position of the array (It's final position when array is sorted. This process is repeated for n-1 elements in the array such that all of them reach the correct position as per sorted order. That indirectly causes the nth element also to be in the final position. Finally the array is in sorted order.
The algorithm is demonstrated as an animation here (Ascending order sort where smallest element is picked & placed at start): https://www.youtube.com/watch?v=EdUWyka7kpI
