Introduction to Programming
Input/Output Data Files &
Searching, Sorting Applications
Objectives
You should be able to describe:
• Input/Output using Data Files
• Basic linear search in a non-ordered and ordered array.
• Bubble sort algorithm
2
Data Files
• For the programs with small amount of data we can store the data inside the
program or take a copy from the output screen. The data used in these programs is
stored in the memory and will not be available after the program is terminated.
• For large-size data, we should store/input data to/from a convenient storage/input
medium e.g. data files. Data files are stored on disks and can be used for
input/output. Besides providing permanent storage for data, data files can be
shared between programs, so the data one program outputs can be input in
another program.
• To store/retrieve data outside a C++
program, we need two things:
(1) A file
(2) A file stream object
Data Files
• A file is a collection of data stored under a common name, usually on a disk, USB drive, or CD/DVD.
Each stored data file has a unique filename, referred to as the file’s external name. The external
name is how the operating system (OS) knows the file. Data files can store data as Text or as Binary
codes.
• In C++ we need to create a file stream object to communicate with the data file.
• Input file stream objects are declared to be of type ifstream, and output file stream objects are
declared to be of type ofstream.
• For example, to declare an input file stream object named inFile:
ifstream inFile;
• Similarly, to declare an output file stream object named outFile:
ofstream outFile;
• Object names, such as inFile and outFile, can be any programmer-selected name that conforms to
C++’s identifier rules.
Data Files
• To store/write data using file stream objects, we need 3 steps:
1- Open the file (connect stream object with data file)
2- Read/Write data using file stream (usually similar to cin/cout)
3- Close the data file
Example 1:
The following is a complete C++ program that opens a data file and output (x, y) points of the
function f(x) = ex – 3x2 – 1 for -3 < x < 5. We can test the file is created by checking the current
folder. Also file contents can be checked using any suitable text editor (e.g. MS Notepad).
Steps: Create an ofstream object, Open the file with the specified name, Check if the file is
created successfully, Write the data using file stream object (same as cout << ), Close the file.
Data Files (input)
Example 2:
Write a complete C++ program that reads data created in Example 1. Display data on the
screen.
Steps:
Create an ifstream object,
Open the file with the specified name and the correct path,
Check if the file is opened successfully,
Read the data using file stream object (same as cin << ), continue reading while not
reaching the end of the file ( ! .eof() )
Close the file.
Sharing Data with other Programs:
Example 3: Use MS Excel to read the data file created in Example 1. Sketch/Plot the data.
Steps: Run Excel, Open/import the data file. Plot the data.
Searching Arrays
• Sometimes, we need to search an array for a specific value.
• We may also want to know the number of occurrences of a
specific value in an array.
• This application is called searching.
• Searching algorithms have many variations depending on
whether the array is sorted or not.
• Easiest algorithm is the Linear (Sequential) Search.
Sequential (Linear) Search
• In this search algorithm, we simply iterate through a list of elements
to find whether a given element is found in the list or not.
• Linear search algorithm has several variations depending on the
nature of the list and the desired output.
• We will consider the basic linear search where the array is not
sorted/sorted and when the desired output is whether the element is
found or it’s required to find the number of occurrences.
Example :Consider the following code segment that searches a list of n unsorted integer
elements to know if a particular value, number, is found or not. We assume that we
have at most 100 values. The input data sequence: 6 4 -1 7 6 2
The input data sequence:
6 4 -1 7 6 2
The trace table is:
i found number n list
[0] [1] [2] [3]
false 6 4 -1 7 6 2
0 false
1 false
2 true
The output will be: 6 is found at location 2
Example: Modify the previous code segment to calculate the
number of occurrences of a particular number in a list of n numbers.
If the input is: 6 4 -1 6 2 6, find the output.
Trace Table
i found number n list
[0] [1] [2] [3]
0 6 4 -1 6 2 6
0 0
1 1
2 1
3 2
The output will be: 6 is found 2 times
Sequential search in a sorted array
• If the array is sorted in a descending order. For example, the
elements of the array z[ ] are:
12 9 8 5 4 2 If we search for 7 ?
• If we want to search a number in a sorted array the steps are:
a) If the current element, z [ k ] equal to number, we stop searching
since we found the required element.
b) If number is greater than the current element, z [ k ], we stop
searching, since number can not be found through the remainder
elements of the array z.
c) If number < z [ k ] we move to the next element of the array.
Example: Consider the following code segment and find the o/p If the input is:
6 6 12 9 6 5 3 1 repeat if input : 7 6 12 9 8 5 4 2. How many times the while
loop executes?
int z[50]; int i, n, k, number; bool exit, found;
cin >> number >> n; Find o/p if: with 1st I/P if the
for (i = 0; i <= n - 1; i++) cin >> z[i]; following is changed:
exit = false; found = false; k = 0;
while ((k <= n - 1) && !(exit)) 1. for(i=n-1;i>=0;i--)
if (number == z[k]) cin>>z[i]
{
found = true; exit = true; 2. If while((k <= n-1) &&
} !(found)) with 2nd I/p
else if (number > z[k]) exit = true;
else k++;
if (found)
cout << number << " is found at position " << k << endl;
else
cout << number << " has not been found " << endl;
If the input is: 6 6 12 9 6 5 3 1 repeat if input : 7 6 12 9 8 5 4 2
number k found exit z
[0] [1] [2] [3] [4] [5]
6 12 9 6 5 3 1
false false
0 false false
1 false false
2 true true
The output will be: 6 is found in position 2
Exercise
Consider the given code segment and answer int main()
the following: {
int z[100];
1. If I/p is 60 6 88 80 77 64 55 40, find the
int i, n, k, x, found;
O/p, how many times the loop executes in
bool exist;
all cases?
cin >> x >> n;
2. Repeat if I/p is 90 6 88 80 77 64 55 40 for (i = 0; i <= n - 1; i++)
cin >> z[i];
3. If the for loop is changed to
found = 0; k = 0; exist = false;
for(i=n-1;i>=0;i--), what is the O/p, Is while ((k <= n - 1) && !(exist))
this correct? if (z[k]>x)
{
4. if (z[k]<x) with 1st I/p?
found++;
k++;
}
else
exist = true;
cout << "There exists" << found <<
"elements greater than " << x;
return 0;
}
Sorting
• Sorting takes an unordered collection and makes
it an ordered one.
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
5 12 35 42 77 101
Sorting
•Sorting data is placing the data into some particular order such as
ascending or descending
•We will discuss one sorting algorithm, which is the Bubble sort
•In the Bubble sort, we compare adjacent elements in the array
repeatedly and if necessary exchange them. Eventually, small values
move toward one end and large values move toward the other end.
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
77 42 35 12 101 5
Show the steps performed to sort 77, 42, 35, 12, 101, 5 using the
bubble sort?
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
42Swap
77 77
42 35 12 101 5
1 2 3 4 5 6
42 35Swap35
77 77 12 101 5
1 2 3 4 5 6
12Swap77
42 35 77 12 101 5
1 2 3 4 5 6
42 35 12 77 101 5
No need to swap
1 2 3 4 5 6
42 35 12 77 5 Swap 101
101 5
1 2 3 4 5 6
35 12 77 5 Largest value correctly placed
42 101
Repeat “Bubble Up” How Many Times?
• If we have N elements…
• And if each time we bubble an element, we
place it in its correct location…
• Then we repeat the “bubble up” process N – 1
times.
• This guarantees we’ll correctly
place all N elements.
“Bubbling” All the Elements
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
N-1
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
1 2 3 4 5 6
5 12 35 42 77 101
Reducing the Number of Comparisons
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
Example. The following code segment sorts a list of numbers in an ascending order
using Bubble sort.
int a[100]; int k, j, temp, i, n;
cin >> n; Consider the input values and trace the code:
for (i = 0; i <= n - 1; i++) 5 12 16 50 24 4
cin >> a[i];
for (k = n - 2; k >= 0; k--) What if it is required to sort in a descending
for (j = 0; j <= k; j++) order?
if (a[j] > a[j + 1])
{
temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
cout << "the sorted list is:";
for (i = 0; i <= n - 1; i++)
cout << a[i] << " ";
Solution n k j a
[0] [1] [2] [3] [4]
5 12 16 50 24 4
3 0 12 16 50 24 4
1 12 16 50 24 4
2 12 16 24 50 4
3 12 16 24 4 50
2 0 12 16 24 4 50
1 12 16 24 4 50
2 12 16 4 24 50
1 0 12 16 4 24 50
1 12 4 16 24 50
The output will be: 0 0 4 12 16 24 50
The sorted list is: 4 12 16 24 50