SORTING ALGORITHMS

Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on
the elements. The comparison operator is used to decide the new order of elements in the respective data
structure

Importance of Sorting Algorithm

The sorting algorithm is important in Computer Science because it reduces the complexity of a problem.
They are crucial for optimizing data processing and enhancing the performance of various applications,
including searching and data analysis.

Classification of sorting algorithms

Algorithms classified into various categories depending on diverse characteristics of the algorithms and also
on the resource usage of them.
i)In-place Sorting & Out of place sorting algorithm
In-place Sorting
In-place algorithms convert the input in to an output without allocating extra memory space for the process
of problem solving. It uses the available space given as the input and replaces input with output.
These algorithms rearrange the elements within the array being sorted, without using any additional space or
memory.
The algorithm operates directly on the input array, modifying its content in place.
Examples of in-place sorting algorithms include:
Bubble Sort: An in-place sorting algorithm that rearranges elements within the original array by comparing
adjacent elements and swapping them if they are in the wrong order.
Selection Sort: Another in-place sorting algorithm that divides the list into two parts the sorted part and the
unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the
end of the sorted part.
QuickSort: QuickSort is an in-place sorting algorithm that works upon the divide and conquer paradigm.
The divide and conquer approach divides the problem into subproblems and continuously divides it until it
becomes a unit problem, then it solves or conquers the problems easily.
Insertion Sort: Insertion Sort is both an in-place and stable algorithm. It is stable because it preserves the
relative order of elements with equal keys. This means that if you have two elements with the same value in
the original list, their order will be maintained in the sorted list as well.
1
Not in-place or "out-of-place" sorting algorithm requires extra memory (beyond the input array) to store
intermediate results or a sorted copy
Requires space which is more than or equal to the elements being sorted.
These algorithms require space that is more than or equal to the elements being sorted to store intermediate
results.
Example is Merge Sort
N.B: When studying algorithms in Computer Science, we come across algorithms that fall into these two
categories. Choosing what algorithm among them to be the best is subjective, yet it is good to know the
following before you make that decision.
 Working in-place is a good way to save time and space. An in-place algorithm avoids the cost of
initializing or copying data structures.
 But, an in-place algorithm can cause side effects. The input is usually destroyed to replace with
output which can affect code outside of the method.
 Therefore, generally out-of-place algorithms are considered safer because they avoid such side
effects.
 One should only use an in-place algorithm if the space is constrained or the original input is not
useful anymore (even for debugging).

i) Stable and Not Stable Sorting

Stable Sorting Algorithm

Stable Sorting maintains the relative order of elements with equal values in the original data set i.e. if two
elements have the same value, the algorithm will sort them in the same order as they appear in the original
data set.
Stability is mainly essential when we have key-value pairs with duplicate keys possible (like people’s names
as keys and their details as values). And we wish to sort these objects by keys.
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted
output as they appear in the input data set.
Examples of stable sorting algorithms are Merge Sort, Insertion Sort,

Unstable Sorting Algorithm

2
These algorithms do not guarantee to maintain the relative order of elements with equal values in the original
data set i.e. the order in which elements with the same value appear in the sorted output may not be the same
as their order in the original data set.
Examples of unstable sorting algorithms are Quick Sort, Selection Sort.

The Efficiency of Sorting Algorithms

The efficiency of sorting algorithms is determined by factors like
Time complexity (how quickly the algorithm sorts),
Time complexity depends on several factors, such as the number of comparisons, swaps, and other
operations that the algorithm performs. To compare the time complexity of different sorting algorithms, we
use Big O notation, which expresses the worst-case, average-case, and best-case scenarios of how the
algorithm scales with the input size.
For example, the time complexity of bubble sort is O(n^2) in the worst and average cases, and O(n) in the
best case, where n is the number of elements to sort.
Space complexity (how much memory it uses)
Space complexity, which is the amount of extra memory or space that the algorithm requires to sort the
input.
Space complexity also depends on several factors, such as the number of auxiliary arrays, variables, and
recursive calls that the algorithm uses.
To compare the space complexity of different sorting algorithms, we use Big O notation, which expresses
the worst-case scenario of how the algorithm uses extra space with the input size.
Example, the space complexity of merge sort is O(n) in the worst case, where n is the number of elements to
sort.
Stability (whether it preserves the original order of equal elements.

3
Stability refers to whether the algorithm preserves the relative order of elements with equal keys after
sorting. For example, a stable sorting algorithm would keep the original order of students with the same
grades after sorting by grades.
TYPES OF SORTING ALGORITHMS

i. Insertion sort
ii. Selection sort
iii. Divide and conquer Merge sort
iv. Bubble sort
Bubble sort
- Works by repeatedly moving the largest element to the highest index position of the array.
- Rather than searching the entire array to find the largest element, bubble sort focuses on successive
adjacent pairs of elements in the array.

Array 0 Array 1 8
8 - 5 7 3 9 - - -
- - - - - - - - -

Array [0] is greater than array [1] so switch the two elements

Array 0 Array 1 8
5 - 8 7 3 9 - - -
- - - - - - - - -

General algorithm for Bubble sort

Main loop
- Compare two adjacent elements at index “k” and “k+1”
- If the elements at index “k” is greater than the element “k+1” then swap the positions of the two
values.
- One iteration moves largest value to the last position of array
- Repeat loop

4
Step-by-step example
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using
bubble sort algorithm. In each step, elements written in bold are being compared. Three passes will be
required.
First Pass:
( 51 4 2 8 ) ( 15 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 154 2 8 ) ( 1 45 2 8 ), Swap since 5 > 4
( 1 4 52 8 ) ( 1 4 25 8 ), Swap since 5 > 2
( 1 4 2 58 ) ( 1 4 2 58 ), Now, since these elements are already in order (8 > 5), algorithm does not swap
them.
Second Pass:
( 14 2 5 8 ) ( 14 2 5 8 )
( 1 42 5 8 ) ( 1 24 5 8 ), Swap since 4 > 2
( 1 2 45 8 ) ( 1 2 45 8 )
( 1 2 4 58 ) ( 1 2 4 58 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one
whole pass without any swap to know it is sorted.
Third Pass:
( 12 4 5 8 ) ( 12 4 5 8 )
( 1 24 5 8 ) ( 1 24 5 8 )
( 1 2 45 8 ) ( 1 2 45 8 )
( 1 2 4 58 ) ( 1 2 4 58 )

Pseudocode implementation
The algorithm can be expressed as:
procedurebubbleSort( A : list of sortable items )
repeat
swapped = false
fori = 1 to length(A) - 1 inclusive do:
if A[i-1] > A[i] then
swap( A[i-1], A[i] )
swapped = true

5
end if
end for
until not swapped
end procedure

Complexity Analysis of Bubble Sort:

Time Complexity: O(n2)
Auxiliary Space: O(1)

Advantages of Bubble Sort:

 Bubble sort is easy to understand and implement.
 It does not require any additional memory space.
 It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative
order in the sorted output.

Disadvantages of Bubble Sort:

 Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.
 Bubble sort has almost no or limited real world applications. It is mostly used in academics to teach
different ways of sorting
Exercise:
Write bubble sort algorithm and apply it to sort the list E,X,A,M,P,L,E.

GRAPH ALGORITHMS:
A graph is a data structure that describe relationships between entities connecting vertices and Edges.
A graph G with a set of V vertices together with a set of E edges is represented as G= (V, E).
Graphs are mostly used to represent various networks like computer networks, social networks, etc.
Graph traversal
The graph traversal involves a search strategy to find a path from the initial state to a goal state.
Examples of Search Problems
Chess game - Each turn explore a move for a win
Route finding - Explore routes for one to gets the destination
Theorem proving : Explore reasoning for proof

6
Evaluating Search strategies
There are four characteristics used to evaluate search graph algorithms:
i. Completeness: the strategy should guarantee to find a solution if one exists?
ii. Optimality: Does the solution have low cost or the minimal cost? Optimal solution achieved
iii. Time complexity: Time taken or the number of nodes visited to find a solution.
iv. Space complexity: Space used by the algorithm i.e. measured in terms of the maximum size of the
search space
Graph Searching - Path finding algorithms
Uninformed search (blind search)
i) Informed search heuristic search a*
ii) Uninformed search / blind search bfs & dfs
Informed search heuristic search
Algorithms that systematically explore a graph to find a goal node without domain-specific knowledge about
the search space. examples BFS & DFS, Dijkstra’s algorithm
Informed search heuristic search
Informed search, also known as heuristic search, uses problem-specific knowledge to find a goal more
efficiently than blind. Example heuristic example search A* Search

Breadth first search

The search strategy visits the nodes of the same level first.
Main idea: Nodes at depth i are expanded before nodes at depth (i+1).
Implementation: use of a First-In-First-Out queue (FIFO).
Example- provided lecture time
The performance measure of BFS is as follows/ BFS evaluation
Completeness: Yes if the branching factor b is finite. (maximum number of successors of any node.) the
branching factor (i.e., number of children) at each node.
Optimality: shallowest goal is not necessarily the optimal one. It is optimal if all actions have the same cost.
Time complexity: At the worst case, BFS expands every node (except goal node) thus taking alot of time
Memory complexity: BFS keeps every node in memory. Space is a big problem.

DFS
7
Un informed search algorithm that expands the deepest node in the current search tree.

DFS strategy is implemented using a Last-In_First-Out (LIFO) queue or stack.

DFS evaluation

Completeness: Incomplete in case of unbounded depth containing no solution.

Optimality: does not provide always optimal solutions.

Time complexity: In the worst case: the goal node may be on the right-most branch
Space complexity. Largest number of nodes in QUEUE is reached in bottom left-most node.

DIJKSTRA’S ALGORITHM - informed

Dijkstra's algorithm finds the shortest path from one vertex to all other vertices.
It does so by repeatedly selecting the nearest unvisited vertex and calculating the distance to all the unvisited
neighboring vertices.
algorithm for finding the shortest path between two nodes in a graph. It works by starting at the source node
and progressively exploring the graph, adding nodes to the shortest path as it goes.
Use of Dijkstra's algorithm
i) GIS map navigation (GPS),
ii) Network routing protocols
iii) logistics/transportation planning,
iv) Path finding in games
v) In telecommunications to determine transmission rate.
vi) In robotic design to determine shortest path for automated robots.

Algorithm for Dijkstra’s Algorithm:

i)Initialization:
-Set the distance to the source node to 0 and the distance to all other nodes to infinity
-Mark all nodes as unvisited and place them into a set or priority queue.
ii)Selection:
Pick the unvisited node with the smallest current distance from the source. On the first step, this will
always be the source node.
iii)Distance Update):

8
  For the current node, look at all of its unvisited neighbors.
 Calculate their tentative distance by adding the current node's distance to the weight of the edge
connecting them.
 If this new distance is less than the previously recorded distance, update it.
iv)Completion:
 Once all neighbors are checked, mark the current node as visited. A visited node will never be
checked again.
 Repeat steps 2–4 until all nodes in the graph have been visited

How does Dijkstra’s Algorithm

Consider the below graph

The algorithm will generate the shortest path from node 0 to all the other nodes in the graph.
The weight of the edges represents the distance between two nodes.
Step 1: Start from Node 0 mark the Node as visited , check it with adjacent notes

9
Step 2: Check for adjacent Nodes, (Either Node1 with distance 2 or Node 2 with distance 6 ) and choose
Node with minimum distance.
Node 1 is Minimum distance adjacent Node, marked as visited and add up the distance
Distance: Node 0 -> Node 1 = 2

Step 3: Move Forward check for adjacent Node i.e Node 3, marked as visited and add up the distance.
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7

10
Step 4: Two choices for adjacent Nodes (Node 4 with distance 10 or Node 5 with distance 15)
Choose Node with minimum distance, Node 4 is Minimum distance adjacent Node, marked it as visited and
add up the distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17

Step 5: Move Forward check adjacent Node i.e Node 6, marked as visited and add up the distance,
distance:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2 = 19

11
Therefore the Shortest Distance from the Source Vertex is 19 which is the optimal one
Dijkstra algorithm

Function dijkstra(G, S) // (source node 'S') to all other nodes in a graph 'G
for each vertex V in G
distance[V] = infinite
previous[V] = NULL
If V != S, add V to Priority Queue Q
distance[S] = 0

while Q IS NOT EMPTY

U = Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]
=================================
function Dijkstra(Graph, source):
12
 for each vertex v in [Link]:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0

while Q is not empty:

u ← vertex in Q with min dist[u]
remove u from Q

for each neighbor v of u still in Q:

alt ← dist[u] + [Link](u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]

Applications of Dijkstra's Algorithm

Here are some of the common applications of Dijkstra's algorithm:
 In maps to get the shortest distance between locations. An example is Google Maps.
 In telecommunications to determine transmission rate.
 In robotic design to determine shortest path for automated robots.

Informed search / Heuristic search strategy/ guided search

Use the problem specific information to guide the search in promising directions using a heuristic function.
A Heuristic is an operation with information on how to direct a search in a problem space.
Heuristics are criteria, methods or principles for deciding which among several alternative courses of action
promises to be the most effective in order to achieve some goal”.

A* Search algorithm

13
A* Search is an informed best-first search algorithm that efficiently determines the lowest cost path between
any two nodes

The A* algorithm is based on cost functions and heuristics.

g(n): The actual cost from the starting node to any node n.
h(n): The heuristic estimated cost from node n to the goal. This is where A* integrates knowledge beyond
the graph to guide the search.
The evaluation function, f(n), for the A* search algorithm is the following:
f(n) = g(n) + h(n)
Where g(x) represents the cost to get to node x and h(x) represents the estimated cost to arrive at the goal
node from node x.

Path cost g(n), represents the exact, known distance from the initial starting node to the current position in
the search.
The heuristic function h(n) provides an estimated cost from the current node to the goal node, acting as the
algorithm's "informed guess" about the remaining path.
N.B: The A* algorithm maintains two essential lists
Open list:
 Contains nodes that need to be evaluated
 Sorted by f(n) value (lowest first)
 New nodes are added as they're discovered
Closed list:
 Contains already evaluated nodes
 Helps avoid re-evaluating nodes
 Used to reconstruct the final path

14
The algorithm continually selects the node with the lowest f(n) value from the open list, evaluates it, and
moves it to the closed list until it reaches the goal node or determines no path exists.
Algorithm Procedure
An open list, implemented as a priority queue, which stores the next nodes to be explored.
Because this is a priority queue, the most promising candidate node (the one with the lowest value from the
evaluation function) is always at the top. Initially, the only node in this list is the start node S.
A closed list which stores the nodes that have already been evaluated. When a node is in the closed list, it
means that the lowest-cost path to that node has been found.
To find the lowest cost path, a search tree is constructed in the following way:
1. Initialize a tree with the root node being the start node S.
2. Remove the top node from the open list for exploration.
3. Add the current node to the closed list.
4. Add all nodes that have an incoming edge from the current node as child nodes in the tree.
5. Update the lowest cost to reach the child node.
6. Compute the evaluation function for every child node and add them to the open list.
Example : Where node A is the initial state and H the goal node.

The algorithm starts with A. successors of A, are B, C, H.

From A to B,
f(n) = g(n) + h(n), 1 + 3 = 4.
From A to C, 2 + 4 = 6.
From A to H, 7 + 0 = 7.
The lowest cost is 4, and the path A to B is chosen. Note: Other paths will be on hold.
15
Select node B for expansion, pick successors D or E.
From A to B to D, the cost is 1 + 4 + 2 = 7 .
From A to B to E, 1 + 6 + 6 = 13.
The lowest cost is 7. Path A to B to D is chosen and compared with other on-hold paths.
Here, paths A to C are of less cost. i,e 6.
Hence, A to C is chosen, and other paths are kept on hold.
Expand node C, and generate successors F & G.
From A to C to F, the cost is 2 + 3 + 3 = 8.
from A to C to G. the cost is 2 + 2 + 1 = 5
The lowest cost is 5, which is also less than other paths on hold. Hence, paths A to G are chosen.
Expand G, pick successor node H, whose cost is 2 + 2 + 2 + 0 = 6.
Here, 6 is less than the cost of other paths, which is on hold.
H is the goal state and the algorithm terminates.
Applications of A* Search Algorithm
The A* algorithm, a powerful path finding technique, finds practical applications in diverse fields like video
games (NPC movement), navigation systems (GPS route optimization), robotics (autonomous vehicle
navigation), and network routing, ensuring efficient and optimal path finding
 Network Routing: In telecommunications, A* helps in determining the shortest routing path that
data packets should take to reach the destination.
 AI and Machine Learning: A* can be used in planning and decision-making algorithms, where
multiple stages of decisions and movements need to be evaluated.
 Navigation: Pathfinding is essential in GPS systems to calculate the shortest or fastest route between
two locations. Systems use algorithms like A* to constantly recalculate paths based on real-time
traffic updates.
 Video Games: Many strategy games rely on AI characters that need to navigate terrain or obstacles
to reach a goal. Games like StarCraft use pathfinding to control character movement.
 Robotics: Autonomous robots, such as vacuum cleaners or delivery drones, require pathfinding to
avoid obstacles and navigate efficiently in dynamic environments

16
A* Algorithm evaluation
The effectiveness of the A* algorithm largely depends on the heuristic used. The choice of heuristic can
dramatically affect the performance and efficiency of the algorithm. A good heuristic is one that helps the
algorithm find the shortest path by exploring the least number of nodes possible. The properties of a heuristic
include:
 Admissibility: A heuristic is admissible if it never overestimates the cost of reaching the goal. The
classic example of an admissible heuristic is the straight-line distance in a spatial map.
 Consistency (or Monotonicity): A heuristic is consistent if the estimated cost from the current node
to the goal is always less than or equal to the estimated cost from any adjacent node plus the step cost
from the current node to the adjacent node.
Exercise.
The state space description for a problem is shown below, with A is the start state and D the goal state.
Shown on the graph are path costs between states. The table lists the estimated distance from a state to the
goal. Perform an A* search for this problem, showing (a) the tree that represents the nodes expanded and (b)
the ordered list of nodes to expand at each step along with the node’s value.

17