AMERICAN INTERNATIONAL UNIVERSITY-BANGLADESH (AIUB)

FACULTY OF SCIENCE & TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE

LAB MANUAL 01
CSC2211 Algorithms
Fall
2024-2025
 TITLE

A review of Linear Searching and Different Sorting Algorithms

PREREQUISITE

 Have a clear understanding of Arrays

 Have a basic idea about Data Structure
 Have a basic idea about Pseudocode

OBJECTIVE

 To understand the significance of Algorithms

 To be able to implement Linear Search
 To be able to implement Bubble Sort
 To be able to implement Selection Sort
 To be able to implement Insertion Sort

THEORY

Algorithm

An algorithm is a step by step method of solving a problem. It is commonly used for data
processing, calculation and other related computer and mathematical operations. An algorithm
is also used to manipulate data in various ways, such as inserting a new data item, searching for
a particular item or sorting an item.

Technically, computers use algorithms to list the detailed instructions for carrying out an
operation. For example, to compute an employee’s paycheck, the computer uses an algorithm.
To accomplish this task, appropriate data must be entered into the system. In terms of
efficiency, various algorithms are able to accomplish operations or problem solving easily and
quickly.

In an algorithm, each instruction is identified and the order in which they should be carried out
is planned. Algorithms are often used as a starting point for creating a computer program, and
they are sometimes written as a flowchart or in pseudocode.
Searching Algorithms

Searching Algorithms are designed to check for an element or retrieve an element from any
data structure where it is stored. Based on the type of search operation, these algorithms are
generally classified into two categories:

Sequential Search: In this, the list or array is traversed sequentially and every element is
checked. For example: Linear Search.

Interval Search: These algorithms are specifically designed for searching in sorted data-
structures. This type of searching algorithms are much more efficient than Linear Search as they
repeatedly target the center of the search structure and divide the search space in half. For
Example: Binary Search.

Linear Search

 A linear search scans one item at a time, without jumping to any item.
 The worst case complexity is O(n), sometimes known an O(n) search
 Time taken to search elements keeps increasing as the numbers of elements are
increased.

Example:

Input: arr[] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}
x = 110;
Output: 6
Element x is present at index 6

Input: arr[] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}
x = 175;
Output: -1
Element x is not present in arr[].

Pseudocode for Linear Search

procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure
 Sorting Algorithms
A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison
operator on the elements. The comparison operator is used to decide the new order of element in the
respective data structure.

Example:

Input: 7, 6, 1, 5, 3, 4, 9, 5

Output: 1, 3, 4, 5, 5, 6, 7, 9

Bubble Sort:

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.

Pseudocode for Bubble Sort

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

Selection Sort

The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an
unsorted array and then putting it in its correct position in a sorted array.

Pseudocode for Selection Sort

SELECTION-SORT(A)

for j ← 1 to n-1
smallest ← j
for i ← j + 1 to n
if A[ i ] < A[ smallest ]
smallest ← i

Exchange A[ j ] ↔ A[ smallest ]
Insertion Sort

Insertion sort is based on the idea that one element from the input elements is consumed in each
iteration to find its correct position i.e, the position to which it belongs in a sorted array.

It iterates the input elements by growing the sorted array at each iteration. It compares the current
element with the largest value in the sorted array. If the current element is greater, then it leaves the
element in its place and moves on to the next element else it finds its correct position in the sorted
array and moves it to that position. This is done by shifting all the elements, which are larger than the
current element, in the sorted array to one position ahead.

Pseudocode for Insertion Sort

INSERTION-SORT(A)

for j = 2 to n

key ← A [j]

j←i–1

while i > 0 and A[i] > key

A[i+1] ← A[i]

i←i–1

A[j+1] ← key

Counting Sort Algorithm

Counting sort is a sorting technique based on keys between a specific range. It works by
counting the number of objects having distinct key values (kind of hashing). Then doing some
arithmetic to calculate the position of each object in the output sequence.

Let us understand it with the help of an example.

For simplicity, consider the data in the range 0 to 9.

Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique
object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0

2) Modify the count array such that each element at each index
stores the sum of previous counts.
 Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in

the output sequence.

3) Output each object from the input sequence followed by

decreasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
Put data 1 at index 2 in output. Decrease count by 1 to place
next data 1 at an index 1 smaller than this index.

Pseudocode for Counting Sort

CountingSort(A)

for i = 0 to k do
c[i] = 0

//Storing Count of each element

for j = 0 to n do
c[A[j]] = c[A[j]] + 1

// Change C[i] such that it contains actual position of these

elements in output array

for i = 1 to k do
c[i] = c[i] + c[i-1]

//Build Output array from C[i]

for j = n-1 down to 0 do

B[ c[A[j]]-1 ] = A[j]
c[A[j]] = c[A[j]] - 1
end func