Institut Universitaire et Stratégique de l’Estuaire

Estuary Academic and Strategic Institute (IUEs/Insam)

Sous la tutelleacadémique des Universités de Dschang et de Buéa.

COURSE CODE: SWE233

COURSE TITLE: ADVANCED DATA STRUCTURE

COURSE INSTRUCTOR: Mr ATANGANA OTELE CHARLIE GAEL

General Objective
By the end of this course, the learner should be able to write valid algorithm using technique offring
functions and procedures. A correct implementation of sorting and searching techniques in C/C++
programming is addressed.
Study Units
The study Units of this course are:
Module 1 ALGORITHM ADVANCED CONCEPTS
Unit1 Introduction to data structure
Unit2 Functions and procedures
Module 2 Algorithms design techniques
Unit3 Sorting
Unit4 Searching
Unit5Practical on C/C++ programming

1
Unit1 Introduction to data structures
At the end of this unit, the learner should be able to:
 Define algorithm and write its minimal structure;
 Define data structure, data type and ADTs.
 State the characteristics of a valid algorithm.
Definition
An algorithm is a set of steps of operations to solve a problem performing calculation, data
processing, and automated reasoning tasks. An algorithm is an efficient method that can be
expressed within finite amount of time and space.
An algorithm is the best way to represent the solution of a particular problem in a very simple and
efficient way. If we have an algorithm for a specific problem, then we can implement it in any
programming language, meaning that the algorithm is independent from any programming
languages.
Algorithm design
The important aspects of algorithm design include creating an efficient algorithm to solve a problem
in an efficient way using minimum time and space.
To solve a problem, different approaches can be followed. Some of them can be efficient with
respect to time consumption, whereas other approaches may be memory efficient. However, one has
to keep in mind that both time consumption and memory usage cannot be optimized simultaneously.
If we require an algorithm to run in lesser time, we have to invest in more memory and if we require
an algorithm to run with lesser memory, we need to have more time.
Problem development steps
The following steps are involved in solving computational problems.
 Problem definition
 Development of a model
 Specification of an Algorithm
 Designing an Algorithm
 Checking the correctness of an Algorithm
 Analysis of an Algorithm
 Implementation of an Algorithm
 Program testing
 Documentation
Characteristics of algorithms
The main characteristics of algorithms are as follows :
 Algorithms must have a unique name
 Algorithms should have explicitly defined set of inputs and outputs
 Algorithms are well-ordered with unambiguous operations
 Algorithms halt in a finite amount of time. Algorithms should not run for infinity, i.e., an
algorithm must end at some point

2
Pseudocode
Pseudocode gives a high-level description of an algorithm without the ambiguity associated with
plain text but also without the need to know the syntax of a particular programming language.
The running time can be estimated in a more general manner by using Pseudocode to represent the
algorithm as a set of fundamental operations which can then be counted.
Difference between algorithm and pseudocode
An algorithm is a formal definition with some specific characteristics that describes a process,
which could be executed by a Turing-complete computer machine to perform a specific task.
Generally, the word "algorithm" can be used to describe any high level task in computer science.
On the other hand, pseudocode is an informal and (often rudimentary) human readable description
of an algorithm leaving many granular details of it. Writing a pseudocode has no restriction of styles
and its only objective is to describe the high level steps of algorithm in a much realistic manner in
natural language.
Structure of an algorithm
A valid algorithm is made up of three parts:
 The head part starting with the word algorithm followed by the algorithm name
 The declaration block starting with the key word variable
 The body block enclosed withn the key words Begin and End
Algorithm algorithmName
variable variableName1, variableName1, … , variableNameN: DataType;
Begin
instructions block;
End
Example: Write an algorithm to compute the sum of two integers input by the user and display the
result
Algorithm algorithmName
variable number1,number2,result: integer;
Begin
write(‘please enter the first name’);
read(number1);
write(‘please enter the second name’);
read(number2);
result:= number1+ number2;
write(‘the result is:’,result);
End

3
Data types
A data type in a programming language is a set of data with predefined values. Examples of data
types are: integer, floating point, unit number, character, string, etc. Computer memory is all filled
with zeros and ones. If we have a problem and we want to code it, it’s very difficult to provide the
solution in terms of zeros and ones. To help users, programming languages and compilers provide
us with data types. For example, integer takes 2 bytes (actual value depends on compiler), float
takes 4 bytes, etc. This says that in memory we are combining 2 bytes (16 bits) and calling it an
integer. Similarly, combining 4 bytes (32 bits) and calling it a float. A data type reduces the coding
effort. At the top level, there are two types of data types:
 System-defined data types (also called Primitive data types)
 User-defined data types
System defined data types (primitive data types)
Data types that are defined by system are called primitive data types. The primitive data types
provided by many programming languages are: int, float, char, double, bool, etc. The number of bits
allocated for each primitive data type depends on the programming languages, the compiler and the
operating system. For the same primitive data type, different languages may use different sizes.
Depending on the size of the data types, the total available values (domain) will also change.
User defined data types
If the system-defined data types are not enough, then most programming languages allow the users
to define their own data types, called user – defined data types. Good examples of user defined data
types are: structures in C/C + + and classes in Java.
Data structures
Based on the discussion above, once we have data in variables, we need some mechanism for
manipulating that data to solve problems. Data structure is a particular way of storing and
organizing data in a computer so that it can be used efficiently. A data structure is a special format
for organizing and storing data. General data structure types include arrays, files, linked lists,
stacks, queues, trees, graphs and so on.
Depending on the organization of the elements, data structures are classified into two types:
 Linear data structures: Elements are accessed in a sequential order but it is not compulsory
to store all elements sequentially. Examples: Linked Lists, Stacks and Queues.
 Non – linear data structures: Elements of this data structure are stored/accessed in a non-
linear order. Examples: Trees and graphs.
Abstract Data Types (ADTs)
Before defining abstract data types, let us consider the different view of system-defined data types.
We all know that, by default, all primitive data types (int, float, etc.) support basic operations such
as addition and subtraction. The system provides the implementations for the primitive data types.
For user-defined data types we also need to define operations. The implementation for these
operations can be done when we want to actually use them. That means, in general, user defined
data types are defined along with their operations.
To simplify the process of solving problems, we combine the data structures with their operations
and we call this Abstract Data Types (ADTs). An ADT consists of two parts:
 Declaration of data
 Declaration of operations
Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues, Binary Trees,
Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, and many others.
Algorithm Flowchart
A flowchart is a blueprint that pictorially represents the algorithm and its steps. The steps of a
flowchart do not have a specific size and shape rather it is designed in different shapes and sizes.

4
Benefits of Flowchart
Simplify the Logic: As it provides the pictorial representation of the steps; therefore, it simplifies
the logic and subsequent steps.
Makes Communication Better: Because of having easily understandable pictorial logic and steps,
it is a better and simple way of representation.
Effective Analysis: Once the flow-chart is prepared, it becomes very simple to analyze the problem
in an effective way.
Useful in Coding: The flow-chart also helps in coding process efficiently, as it gives directions on
what to do, when to do, and where to do. It makes the work easier.
Proper Testing: Further, flowchart also helps in finding the error (if any) in program
Applicable Documentation: Last but not the least, a flowchart also helps in preparing the proper
document (once the codes are written).
Advantages of Flowchart in:
Following are the various advantages of flowchart:
 Communication: A flowchart is a better way of communicating the logic of a program.
 Synthesis: Flowchart is used as working models in designing new programs and software
systems.
 Efficient Coding: Flowcharts act as a guide for a programmer in writing the actual code in a
high-level language.
 Proper Debugging: Flowcharts help in the debugging process.
 Effective Analysis: Effective analysis of logical programs can be easily done with the help
of a related flowchart.
 Proper Documentation: Flowchart provides better and proper documentation. It consists of
various activities such as collecting, organizing, storing, and maintaining all related program
records.
 Testing: A flowchart helps in the testing process.
 Efficient program maintenance: The maintenance of the program becomes easy with the
help of a flowchart.

Disadvantages of Flowchart in:

Following are the various disadvantages of flowchart:
 Time-consuming: Designing a flowchart is a very time-consuming process.
 Complex: It isn't easy to draw a flowchart for large and complex programs.
 There is no standard in the flowchart; there is no standard to determine the quantity of
detail.
 Difficult to modify: It is very difficult to modify the existing flowchart.

Flow-Chart Symbols
The following table illustrates the symbols along with their names (used in a flow-chart):

5
Example of flowchart:
The various examples of the flowchart are given below:

Example:
Design a flowchart for adding two numbers entered by the user.

6
Exercises1
1. Define algorithm and state the characteristics of a good algorithm.
2. Write the minimal structure of an algorithm.
3. State at least three basic instructions of an algorithm
4. State some basic operators used in algorithmic.
5. Define data structures, data type, ADTs
6. State some examples of data structures
a. Evaluate the expression (11<3*2+5)OR(6*2=4*3)AND NOT(2+2=4)
b. Evaluate the expression (11<=3*2+5)OR(6*2=4*3)AND NOT(2+2=4)
c. State four conditional statements and propose their syntax
d. write an algorithm that reads the length and width of an arbitrary number N of fields and
calculate their area and perimeter of each. The algorithm should print the length, width, area,
perimeter of each field as well as the total area and total perimeter of all the fields.
e. write an algorithm to compute the area A of N circles with radius R and print the total area.
The value for pie should be declared as a constant.
Exercises2
1) Design a flowchart for calculating the profit and loss according to the value entered by the
user.
2) Draw a flowchart to calculate the average of two numbers.
3) Design a flowchart for the multiplication of three numbers entered by the user.
4) Design a flowchart for calculating the area of a rectangle.

7
5) Design a flowchart for checking whether the number is positive or negative according to the
number entered by the user.

Unit2 Functions and procedures

At the end of this unit, the learner should be able to:
 define a function prototype
 write correctly the syntax of a function
 differentiate between function and procedure
 implement function using C++ languages
 manipulate records and files
 appply the recursivity property

Introduction
In programming terms, a function is a block of statements that performs a specific task. Functions
accept data, process it, and return a result. Functions are written primarily to support the concept of
reusability. Once a function is written, it can be called easily, without having to write the same code
again and again.
Different programming languages use different syntax to write a function.

Prerequisites to Writing a Function

Before writing a function, a programmer must know the following points:
 Purpose of function should be known to the programmer.
 Algorithm of the function should be known to the programmer.
 Functions data variables & their goal should be known to the programmer.
 Function's data should be known to the programmer that is called by the user.

Flow Control of a Function

When a function is "called", the program "transfers" the control to execute the function and its
"flow of control" is as below:
 The program reaches to the statement containing a "function call".
 The first line inside the function is executed.
 All the statements inside the function are executed from top to bottom.
 When the function is executed successfully, the control goes back to the statement where it
started from.
 Any data computed and returned by the function is used in place of the function in the
original line of code.

Syntax of a Function
The general syntax of a function looks as follows:

8
returnType functionName(type1 argument1, type2 argument2, . . . ) {
// function body
}

Defining a Function in C++

Let’s take an example to understand how a function can be defined in C++ which is an object-
oriented programming language. The following code has a function that adds two numbers and
provides its result as the output.
#include <stdio.h>

int addNum(int a, int b); // function prototype

int main() {
int sum;
sum = addNum(5,6); // function call
printf("sum = %d",sum);
return 0;
}
int addNum (int a,int b) { // function definition
int result;
result = a + b;
return result; // return statement
}

Function Prototype
A function prototype is a declaration of the function that includes return-type, function-name &
arguments-list. It is similar to function definition without function-body.
For Example: Some programming languages supports function prototyping & some are not.
In C++, we can make function prototype of function ‘sum’ like this:
int sum(int a, int b)

What is the use of function prototype?

The function prototype is used by the compiler when the function is called. Compiler uses it to
ensure correct return-type, proper arguments list are passed-in, & their return-type is correct.

Function Signature
A function signature is similar to function prototype in which number of parameters, datatype of
parameters & order of appearance should be in similar order. For Example:
void Sum(int a, int b, int c); // function 1
void Sum(float a, float b, float c); // function 2
void Sum(float a, float b, float c); // function 3

9
Function1 and Function2 have different signatures. Function2 and Function3 have same signatures.
Note: Function overloading and Function overriding which we will discuss in the subsequent
sections are based on the concept of function signatures.
 Function overloading is possible when a class has multiple functions with the same name but
different signatures.
 Function overriding is possible when a derived class function has the same name and
signature as its base class.

Function Types
Functions are of two types:
 Predefined functions
 User-defined functions

Predefined Functions
These are the functions that are built into Language to perform operations & are stored in the
Standard Function Library.
For Example − ‘Strcat’ in C++ is used to append the two strings, ‘strlen’ in C++ is used to calculate
the string length.

Program to print string length in C++

The following program shows how you can print the length of a string using C++:
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int main() {
char str[20] = "Hello World";
int len;
len = strlen(str);
cout<<"String length is: "<<len;
return 0;
}

User-defined Functions
User-defined functions are defined by the user to perform specific tasks. There are four different
patterns to define a function:
 Functions with no argument and no return value
 Functions with no argument but a return value
 Functions with argument but no return value
 Functions with argument and a return value

10
Functions with no argument and no return value
The following program shows how to define a function with no argument and no return value in C+
+:
#include <iostream>
using namespace std;

void function1() {
cout <<"Hello World";
}
int main() {
function1();
return 0;
}

Functions with no argument but a return value

The following program shows how to define a function with no argument but a return value in C++:
#include <iostream>
using namespace std;
string function1() {
return("Hello World");
}

int main() {
cout<<function1();
return 0;
}

Functions with argument but no return value

The following program shows how to define a function with argument but no return value in C++:
#include <iostream>
using namespace std;
void function1(int x, int y) {
int c;
c = x+y;
cout<<"Sum is: "<<c;
}

int main() {
function1(4,5);
return 0;
}

Functions with argument and a return value

The following program shows how to define a function in C++ with no argument but a return value

11
#include <iostream>
using namespace std;
int function1(int x, int y) {
int c;
c = x + y;
return c;
}

int main() {
int res;
res = function1(4,5);
cout<<"Sum is: "<<res;
return 0;
}

Call By Value
After defining a function, we need pass arguments into it to get desired output. Most programming
languages support call by value and call by reference methods for passing arguments into
functions.
In Call by Value method, the original value cannot be changed. When we pass an argument to a
function, it is stored locally by the function parameter in stack memory. Hence, the values are
changed inside the function only and it will not have an effect outside the function.

Call by Value in C++

The following program shows how Call by Value works in C++:
#include <iostream>
using namespace std;

void swap(int a, int b) {

int temp;
temp = a;
a = b;
b = temp;
cout<<"\n"<<"value of a inside the function: "<<a;
cout<<"\n"<<"value of b inside the function: "<<b;
}
int main() {
int a = 50, b = 70;
cout<<"value of a before sending to function: "<<a;
cout<<"\n"<<"value of b before sending to function: "<<b;
swap(a, b); // passing value to function
cout<<"\n"<<"value of a after sending to function: "<<a;
cout<<"\n"<<"value of b after sending to function: "<<b;
return 0;
}

12
Call By Reference
In Call by Reference, the original value is changed because we pass reference address of
arguments. The actual and formal arguments share the same address space, so any change of value
inside the function is reflected inside as well as outside the function.

Call by Reference in C++

The following program shows how Call by Value works in C++:
#include <iostream>
using namespace std;

void swap(int *a, int *b) {

int temp;
temp = *a;
*a = *b;
*b = temp;
cout<<"\n"<<"value of a inside the function: "<<*a;
cout<<"\n"<<"value of b inside the function: "<<*b;
}
int main() {
int a = 50, b = 75;
cout<<"\n"<<"value of a before sending to function: "<<a;
cout<<"\n"<<"value of b before sending to function: "<<b;
swap(&a, &b); // passing value to function
cout<<"\n"<<"value of a after sending to function: "<<a;
cout<<"\n"<<"value of b after sending to function: "<<b;
return 0;
}

Function Overloading
When we have multiple functions with the same name but different parameters, then they are said to
be overloaded. This technique is used to enhance the readability of the program.
There are two ways to overload a function, i.e.:
 Having different number of arguments
 Having different argument types
Function overloading is normally done when we have to perform one single operation with different
number or types of arguments.

Function Overloading in C++

The following example shows how function overloading is done in C++, which is an object oriented
programming langage:
#include <iostream>
using namespace std;
void addnum(int,int);

13
void addnum(int,int,int);

int main() {
addnum (5,5);
addnum (5,2,8);
return 0;
}

void addnum (int x, int y) {

cout<<"Integer number: "<<x+y<<endl;
}

void addnum (int x, int y, int z) {

cout<<"Float number: "<<x+y+z<<endl;
}

Function Overriding
When the base class and derived class have member functions with exactly the same name, same
return-type, and same arguments list, then it is said to be function overriding.

Function Overriding using C++

The following example shows how function overriding is done in C++, which is an objectoriented
programming langage:
#include <iostream>
using namespace std;

class A {
public:
void display() {
cout<<"Base class";
}
};

class B:public A {
public:
void display() {
cout<<"Derived Class";
}
};

int main() {
B obj;
obj.display();
return 0;
}

14
Recursion
A function that calls itself is known as a recursive function and this technique is known as
recursion. A recursion instruction continues until another instruction prevents it.

Recursion in C++
The following example shows how recursion works in C++, which is an object-oriented
programming language
#include <stdio.h>
long int fact(int n);

int main() {
int n;
printf("Enter a positive integer: ");
scanf("%d", &n);
printf("Factorial of %d = %ld", n, fact(n));
return 0;
}
long int fact(int n) {
if (n >= 1)
return n*fact(n-1);
else
return 1;
}

Polymorphism
Polymorphism, in terms of programming, means reusing a single code multiple times. More
specifically, it is the ability of a program to process objects differently depending on their data type
or class.
Polymorphism is of two types −
 Compile-time Polymorphism − This type of polymorphism can be achieved using method
overloading.
 Run-time Polymorphism − This type of polymorphism can be achieved using method
overriding and virtual functions.

Advantages of Polymorphism
Polymorphism offers the following advantages −
 It helps the programmer to reuse the codes, i.e., classes once written, tested and
implemented can be reused as required. Saves a lot of time.
 Single variable can be used to store multiple data types.
 Easy to debug the codes.

15
Polymorphic Data Types
Polymorphic data-types can be implemented using generic pointers that store a byte address only,
without the type of data stored at that memory address. For example,
function1(void *p, void *q)
where p and q are generic pointers which can hold int, float (or any other) value as an argument.

Polymorphic Function in C++

The following program shows how to use polymorphic functions in C++, which is an object
oriented programming language.
#include <iostream>
Using namespace std:

class A {
public:
void show() {
cout << "A class method is called/n";
}
};

class B:public A {
public:
void show() {
cout << "B class method is called/n";
}
};

int main() {
A x; // Base class object
B y; // Derived class object
x.show(); // A class method is called
y.show(); // B class method is called
return 0;
}

Strings
A string is a group of characters including spaces. We can say it is a one-dimensional array of
characters which is terminated by a NULL character (‘\0’). A string can also be regarded as a
predefined class which is supported by most of the programming languages such as C, C++, Java,
PHP, Erlang, Haskell, Lisp, etc.
The following image shows how the string "Tutorial" will look in the memory.

16
Create a String in C++
The following program is an example that shows how to create a string in C++, which is an object-
oriented programming language.
#include <iostream>
using namespace std;

int main () {
char greeting[20] = {'H', 'o', 'l', 'i', 'd', 'a', 'y', '\0'};
cout << "Today is: ";
cout << greeting << endl;
return 0;
}

String Operations in C++

Different programming languages support different methods on strings. The following table shows a
few predefined string methods supported by C++.

17
The following program shows how the above methods can be used in C++
#include <iostream>
#include <cstring>
using namespace std;

int main () {
char str1[20] = "Today is ";
char str2[20] = "Monday";
char str3[20];
int len ;
strcpy( str3, str1); // copy str1 into str3
cout << "strcpy( str3, str1) : " << str3 << endl;

strcat( str1, str2); // concatenates str1 and str2

cout << "strcat( str1, str2): " << str1 << endl;

len = strlen(str1); // String length after concatenation

cout << "strlen(str1) : " << len << endl;
return 0;
}

18
Records
A record is a data structure for storing a fixed number of elements. It is similar to a structure in C
language. At the time of compilation, its expressions are translated to tuple expressions.

How to create a record?

The keyword ‘record’ is used to create records specified with record name and its fields. Its syntax
is as follows
record(recodname, {field1, field2, . . fieldn})

The syntax to insert values into the record is:

#recordname {fieldName1 = value1, fieldName2 = value2 .. fieldNamen = valuen}

Program to create records using C++

The following example shows how to create records using C++, which is an object-oriented
programming language
#include<iostream>
#include<string>
using namespace std;

class student {
public:
string sname;
int sid;
};

int main() {
student S;
S.sname = "Sachin";
S.sid = 5;
return 0;
}

Program to access record values using C++

The following program shows how to access record values using C++
#include<iostream>
#include<string>
using namespace std;

class student {
public:
string sname;
int sid;
};

19
int main() {
student S;
S.sname = "Sachin";
S.sid = 5;
cout<<S.sid<<"\n"<<S.sname;
return 0;
}

Program to update record values using C++

The following program shows how to update record values using C++
#include<iostream>
#include<string>
using namespace std;

class student {
public:
string sname;
int sid;
};

int main() {
student S;
S.sname = "Jonny";
S.sid = 5;
cout<<S.sname<<"\n"<<S.sid;
cout<<"\n"<< "value after updating"<<"\n";
S.sid = 10;
cout<<S.sname<<"\n"<<S.sid;
return 0;
}

File I/O Operations

We need files to store the output of a program when the program terminates. Using files, we can
access related information using various commands in different languages.
Here is a list of some operations that can be carried out on a file:
 Creating a new file
 Opening an existing file
 Reading file contents
 Searching data on a file
 Writing into a new file
 Updating contents to an existing file
 Deleting a file
 Closing a file

20
Writing into a File
To write contents into a file, we will first need to open the required file. If the specified file does not
exist, then a new file will be created.
Let’s see how to write contents into a file using C++.

Example
#include <iostream>
#include <fstream>
using namespace std;

int main () {
ofstream myfile;
myfile.open ("Tempfile.txt", ios::out);
myfile << "Writing Contents to file.\n";
cout << "Data inserted into file";
myfile.close();
return 0;
}

Note:
 fstream is the stream class used to control file read/write operations.
 ofstream is the stream class used to write contents into file.

Reading from a File

To read from a file, first we have to open the specified file in reading mode. If the file doesn’t
exist, then its respective method returns NULL.
The following program shows how to read the contents of a file in C++
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main () {
string readfile;
ifstream myfile ("Tempfile.txt",ios::in);

if (myfile.is_open()) {
while ( getline (myfile,readfile) ) {
cout << readfile << '\n';
}
myfile.close();
} else
cout << "file doesn't exist";
return 0;
}

21
Note − In this program, we opened a text file in read mode using “ios::in” and then print its
contents on the screen. We have used while loop to read the file contents line by line by using
“getline” method.

Delete an Existing File

We can delete an existing file using file operations. The following program shows how to delete an
existing file using C++
#include <stdio.h>

int main () {
if(remove( "Tempfile.txt" ) != 0 )
perror( "File doesn’t exist, can’t delete" );
else
puts( "file deleted successfully " );
return 0;
}

Determining the Size of a File

The following program shows how you can determine the size of a file using C++. Here, the
function fseek sets the position indicator associated with the stream to a new position, whereas ftell
returns the current position in the stream.
#include <stdio.h>

int main () {
FILE * checkfile;
long size;
checkfile = fopen ("Tempfile.txt","rb");

if (checkfile == NULL)
perror ("file can’t open");
else {
fseek (checkfile, 0, SEEK_END); // non-portable
size = ftell (checkfile);
fclose (checkfile);
printf ("Size of Tempfile.txt: %ld bytes.\n",size);
}
return 0;
}

Output − If the file “Tempfile.txt” exists, then it will show its size in bytes.
Assignment
Exercise1
1) Define a function and write the syntax of a function
2) Define a procedure and write its syntax

22
 3) defferentiate between call by value and call by reference
4) Write a function exchanging two variables. What problem happens ? Propose an appropriate
solution.
5) Write a function to insert and display values of a two dimensional array. An implementation
can be done in C/C++.
6) Write a c++ program to print the maximum value of an array passed in a function as
parameters.
7) Write a c++ program to print fibonacci series without using recursion and using recursion.
Exercise2
1. Write a program in C++ programinng that will read a file containing students records and
determine if the student with the following description is on the file.
Identifier Student1 Student2 Student3
fields
Name Ali Rose Peter
Age 20 18 21
Sex Male Female Male
Year of study 2 1 3

Unit3 Sorting
At the end of this unit the learner should be able to:
 implement the sorting algorithms including insertion, selection, bubbles.
Sorting is an algorithm that arranges the elements of a list in a certain order [either ascending or
descending]. The output is a permutation or reordering of the input. Sorting refers to arranging data
in a particular format. Sorting algorithm specifies the way to arrange data in a particular order.
The importance of sorting lies in the fact that data searching can be optimized to a very high level,
if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats.
Following are some of the examples of sorting in real-life scenarios:
 Telephone Directory − The telephone directory stores the telephone numbers of people
sorted by their names, so that the names can be searched easily.
 Dictionary − The dictionary stores words in an alphabetical order so that searching of any
word becomes easy.

In-place Sorting and Not-in-place Sorting

Sorting algorithms may require some extra space for comparison and temporary storage of few data
elements. These algorithms do not require any extra space and sorting is said to happen in-place, or
for example, within the array itself. This is called in-place sorting. Bubble sort is an example of in-
place sorting.

23
However, in some sorting algorithms, the program requires space which is more than or equal to the
elements being sorted. Sorting which uses equal or more space is called not-in-place sorting.
Merge-sort is an example of not-in-place sorting.

Stable and Not Stable Sorting

If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in
which they appear, it is called stable sorting.

If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which
they appear, it is called unstable sorting.

Stability of an algorithm matters when we wish to maintain the sequence of original elements, like
in a tuple for example.

Adaptive and Non-Adaptive Sorting Algorithm

A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list
that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive
algorithms will take this into account and will try not to re-order them.
A non-adaptive algorithm is one which does not take into account the elements which are already
sorted. They try to force every single element to be re-ordered to confirm their sortedness.

Important Terms
Some terms are generally coined while discussing sorting techniques, here is a brief introduction to
them −

24
Increasing Order
A sequence of values is said to be in increasing order, if the successive element is greater than the
previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater
than the previous element.

Decreasing Order
A sequence of values is said to be in decreasing order, if the successive element is less than the
current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than
the previous element.

Non-Increasing Order
A sequence of values is said to be in non-increasing order, if the successive element is less than or
equal to its previous element in the sequence. This order occurs when the sequence contains
duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is
less than or equal to (in case of 3) but not greater than any previous element.

Non-Decreasing Order
A sequence of values is said to be in non-decreasing order, if the successive element is greater
than or equal to its previous element in the sequence. This order occurs when the sequence contains
duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is
greater than or equal to (in case of 3) but not less than the previous one.

Bubble Sort Algorithm

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in
which each pair of adjacent elements is compared and the elements are swapped if they are not in
order. This algorithm is not suitable for large data sets as its average and worst case complexity are
of Ο(n2) where n is the number of items.

How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n 2) time so we're keeping it short
and precise.

Bubble sort starts with very

first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33
with 27.

25
We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration, the
array should look like this

To be precise, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this

Notice that after each iteration, at least one value moves at the end.

26
And when there's no swap required, bubble sorts learns that an array is completely sorted.

Now we should look into some practical aspects of bubble sort.

Algorithm
We assume list is an array of n elements. We further assume that swap function swaps the values of
the given array elements.
begin BubbleSort(list)

for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for

return list

end BubbleSort

Pseudocode
We observe in algorithm that Bubble Sort compares each pair of array element unless the whole
array is completely sorted in an ascending order. This may cause a few complexity issues like what
if the array needs no more swapping as all the elements are already ascending.To ease-out the issue,
we use one flag variable swapped which will help us see if any swap has happened or not. If no
swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the
loop.Pseudocode of BubbleSort algorithm can be written as follows
procedure bubbleSort( list : array of items )

loop = list.count;

for i = 0 to loop-1 do:

swapped = false

for j = 0 to loop-1 do:

/* compare the adjacent elements */

if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true

27
 end if

end for

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped) then

break
end if

end for

end procedure return list

Insertion Sort
This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is
always sorted. For example, the lower part of an array is maintained to be sorted. An element which
is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted
there. Hence the name, insertion sort.
The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list
(in the same array). This algorithm is not suitable for large data sets as its average and worst case
complexity are of Ο(n2), where n is the number of items.

How Insertion Sort Works?

We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.
Insertion sort moves ahead and compares 33 with 27.
And finds that 33 is not in the correct position.
It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the
sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains
sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.
These values are not in a sorted order.
So we swap them.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.

28
This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see
some programming aspects of insertion sort.
Algorithm
Now we have a bigger picture of how this sorting technique works, so we can derive simple steps
by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocode
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert

for i = 1 to length(A) inclusive do:

/* select value to be inserted */

valueToInsert = A[i]
holePosition = i

/*locate hole position for the element to be inserted */

while holePosition > 0 and A[holePosition-1] > valueToInsert do:

A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while

/* insert the number at hole position */

A[holePosition] = valueToInsert

end for

end procedure

Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based
algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted
part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

29
The smallest element is selected from the unsorted array and swapped with the leftmost element,
and that element becomes a part of the sorted array. This process continues moving unsorted array
boundary by one element to the right.
This algorithm is not suitable for large data sets as its average and worst case complexities are of
Ο(n2), where n is the number of items.

How Selection Sort Works?

Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first position
where 14 is stored presently, we search the whole list and find that 10 is the lowest value.
So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list,
appears in the first position of the sorted list.
For the second position, where 33 is residing, we start scanning the rest of the list in a linear
manner.
We find that 14 is the second lowest value in the list and it should appear at the second place. We
swap these values.
After two iterations, two least values are positioned at the beginning in a sorted manner.
The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process

Algorithm
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Pseudocode
procedure selection sort
list : array of items
n : size of list

for i = 1 to n - 1
/* set current element as minimum*/
min = i

/* check the element to be minimum */

for j = i+1 to n

30
 if list[j] < list[min] then
min = j;
end if
end for

/* swap the minimum element with the current element*/

if indexMin != i then
swap list[min] and list[i]
end if
end for

end procedure

Assignment

1) Write a c program to sort the following list {1,8,4,6,0,3,5,2,7,9} using bubble sort algorithm

2) Write a C program to sort the above list using insertion sort algorithmi

3) write a C program to sort the above list using selection sort.

Unit4 Searching
At the end of this unit, the learner should be able to :
 write some searching algorithms
 implement some searching algorithms in c/c++ language
 use searching techniques in order to solve real live situations
In computer science, searching is the process of finding an item with specified properties from a
collection of items. The items may be stored as records in a database, simple data elements in
arrays, text in files, nodes in trees, vertices and edges in graphs, or they may be elements of other
search spaces.
Why do we need Searching?
Searching is one of the core computer science algorithms. We know that today’s computers store
a lot of information. To retrieve this information proficiently we need very efficient searching
algorithms. There are certain ways of organizing the data that improves the searching process.
That means, if we keep the data in proper order, it is easy to search the required element. Sorting
is one of the techniques for making the elements ordered. In this chapter we will see different
searching algorithms.
Types of Searching
Following are some type of search algorithms
Unordered Linear Search
Sorted/Ordered Linear Search
Binary Search
Interpolation search
Binary Search Trees
Symbol Tables and Hashing
String Searching Algorithms: Tries, Ternary Search and Suffix Trees

31
Unordered Linear Search
Let us assume we are given an array where the order of the elements is not known. That means the
elements of the array are not sorted. In this case, to search for an element we have to scan the
complete array and see if the element is there in the given list or not.
int UnorderedLinearSearch(int A[], int n, int data){
for(int i=0; i<n, i++){
if(A[i]==data)
return i;
}
return -1;
}
Sorted/Ordered Linear Search
If the elements of the array are already sorted, then in many cases we don’t have to scan the
complete array to see if the element is there in the given array or not. In the algorithm below, it
can be seen that, at any point if the value at A[i] is greater than the data to be searched, then we
just return –1 without searching the remaining array.
int OrederedLinearSearch(int A[], int n, int data){
for(int i=0; i<n, i++){
if(A[i]==data)
return i;
else if(A[i]>data)
return -1;
}
return -1;
}

Binary Search
Let us consider the problem of searching a word in a dictionary. Typically, we directly go to
some approximate page [say, middle page] and start searching from that point. If the name that we
are searching is the same then the search is complete. If the page is before the selected pages then
apply the same process for the first half; otherwise apply the same process to the second half.
Binary search also works in the same way. The algorithm applying such a strategy is referred to
as binary search algorithm.
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search
algorithm works on the principle of divide and conquer. For this algorithm to work properly, the
data collection should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the collection. If a
match occurs, then the index of item is returned. If the middle item is greater than the item, then the
item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in
the sub-array to the right of the middle item. This process continues on the sub-array as well until
the size of the subarray reduces to zero.

32
How Binary Search Works?
For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the
process of binary search with a pictorial example. The following is our sorted array and let us
assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula

mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that
the value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a
sorted array, so we also know that the target value must be in the upper portion of the array.

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the
value must be in the lower part from this location.

33
Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be made to
very less numbers.

Pseudocode
The pseudocode of binary search algorithms should look like this
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched

Set lowerBound = 1
Set upperBound = n

while x not found

if upperBound < lowerBound
EXIT: x does not exists.

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] = x
EXIT: x found at location midPoint
end while

end procedure

34
Assignment
1) write a program in C programming using linear search to display an element found in a list.
2) Write a program in C programming using binary search to display an element found in a list.

35