Lecture 3

Twaha Kateete
[email protected]
+256778313421
2/13/2025 MIU 1
Outline
 Arrays
 Introduction
 x-tics o Arrays
 Types of Arrays
 Array Operations
 Traversing
 Inserting
 Searching
 Deleting
 Sorting

2/13/2025 MIU 2
2/13/2025 MIU 3
 Arrays
 An array data structure is a fundamental concept in
computer science and Software Engineering that stores a
collection of elements in a contiguous block of memory.
 It efficient access to elements using indices and it is
widely used in programming for organizing and
manipulating data.
 Arrays are one of the most fundamental data structures in
programming.
 They store a fixed-size sequential collection of elements.
 Unlike lists in Python, which can hold different data
types, arrays typically hold elements of a single data type.
 It is one of the most popular and simple data structures
and is often used to implement other data structures.

2/13/2025 MIU 4
Why Array Data Structures
▪ Creating dynamic data structures such as linked lists and trees.

▪ Space Efficiency, Arrays occupy least space compared to other data

structures like stacks and linked lists.

▪ Storing data for processing

▪ Implementing data structures such as stacks and queues.

▪ Representing data in tables and matrices.

▪ Time Complexity, Arrays offer O(1) time complexity for access to elements.
This makes arrays faster than other data structures.

• .

2/13/2025 MIU 5
 X-tics of Arrays
Fixed Size: Once most arrays are created, their sizes cannot be changed, you
cannot add or remove elements but you can only modify the existing ones.

Sequential Storage: Elements in an array are stored in contiguous memory

locations. This makes accessing elements by index very fast.

Homogeneous: All elements in an array are of the same data type. Hence
being easy to manipulate

Order: Arrays are linear data structures that store items in a specific order.

Searching: The time complexity of searching an element in arrays is O(n).

Access: Arrays offer direct access to any element with its index or position
number.

Insertion and Deletion: Insertion and deletion operations take more time than
searching an element as it requires shifting elements from one location to
another.
2/13/2025 MIU 6
How Arrays work in DSs
 Arrays in data structure stores a set of data in an
organized manner.
 The size of an array is determined by the number of
elements it can hold.
 They have their unique syntax and functions, making
them very useful for storing large amounts of
information.
 They can store anything from numbers and strings to
complex objects like classes and arrays.

2/13/2025 MIU 7
2/13/2025 MIU 8
 Size Basis
 Fixed Sized: No altering or updating the size of this
array. Only a fixed size of memory will be allocated
for storage.
Fixed-Sized Arrays Use libraries like numpy or the array
module. These arrays have a fixed size and are less flexible
but may offer performance benefits when you know the
array's size ahead of time.

2/13/2025 MIU 9
 Dynamic Sized: The size of the array changes as per user
requirements during execution of code so the coders do not have
to worry about sizes. They can add and removed the elements as
per the need. The memory is mostly dynamically allocated and
de-allocated in these arrays.
 Dynamic-Sized Arrays: Python's built-in list is inherently
dynamic. Lists are flexible and convenient for most use cases
where the size of the data changes, though they may incur
performance costs during resizing operations.

2/13/2025 MIU 10
 Differences – Fixed and Dynamic Sized
Fixed-Sized Arrays (e.g., Dynamic-Sized Arrays
Feature
numpy, array module) (list)
Can grow or shrink
Size Fixed at creation
dynamically

Memory Allocation Static memory allocation Dynamic memory allocation

Resizing (e.g., append, pop)

Resizing Not possible; size is fixed
allowed
Generally faster for fixed May be slower due to resizing
Performance
operations and copying

When array size is known When array size is unknown

Use Cases
and constant or changes frequently

Example Libraries array, numpy Python list

2/13/2025 MIU 11
 Dimensional Basis
 i. One-Dimensional
 Contains a single row of elements. These arrays are usually
indexed from 0 to n-1.

numpy library is mostly used for array manipulation in python

2/13/2025 MIU 12
 2. Two-Dimensional
 Two-dimensional array type are arrays that contain arrays of
elements. These are also referred to as matrix arrays since they can
be thought of as a grid that lays out the elements into rows and
columns. Each element within the two-dimensional array can be
accessed individually by its row and column location.

2/13/2025 MIU 13
  iii. Multi-Dimensional
 Multi-Dimensional arrays are a powerful data structure
used to store and manage data organizationally. This type
of arrays consist of multiple arrays that are arranged
hierarchically.

2/13/2025 MIU 14
 iii. Multi-Dimensional

The array_3d consists of two layers (2 matrices). Each matrix has 3 rows and 3 columns,
corresponding to the provided sets of elements.
The first matrix contains the elements {5, 10, 20}, {25, 30, 35}, {1, 3, 4}.
The second matrix contains the elements {2, 8, 12}, {1, 3, 4}, {8, 7, 22}.

2/13/2025 MIU 15
 Jagged Array
 A jagged array (also known as a "ragged array") is an array
of arrays where the inner arrays can have different
lengths. In Python, we create a jagged array using lists.

2/13/2025 MIU 16
Common Operations on Arrays
 Traversing, Traversing arrays involves looping through each
element in the array and processing each element one at a
time.
 Insertion, Insertion is the process of adding new elements
into an existing array.
 Deletion, Deletion is the opposite of insertion and involves
removing elements from an existing array.
 Searching, process of identifying an element from within
an array by comparing it to your desired value until you find
a match.
 Sorting, Sorting is a process of arranging elements of an
array in either ascending or descending order.
2/13/2025 MIU 17
Traversing - Arrays

2/13/2025 MIU 18
 Insertion - Arrays
Single-Dimensional Array: Use insert(index, element)
to insert an element at a specific index.
Two-Dimensional Array: Use insert(index, row) to add
a new row.
Multi-Dimensional Array: Use numpy.insert to add
new layers along a specified axis.

2/13/2025 MIU 19
 Insertion - Arrays

2/13/2025 MIU 20
 Deletion - Arrays
Single-Dimensional Array: Use del array[index] to remove an element at a
specific index or pop(index) to remove and return the element.
Two-Dimensional Array: Use del array[index] to remove an entire row or
pop(index) to remove an element from a row.
Multi-Dimensional Array: Use numpy.delete(array, index, axis) to
remove elements along a specific axis.

2/13/2025 MIU 21
Deletion - Arrays

2/13/2025 MIU 22
Deletion - Arrays

2/13/2025 MIU 23
Searching - Arrays
Single-Dimensional Array: Use in to check for existence and index() to find the
position of the element.
Two-Dimensional Array: Iterate through each row to find the element. Use index()
to find the column position within the row.
Multi-Dimensional Array: Use numpy.where() to find the indices of the element
across all dimensions. This function returns indices in the form of tuples for each
dimension.

2/13/2025 MIU 24
Searching - Arrays

2/13/2025 MIU 25
Searching - Arrays

2/13/2025 MIU 26
Sorting - Arrays
Single-Dimensional Array: Use sort() to sort in place or sorted() to create a new
sorted list.
Two-Dimensional Array: Sort each row individually using sort() or sort the entire
array based on a specific column using a custom key in sort().
Multi-Dimensional Array: Use numpy.sort() with the axis parameter to sort along
a specific axis or flatten, sort, and reshape the array.

2/13/2025 MIU 27
 Sorting Each Row
Individually

Sorting Entire Array

Based on a Specific
Column

2/13/2025 MIU 28
 Sorting Along a
Specific Axis

Flattening and
Sorting

2/13/2025 MIU 29
 Questions

2/13/2025 MIU 30