Array

Application
Programming 2
Erwin D. Marcelo
November 2023
Sorting
01. Bubble Sort 02Balloon Sort
This sorting algorithm The balloon sort compares the first element
is comparison-based with each following element of the array,
algorithm in which making any necessary swaps. When the first
each pair of adjacent pass through the array is complete, the
elements is compared balloon sort then takes the second element
and the elements are and compares it with each following element
swapped if they are of the array swapping elements that are out
not in order. of order.

Sorting algorithms are a set of instructions that take an array or list as an

input and arrange the items into a particular order. Sorts are most
commonly in numerical or a form of alphabetical (or lexicographical)
order, and can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0) order.
 BUBBLE SORT
In this algorithm,
•traverse from left and compare adjacent elements and the
higher one is placed at right side.
•In this way, the largest element is moved to the rightmost
end at first.
•This process is then continued to find the second largest
and place it and so on until the data is sorted.
BUBBLE SORT
51 18 10 16 9
0K 1 2 3 4

• COMPARE Key Element

• IF Greater Than, then Swap

51 18 10 16 9
0K 1K+1 2 3 4
18 51 10 16 9
0 1K 2K+1 3 4
18 10 51 16 9
0 1 2K 3K+1 4
18 10 16 51 9
0K 1 2 3K 4K+1
BUBBLE SORT

First Pass
18 10 16 9 51
0 1 2 3 4

Largest element has been placed to the last index

BUBBLE SORT
18 10 16 9 51
0K 1 2 3 4

• COMPARE Key Element

• IF Greater Than, then Swap

18 10 16 9 51
0K 1K+1 2 3 4
10 18 16 9 51
0 1K 2K+1 3 4
10 16 18 9 51
0 1 2K 3K+1 4
BUBBLE SORT

Second Pass
10 16 9 18 51
0 1 2 3 4

2nd largest element has been placed to its proper location

BUBBLE SORT
10 16 9 18 51
0K 1 2 3 4

• COMPARE Key Element

• IF Greater Than, then Swap

10 16 9 18 51
0K 1K+1 2 3 4
10 16 9 18 51
0 1K 2K+1 3 4
BUBBLE SORT

Third Pass
10 9 16 18 51
0 1 2 3 4

3rd largest element has been placed to its proper location

BUBBLE SORT
10 16 9 18 51
0K 1 2 3 4

• COMPARE Key Element

• IF Greater Than, then Swap

10 16 9 18 51
0K 1K+1 2 3 4
BUBBLE SORT

Fourth Pass
9 10 16 18 51
0 1 2 3 4

4th largest element has been placed to its proper location

 BALLOON SORT
In this algorithm,
•To sort an array of size N in ascending order iterate over
the array and compare the current element (key) to its
predecessor, if the key element is smaller than its
predecessor, compare it to the elements before. Move the
greater elements one position up to make space for the
swapped element.

12 Annual Review March 2, 2024

 BALLOON SORT
9 7 4 6 2
0Key 1 2 3 4
• COMPARE Key Element
• IF Greater Than, then Swap
9 7 4 6 2
0K 1K+1 2 3 4
7 9 4 6 2
0-K 1 2K+2 3 4
4 9 7 6 2
0K 1 2 3K+3 4

4 9 7 6 2
0-K 1 2 3 4K+4
March 2, 2024
 BALLOON SORT

First Pass
2 9 7 6 4
0 1 2 3 4

Smallest element has been placed to the first index

March 2, 2024
 BALLOON SORT
2 9 7 6 4
0 1 Key 2 3 4
• COMPARE
• IF Greater Than, then Swap
2 9 7 6 4
0 1K 2 K+1 3 4
2 7 9 6 4
0 1-K 2 3K+2 4

2 6 9 7 4
0 1K 2 3 4K+3

March 2, 2024
 BALLOON SORT

Second Pass
2 4 9 7 6
0 1 2 3 4

2nd smallest element has been placed to the second index

March 2, 2024
 BALLOON SORT
2 4 9 7 6
0 1 2 Key 3 4
• COMPARE
• IF Greater Than, then Swap
2 4 9 7 6
0 1 2 K 3  K+1 4
2 4 7 9 6
0 1 2K 3 4 K+2

March 2, 2024
 BALLOON SORT

Third Pass
2 4 6 9 7
0 1 2 3 4

3rd smallest element has been placed to the third index

March 2, 2024
 BALLOON SORT
2 4 6 9 7
0 1 2 3 Key 4
• COMPARE
• IF Greater Than, then Swap
2 4 6 9 7
0 1 2 3 K 4  K+1

March 2, 2024
 BALLOON SORT

Fourth Pass
2 4 6 7 9
0 1 2 3 4

4th smallest element has been placed to the fourth index

March 2, 2024
Searching
01. Linear Search 02. Binary Search
This algorithm works by This type of searching algorithm is used to
sequentially iterating through find the position of a specific value
the whole array or list from contained in a sorted array. The binary
one end until the target search algorithm works on the principle of
element is found. If the divide and conquer and it is considered the
element is found, it returns best searching algorithm because it's faster
its index, else -1.
Search algorithms are
to run.
designed to check or
retrieve an element
from any data structure
Any algorithm which solves the search problem, namely, to retrieve where that element is
information stored within some data structure, or calculated in the search being stored. They
space of a problem domain, either with discrete or continuous values. search for a target (key)
in the search space.
 LINEAR SEARCH
Approach for Linear or Sequential Search
• Start with index 0 and compare each element with the target
• If the target is found to be equal to the element, return its index
• If the target is not found, return -1

March 2, 2024
 • Start with index 0 and
compare each element

LINEAR SEARCH with the target

• If the target is found to
be equal to the element,
return its index

Find: 7
• If the target is not found,
return -1

X
2 X
4 X
6 7 9
0 1 2 3 4

Return: 3
March 2, 2024
 • Start with index 0 and
compare each element

LINEAR SEARCH with the target

• If the target is found to
be equal to the element,
return its index

Find: 8
• If the target is not found,
return -1

X
2 X
4 X
6 X
7 X
9
0 1 2 3 4

March 2, 2024
Return: -1
 BINARY SEARCH
Approach for Binary Search
•Compare the target element with the middle element
of the array.
•If the target element is greater than the middle
element, then the search continues in the right half.
•Else if the target element is less than the middle
value, the search continues in the left half.
•This process is repeated until the middle element is
equal to the target element, or the target element is
not in the array
•If the target element is found, its index is returned,
else -1 is returned.

March 2, 2024
 •Compare the target
element with the middle
element of the array.

BINARY SEARCH •If the target element is

greater than the middle
element, then the search
continues in the right half.

Find: 43 •Else if the target element

is less than the middle
value, the search continues
in the left half.
2 6 9 15 18 X 43 60
X 21 37 •This process is repeated
until the middle element is
equal to the target element,
0 1 2 3 4 5 6 7 8 or the target element is not
s m s m s e in the array
m •If the target element is
found, its index is returned,
else -1 is returned.

March 2, 2024
Return: 7
 •Compare the target
element with the middle
element of the array.

BINARY SEARCH •If the target element is

greater than the middle
element, then the search
continues in the right half.

Find: 8 •Else if the target element

is less than the middle
value, the search continues
in the left half.
2 X
6 X X 21 37 43 60
9 15 18 •This process is repeated
until the middle element is
equal to the target element,
0 1 2 3 4 5 6 7 8 or the target element is not
s m s e m e in the array
e m •If the target element is
found, its index is returned,
else -1 is returned.

March 2, 2024
Return: -1
Multi-
Dimensional
Array
Programming 2
Erwin D. Marcelo
November 2023
A two-dimensional
array in C++ is the
simplest form of a multi-
dimensional array. It can
be visualized as an array of
arrays. The image below
depicts a two-dimensional
array.

A two-dimensional array is
also called a matrix. It can be
of any type like integer,
character, float, etc.
depending on the
initialization. In the next
section, we are going to
discuss how we can initialize
2D arrays.
 In the above code,
•We firstly initialize a 2D array, arr[4]
[2] with certain values,
•After that, we try to print the respective
array using two for loops,
•the outer for loop iterates over the rows,
while the inner one iterates over the
columns of the 2D array,
•So, for each iteration of the outer
loop, i increases and takes us to the next
1D array. Also, the inner loop traverses
over the whole 1D array at a time,
•And accordingly, we print the individual
element arr[ i ][ j ].
33 Annual Review
Taking 2D Array Elements As User In
put
#include<iostream>
using namespace std;
main( )
{
int s[2][2];
int i, j;
cout<<"\n2D Array Input:\n";
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
cout<<"\ns["<<i<<"]["<<j<<"]= ";
cin>>s[i][j];
}
}

cout<<"\nThe 2-D Array is:\n";

for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
cout<<"\t"<<s[i][j];
}
cout<<endl;
34 }
Annual Review
}
“