Transcript Powerpoint format

Lab Session-XI CSIT121
Spring 2002





Sorting the arrays (array application)
Bubble Sort
Structures and Their Usage
Passing Struct Variables to Functions
Examples and Exercises
1
Sorting Arrays



Arrays may contain numbers that need to be
sorted in ascending or descending order
Sorting is a special technique and many
algorithms are proposed for sorting
Look at
http://www.cs.ubc.ca/spider/harrison/Java/s
orting-demo.html for a demo
2
Bubble Sort





Sorting of arrays can be done with many
techniques
Look at the example of SELECTION SORT
SELECTION SORT chooses the smallest (or
largest) value in the array and moves it to one end.
By repeatedly picking up smallest (or largest)
value out of the remaining values, selection sort
decreases the search space one at a time
Another sorting technique is called bubble sort
3
Bubble Sort

In bubble sort, the smallest value pops up. That is why it is
called bubble sort.
 Bubble Sort Algorithm is quite simple
 It performs as many passes as the number of elements in
the array minus one
 On each pass, adjacent elements are compared and
swapped if the current value is found greater than next.
 Due to it simplicity, bubble sort is also inefficient because
it makes too many comparisons
4
Bubble Sort

Let us develop the bubble sort algorithm as
nested for loops:

for (outer=0; outer<SIZE-1; outer++)
for (inner=0; inner<SIZE-1; inner++)
if (array[inner] > array[inner+1])
swap values (array[inner]<==array[inner+1]
and array[inner+1]<==array[inner])
Please write a swap function separately





5
Structures and Their Usage



Arrays can only store data items of same
data type under a common name
If we want to store student’s name and SS#
together under a common name, it is not
possible with arrays
We need to group together data items that
are logically related to each other but these
are of different data types
6
Structures and Their Usage




Examples of logical groups
Passenger Name, Flight Number, Seat
Number and Status
Book Name, Author, Year published,
Catalogue Number, Status
Student Name, SS#, Current courses
7
Structures and Their Usage

C++ provides struct data type
 Using struct data type, we can collect many data
items with different data types together under a
same name
 For example, if we wish to implement flight
reservation system, we will need something
similar to the following:
8
Structures and Their Usage








Struct flight
{
int SNo;
char name[40];
char aisle;
int seat;
char status;
}
9
Structures and Their Usage




We have defined a data type by the name
flight.
We can now declare variables of this data
type
Example: flight AA474;
we can use AA474 in our program now
10
Structures and Their Usage





The data items grouped together under
flight data type are called members of the
structure.
Accessing members is done via dot notation
For Example:
AA474.seat=24; AA474.aisle=‘F’;
AA474.status=‘K’; (K means OK)
11
Structures and Their Usage









The members can be used just like any
other variables are used
Example:
switch(AA474.status)
{
case ‘K’:cout<<“Confirmed\n”; break;
case ‘W’:cout<<“Waiting\n”;break;
case ‘C’:cout<<“Canceled”; break;
default: cout<<“Error in flight information\n”; break;
}
12
Passing Struct Variables to
Functions

Struct variables can be assigned as below

flight AA475; AA475=AA474;

We can pass struct variables as arguments to
functions. See example prototypes
By Value void print_info(flight);
By Reference void change_info(flight&);
Better pass by reference and add const if
you wish to protect it



13
Lab Exercise 11-1



Let us sort an array using the bubble sort
technique.
As the name suggests, the array will be
sorted in ascending order with smallest
value popping up to the beginning of the
array.
int schedule[10]={474, 282, 120, 765, 780,
23, 232, 75, 24, 812};
14
Lab Exercise 11-2 (DEMO)

Define a struct time that can hold hours,
minutes and seconds as well as a char flag
for am or PM.

struct time
{ int hours;
int minutes;
int seconds;
char ampm;
}
time now;
now.ampm=‘a’;







15
Lab Exercise 11-2 (DEMO)






Develop a program to
print standard time with AM/PM notation
print military time without AM/PM notation
For example, if we have stored 14 hours, 20
minutes and 30 seconds
Standard time prints 02:20:30 PM
Military time prints14:20:30
16