Programming Fundamentals Lab Lab 02

Name ____________________ Roll No._______________________

Arrays 1D, Sorting Algorithms (Bubble sort, Selection Sort)

Lab Objectives:
After completing this lab, the students should be able to
Explain the syntax of array declaration, array assignments and array initialization in C++.
Write programs to model repetitive data using arrays
Manipulate the array data structure.
Sorting the elements of an array

Background:
Array is a data structure that groups together entries of similar data type. Arrays can be used to represent
polynomials and matrices.

One-Dimensional Arrays:
So far we have talked about a variable as a single location in the computer’s memory. It is possible to have a
collection of memory locations, all of which have the same data type, grouped together under one name. Such a
collection is called an array. Like every variable, an array must be defined so that the computer can “reserve” the
appropriate amount of memory. This amount is based upon the type of data to be stored and the number of locations,
i.e., size of the array, each of which is given in the definition.
 Syntax of array in C++:
The syntax of array in C++ is as follows:
type array_name [size];
type array_name [size] = {list of array values};
Here the type is a variable type defined in C++ such as int, double, char, etc. The type can also be a user defined
type or a class defined in C++.
Example:
int a[5]; // array declared without initialization
int a[5] = {1, 2, 3}; // array declared with 5 entries but only 3 initialized (the rest two will be 0).
int a[5] = {1, 2, 3, 4, 5, 6}; // this definition is invalid. It may compile but will crash at run time since the number of
entries initialized exceeds the array size.
Example:
Example 3. int a __gc [ ] = new int __ gc [5]; // equivalent of int a[5];
Example 4. int a __gc [ ] = { 1, 2, 3, 4, 5}; // equivalent of int a[5] = {1, 2, 3, 4, 5};
Pre-labs:
1. Which of the following array declaration and / or initialization is valid (no compile or run time error)? State the
reasons.
int a[80]; (b) int a[10] = {0}; (c) int a [10] = {50}; (d) int a[3] = {0, 1, 2, 3}; (e) int a[ ] = {0, 1,2};
_____________________________________________________________________________________________
____________________________________________________________________________________________

2. Write code to initialize an integer array of 1000 elements to {1, 2, 3, 4, 5, …, 1000}.

_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
____________________________________________________________________________________________

1
Programming Fundamentals Lab Lab 02
3. Write code to initialize an integer array of 1000 elements to {1000, 999, 998, …. 1}
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________

Write a program that reads in a group of test scores (positive integers from 1 to 100) from the keyboard and then
calculate and output the average score as well as the highest and lowest score. There will be a maximum of 100
scores.
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________

Sorting Elements of an Array:

Sorting array means placing the elements of an array in some particular order. You can sort the arrays either in
ascending order or descending order. Different types of sorting algorithm are:
 Insertion sort
 Bubble Sort
 Merge sort
 Selection sort
We will use only bubble sort and selection sort here.
 Bubble Sort:
The bubble sort is a simple algorithm used to arrange data in either ascending (lowest to highest) or descending
(highest to lowest) order. To see how this sort works, let us arrange the array below in ascending order.
9 2 0 11 5
Element 0 Element 1 Element 2 Element 3 Element 4

The bubble sort begins by comparing the first two array elements. If Element 0 > Element 1, which is true in this
case, then these two pieces of data are exchanged. The array is now the following:
2 9 0 11 5
Element 0 Element 1 Element 2 Element 3 Element 4

Next elements 1 and 2 are compared. Since Element 1 > Element 2, another exchange occurs:
2 0 9 11 5
Element 0 Element 1 Element 2 Element 3 Element 4

2
Programming Fundamentals Lab Lab 02
Now elements 2 and 3 are compared. Since 9 < 11, there is no exchange at this step. Next elements 3 and 4 are
compared and exchanged:
2 0 9 5 11
Element 0 Element 1 Element 2 Element 3 Element 4
At this point we are at the end of the array. Note that the largest value is now inthe last position of the array. Now
we go back to the beginning of the array and repeat the entire process over again. Elements 0 and 1 are compared.
Since 2 > 0, an exchange occurs:

0 2 9 5 11
Element 0 Element 1 Element 2 Element 3 Element 4

Next elements 1 and 2 are compared. Since 2 < 9, no swap occurs. However, when we compare elements 2 and 3 we
find that 9 > 5 and so they are exchanged. Since Element 4 contains the largest value (from the previous pass), we
do not need to make any more comparisons in this pass. The final result is:
0 2 5 9 11
Element 0 Element 1 Element 2 Element 3 Element 4

The data is now arranged in ascending order and the algorithm terminates. Note that the larger values seem to rise
“like bubbles” to the larger positions of the array as the sort progresses.

 Selection Sort:
A generally more efficient algorithm for large arrays is the selection sort. As before, let us assume that we want to
arrange numerical data in ascending order. The idea of the selection sort algorithm is to first locate the smallest
value in the array and move that value to the beginning of the array (i.e., position 0). Then the next smallest element
is located and put in the second position (i.e., position 1). This process continues until all the data is ordered. An
advantage of the selection sort is that for n data elements at most n-1 moves are required. The disadvantage is that
n(n-1)/2 comparisons are always required. To see how this sort works, let us consider the array we arranged using
the bubble sort:
9 2 0 11 5
Element 0 Element 1 Element 2 Element 3 Element 4

First the smallest value is located. It is 0, so the contents of Element 0 and Element 2 are swapped:
0 2 9 11 5
Element 0 Element 1 Element 2 Element 3 Element 4

Next we look for the second smallest value. The important point to note here is that we do not need to check
Element 0 again since we know it already contains the smallest data value. So the sort starts looking at Element 1.
We see that the second smallest value is 2, which is already in Element 1. Starting at Element 2 we see that 5 is the
smallest of the remaining values. Thus the contents of Element 2 and Element 4 are swapped:
0 2 5 11 9
Element 0 Element 1 Element 2 Element 3 Element 4

Finally, the contents of Element 3 and Element 4 are compared. Since 11 > 9, thecontents are swapped leaving the
array ordered as desired:
0 2 5 9 11
Element 0 Element 1 Element 2 Element 3 Element 4

3
Programming Fundamentals Lab Lab 02

Lab Exercise:
Develop a C++ program to sort the elements of any array using bubble sort algorithm.

_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________

Develop a C++ program to sort the elements of any array using insertion sort algorithm.
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________
_____________________________________________________________________________________________