UNIT 2

Overview of Array, Array as an Abstract Data Type, Operations on Array, Storage

Representation, Multidimensional Arrays[2D, nD], Sparse matrix representation
using 2D Searching: Sequential Search/Linear Search, Binary Search, Fibonacci
Search, and Indexed Sequential Search.
Sorting: Concepts- Stability, Efficiency, and Number of Passes, Internal and External
Sorting, Bubble sort, Insertion Sort, Selection Sort , Quick Sort, Merge sort

ADT:

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and
behaviors for a data structure, without specifying how these operations are
implemented or how data is organized in memory. The definition of ADT only mentions
what operations are to be performed but not how these operations will be
implemented. It does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations. It is called "abstract" because
it provides an implementation-independent view.
The process of providing only the essentials and hiding the details is known
as abstraction.
Features of ADT
Abstract data types (ADTs) are a way of encapsulating data and operations on that data
into a single unit. Some of the key features of ADTs include:
 Abstraction: The user does not need to know the implementation of the data
structure only essentials are provided.
 Robust: The program is robust and has the ability to catch errors.
 Encapsulation: ADTs hide the internal details of the data and provide a public
interface for users to interact with the data. This allows for easier maintenance and
modification of the data structure.
 Data Abstraction: ADTs provide a level of abstraction from the implementation
details of the data. Users only need to know the operations that can be performed on
the data, not how those operations are implemented.
 Data Structure Independence: ADTs can be implemented using different data
structures, such as arrays or linked lists, without affecting the functionality of the
ADT.
 Information Hiding: ADTs can protect the integrity of the data by allowing access
only to authorized users and operations. This helps prevent errors and misuse of the
data.
 Modularity: ADTs can be combined with other ADTs to form larger, more complex
data structures. This allows for greater flexibility and modularity in programming.

Array as an Abstract Data Type

 Arrays are stored in consecutive set of memory locations.

 Array can be thought of as set of index and values.

 For each index which is defined there is a value associated with that index.

 There are two operations permitted on array data structure .retrieve and store
What are Python Arrays?
Arrays are a fundamental data structure, and an important part of most programming
languages. In Python, they are containers which are able to store more than one item at the
same time.Specifically, they are an ordered collection of elements with every value being of
the same data type. That is the most important thing to remember about Python arrays - the
fact that they can only hold a sequence of multiple items that are of the same type.

What's the Difference between Python Lists and Python Arrays?

When to Use Python Arrays

Lists are built into the Python programming language, whereas arrays aren't. Arrays
are not a built-in data structure, and therefore need to be imported via the array module in
order to be used.Arrays of the array module are a thin wrapper over C arrays, and are useful
when you want to work with homogeneous data.

They are also more compact and take up less memory and space which makes them more
size efficient compared to lists. If you want to perform mathematical calculations, then you
should use NumPy arrays by importing the NumPy package.

How to Use Arrays in Python

In order to create Python arrays, you'll first have to import the array module which contains
all the necessary functions.

There are three ways you can import the array module:
1) By using import array at the top of the file. This includes the module array. You would
then go on to create an array using array.array().
import array
2) Instead of having to type array.array() all the time, you could use import array as arr at
the top of the file, instead of import array alone. You would then create an array by
typing arr.array(). The arr acts as an alias name, with the array constructor then
immediately following it.
import array as arr
3) Lastly, you could also use from array import *, with * importing all the functionalities
available. You would then create an array by writing the array() constructor alone.
from array import *

How to Define Arrays in Python:

Once you've imported the array module, you can then go on to define a Python
array.The general syntax for creating an array looks like this:
variable_name = array(typecode,[elements])
Let's break it down:
 variable_name would be the name of the array.
 The typecode specifies what kind of elements would be stored in the array.
Whether it would be an array of integers, an array of floats or an array of any other
Python data type. Remember that all elements should be of the same data type.
 Inside square brackets you mention the elements that would be stored in the array,
with each element being separated by a comma. You can also create an empty array
by just writing variable_name = array(typecode) alone, without any elements.
Below is a typecode table, with the different typecodes that can be used with the different
data types when defining Python arrays:

Typecode C type Python Type Size

'b' signed char int 1

'B' unsigned char int 1

'u' wchar_t Unicode character 2

'h' signed short int 2

 Typecode C type Python Type Size

'H' unsigned short int 2

'i' signed int int 2

'I' unsigned int int 2

'l' signed long int 4

'L' unsigned long int 4

'q' signed long long int 8

'Q' unsigned long long int 8

'f' float float 4

'd' double float 8

here is an example of how you would define an array in Python:

1. import array as arr

numbers = arr.array('i',[10,20,30])
print(numbers)
output :array('i', [10, 20, 30])

Let's break it down:

 First we included the array module, in this case with import array as arr.
 Then, we created a numbers array.
 We used arr.array() because of import array as arr.
 Inside the array() constructor, we first included i, for signed integer. Signed integer
means that the array can include positive and negative values. Unsigned integer,
with H for example, would mean that no negative values are allowed.
 Lastly, we included the values to be stored in the array in square brackets.

Keep in mind that if you tried to include values that were not of i typecode, meaning
they were not integer values, you would get an error:
import array as arr
numbers = arr.array('i',[10.0,20,30])
print(numbers)
#output
#Traceback (most recent call last):
# File "/Users/dionysialemonaki/python_articles/demo.py", , in <module>
# numbers = arr.array('i',[10.0,20,30])
 #TypeError: 'float' object cannot be interpreted as an integer

In the example above, I tried to include a floating point number in the array. I got an
error because this is meant to be an integer array only.

2. from array import *

#an array of floating point values
numbers = array('d',[10.0,20.0,30.0])
print(numbers)
#output: array('d', [10.0, 20.0, 30.0]
The example above imported the array module via from array import * and created
an array numbers of float data type. This means that it holds only floating point
numbers, which is specified with the 'd' typecode.

How to Find the Length of an Array in Python

To find out the exact number of elements contained in an array, use the built-
in len() method.It will return the integer number that is equal to the total number of
elements in the array you specify.
import array as arr
numbers = arr.array('i',[10,20,30])
print(len(numbers))
#output: 3
In the example above, the array contained three elements – 10, 20, 30 – so the length
of numbers is 3.

Array Indexing and How to Access Individual Items in an Array in Python

Each item in an array has a specific address. Individual items are accessed by referencing
their index number. Indexing in Python, and in all programming languages and computing in
general, starts at 0. It is important to remember that counting starts at 0 and not at 1.
To access an element, you first write the name of the array followed by square brackets.
Inside the square brackets you include the item's index number.The general syntax would
look something like this: array_name[index_value_of_item]
Here is how you would access each individual element in an array:
import array as arr
numbers = arr.array('i',[10,20,30])
print(numbers[0]) # gets the 1st element
print(numbers[1]) # gets the 2nd element
 print(numbers[2]) # gets the 3rd element

output
#10
#20
#30
Remember that the index value of the last element of an array is always one less than the
length of the array. Where n is the length of the array, n - 1 will be the index value of the last
item.
Note that you can also access each individual element using negative indexing.With negative
indexing, the last element would have an index of -1, the second to last element would have
an index of -2, and so on.Here is how you would get each item in an array using that
method:
import array as arr
numbers = arr.array('i',[10,20,30])
print(numbers[-1]) #gets last item
print(numbers[-2]) #gets second to last item
print(numbers[-3]) #gets first item
#output
#30
#20
#10
How to Search Through an Array in Python
You can find out an element's index number by using the index() method.
You pass the value of the element being searched as the argument to the method, and the
element's index number is returned.
import array as arr
numbers = arr.array('i',[10,20,30])
#search for the index of the value 10
print(numbers.index(10))
#output
#0
If there is more than one element with the same value, the index of the first instance of the
value will be returned:
import array as arr
numbers = arr.array('i',[10,20,30,10,20,30])
#search for the index of the value 10
#will return the index number of the first instance of the value 10
print(numbers.index(10))
#output
#0
How to Loop through an Array in Python
You've seen how to access each individual element in an array and print it out on its
own.You've also seen how to print the array, using the print() method. That method gives
the following result:
 import array as arr
numbers = arr.array('i',[10,20,30])
print(numbers)
#output
#array('i', [10, 20, 30])

What if you want to print each value one by one?

This is where a loop comes in handy. You can loop through the array and print out
each value, one-by-one, with each loop iteration.For this you can use a simple for loop:
import array as arr
numbers = arr.array('i',[10,20,30])
for number in numbers:
print(number)
#output
#10
#20
#30
You could also use the range() function, and pass the len() method as its parameter. This
would give the same result as above:
import array as arr
values = arr.array('i',[10,20,30])
#prints each individual value in the array
for value in range(len(values)):
print(values[value])
#output
#10
#20
#30
How to Slice an Array in Python
To access a specific range of values inside the array, use the slicing operator, which
is a colon :
When using the slicing operator and you only include one value, the counting starts
from 0 by default. It gets the first item, and goes up to but not including the index number
you specify.
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#get the values 10 and 20 only
print(numbers[:2]) #first to second position
#output
#array('i', [10, 20])
When you pass two numbers as arguments, you specify a range of numbers. In this case, the
counting starts at the position of the first number in the range, and up to but not including
the second one:
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#get the values 20 and 30 only
print(numbers[1:3]) #second to third position
#output
#array('i', [20, 30])
How to Change the Value of an Item in an Array
You can change the value of a specific element by speficying its position and assigning it a
new value:
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#change the first element
#change it from having a value of 10 to having a value of 40
numbers[0] = 40
print(numbers)
#output
#array('i', [40, 20, 30])

How to Add a New Value to an Array

To add one single value at the end of an array, use the append() method:
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#add the integer 40 to the end of numbers
numbers.append(40)
print(numbers)
#output
#array('i', [10, 20, 30, 40])
Be aware that the new item you add needs to be the same data type as the rest of the
items in the array.Look what happens when I try to add a float to an array of integers:
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#add the float 40.0 to the end of numbers
numbers.append(40.0)
print(numbers)
#output
 #Traceback (most recent call last):
# File "/Users/dionysialemonaki/python_articles/demo.py", line 19, in <module>
# numbers.append(40.0)
#TypeError: 'float' object cannot be interpreted as an integer

But what if you want to add more than one value to the end an array?
Use the extend() method, which takes an iterable (such as a list of items) as an
argument. Again, make sure that the new items are all the same data type.
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#add the integers 40,50,60 to the end of numbers
#The numbers need to be enclosed in square brackets
numbers.extend([40,50,60])
print(numbers)
#output
#array('i', [10, 20, 30, 40, 50, 60])
And what if you don't want to add an item to the end of an array?
Use the insert() method, to add an item at a specific position.
The insert() function takes two arguments: the index number of the position the new
element will be inserted, and the value of the new element.
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
#add the integer 40 in the first position
#remember indexing starts at 0
numbers.insert(0,40)
print(numbers)
#output
#array('i', [40, 10, 20, 30])
How to Remove a Value from an Array
To remove an element from an array, use the remove() method and include the
value as an argument to the method.
import array as arr
#original array
numbers = arr.array('i',[10,20,30])
numbers.remove(10)
print(numbers)
#output
#array('i', [20, 30])
With remove(), only the first instance of the value you pass as an argument will be removed.
See what happens when there are more than one identical values:
import array as arr
#original array
numbers = arr.array('i',[10,20,30,10,20])
numbers.remove(10)
print(numbers)
#output
#array('i', [20, 30, 10, 20])

Only the first occurence of 10 is removed.

You can also use the pop() method, and specify the position of the element to be removed:
import array as arr
#original array
numbers = arr.array('i',[10,20,30,10,20])
#remove the first instance of 10
numbers.pop(0)
print(numbers)
#output
#array('i', [20, 30, 10, 20])

Numpy

import numpy as np

# Create a 1D array from a list

arr_1d = np.array([1, 2, 3, 4, 5])
print("1D Array:") print(arr_1d)
# Create a 2D array from a list of lists
arr_2d = np.array([[1, 2, 3], [4, 5, 6]])
print("\n2D Array:")
print(arr_2d)

# Create a 3D array from a nested list of lists arr_3d =

np.array([[[1, 2], [3, 4]], [[5, 6], [7, 8]]])
print("\n3D Array:")
print(arr_3d)
OutPut:
1D Array:
[1 2 3 4 5]

2D Array:
[[1 2 3]
[4 5 6]]

3D Array:
[[[1 2]
[3 4]]

[[5 6]
[7 8]]]

Built in functions

1. np.zeros(shape): Creates an array filled with zeros.

2. np.ones(shape): Creates an array filled with ones.
3. np.full(shape, fill_value): Creates an array filled with a specified value.

Array Attributes:

1. arr.shape: Returns a tuple indicating the dimensions of the array.

2. arr.ndim: Returns the number of dimensions (axes) of the array.
3. arr.size: Returns the total number of elements in the array.
4. arr.dtype: Returns the data type of the elements in the array.

Operations on array:

Addition,subtraction,multiplication ,division,power,reshape ,concatenate are some of

the operations allowed on array.
Storage representation of arrays:

Different languages uses different kind of representations for storing array elements. C is
row-major (as is C++, Pascal, and Python), Fortran is column- major (as is Julia, R and
Matlab).
It is all about how array elements are stored in memory. Row major stores an array row-
by-row, and column major stores an array column-by-column
e.g.

Address calculation of element for row major and column major representation:

1. Row Major Address

To calculate the address of an element in the ith row and jth column, we need to count how
many memory locations have been used by the elements in the preceeding i-1 rows (where
each row has N elements) in addition to the memory locations used by the preceeding j-1
elements in the current row. Each element need as many bytes as used by the data type of
the array. Hence, calculating the number of bytes required by all the preceeding elements
in a row major fashion and adding this to the base address, would give use the address of
the required element.
address[i][j] = B + (row_index * total no. of columns + column_index)*element_size
B : Base address
Lr : lower bound for row
Lc : lower bound for column
S : size of single element stored in array(depend on it’s data type) N: Total
number of columns in each row
 2. Column Major Address
Here, for an element at index (i,j) we need to calculate the number of memory locations
required by the elements in the preceeding j-1 columns (where each column has M
elements) in addition to the i-1 elements in the current column. Adding this amount to the
base element will give us the address of the required element.
address[i][j] = B + (column_index * total no. of rows + row_index)*element_size
B : Base address
S : size of single element stored in array(depend on it’s data type)

Example 1: Consider two dimensional array of size ( 4*5) storing integer elements in row
major representation. Array is having base address 200.Find address of element X(3,2)
.(Note : size of each integer element is 4 bytes
Solution: Here given array X is of size (4*5) and elements are stored in row major form.
As we know Address of any element X [i][j] = B + (row_index * total no. of columns +
column_index)*element_size
B : Base address
S : size of single element stored in array(depend on it’s data type)
N: Total number of columns in each row
Here ,
Base address of array X = B=200
S=size of element=4 bytes (as here every element is of type int)
i=current row =3
j=current column =2
N=total columns in each row=5

Address of X(3,2) = B + (row_index * total no. of columns + column_index)*element_size

=200 +[( 3 * 5 + 2 ] * 4 =200 +[ 15 + 2 ] *4

=200 + 17 *4
=200+68
= 268
Example 2: Consider two dimensional array of size ( 4*3) storing integer elements in
Column major representation. Array is having base address 100.Find address of element
X(3,2) .
(Note : size of each integer element is 4 bytes)

Here given array X is of size (4*3) and elements are stored in column major form.
As we know,
Address of any element X [i][j] = B+(column_index * total no. of rows +
row_index)*element_size
B : Base address
i=current row =3
j=current column =2
S : size of single element stored in array(depend on it’s data type)

Here ,
Base address of array X = B=200
since column numbers are starting from zero
M=total elements in each row=4
Address of X(3,2) = B+(column_index * total no. of rows + row_index)*element_size
=200 +[(2 * 4 + 3 ] * 4
=200 + [ 8+ 3]*4
=200 + 11 *4
=200 + 44
=244
A matrix is a two-dimensional data object made of m rows and n columns, therefore having
total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse
matrix.
Why to use Sparse Matrix instead of simple matrix ?
 Storage: There are lesser non-zero elements than zeros and thus lesser memory can be
used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data structure
traversing only non-zero elements..
Example:

00304
00570
00000
02600

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in

the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero
elements, we only store non-zero elements. This means storing non-zero elements
with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays:
2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index - (row,column)

Method 2 : using link list

In linked list, each node has four fields. These four fields are defined as:
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index - (row,column)
 Next node: Address of the next node