Bubble Sort; 2- Insertion Sort; 3- Selection Sort

8. How many swappings are required to sort the following array in descending order?
int arr [6] = {8, 22, 7, 0, 5, 13};

1- Bubble Sort; 2- Insertion Sort; 3- Selection Sort explain the whole process step by step

Copilot

Certainly! Let’s walk through the process of sorting the array int arr[6] = {8, 22, 7, 0, 5,
13}; in descending order using Bubble Sort, Insertion Sort, and Selection Sort, and count the
number of swappings required for each.

1. Bubble Sort: Bubble Sort works by repeatedly swapping the adjacent elements if they are in
the wrong order. Here’s how it would work on your array:
Original array: [8, 22, 7, 0, 5, 13]
Pass 1:
- Compare 8 and 22, no swap needed
- Compare 22 and 7, no swap needed (22 > 7)
- Compare 22 and 0, no swap needed (22 > 0)
- Compare 22 and 5, no swap needed (22 > 5)
- Compare 22 and 13, no swap needed (22 > 13)
Pass 2:
- Compare 8 and 7, no swap needed (8 > 7)
- Compare 8 and 0, no swap needed (8 > 0)
- Compare 8 and 5, no swap needed (8 > 5)
- Compare 8 and 13, swap needed: [8, 13, 7, 0, 5, 8]
Pass 3:
- Compare 8 and 7, no swap needed (8 > 7)
- Compare 8 and 0, no swap needed (8 > 0)
- Compare 8 and 5, no swap needed (8 > 5)
- Array is sorted
Total swaps = 1
 2. Insertion Sort: Insertion Sort builds the sorted array one element at a time by shifting
elements to make room for each new element at its correct position.
Original array: [8, 22, 7, 0, 5, 13]
- 22 is already in place
- Insert 7: Shift 22 to the right, array becomes [8, 22, 22, 0, 5, 13], insert 7: [8, 7, 22, 0, 5, 13]
- Insert 0: Shift 22 and 7 to the right, array becomes [8, 7, 7, 22, 5, 13], insert 0: [8, 0, 7, 22, 5, 13]
- Insert 5: Shift 22, 7, and 0 to the right, array becomes [8, 0, 0, 7, 22, 13], insert 5: [8, 5, 0, 7, 22, 13]
- Insert 13: Shift 22 to the right, array becomes [8, 5, 0, 7, 22, 22], insert 13: [8, 5, 0, 7, 13, 22]
- Array is sorted
Total shifts (equivalent to swaps) = 8

3. Selection Sort: Selection Sort selects the largest element from the unsorted portion and
swaps it with the first unsorted element.
Original array: [8, 22, 7, 0, 5, 13]
- Select 22 (largest), no swap needed as it's already in the correct position
- Select 13 (next largest), swap with 8: [13, 22, 7, 0, 5, 8]
- Select 8 (next largest), no swap needed as it's already in the correct position
- Select 7 (next largest), no swap needed as it's already in the correct position
- Select 5 (next largest), swap with 0: [13, 22, 7, 5, 0, 8]
- Select 0 (next largest), no swap needed as it's already in the correct position
- Array is sorted
Total swaps = 2

In summary:

● Bubble Sort required 1 swap to sort the array.

● Insertion Sort required 8 shifts (equivalent to swaps) to sort the array.
● Selection Sort required 2 swaps to sort the array in descending order.

Each algorithm has its own process and efficiency depending on the initial order of the elements and
the algorithm’s design. In this case, Bubble Sort was the most efficient with the fewest number of
swaps needed to sort the array in descending order. Please note that the number of swaps can vary
depending on the implementation details of each sorting algorithm.
You

9. How many swappings are required to sort the following array in ascending order?
int arr [6] = {8, 22, 7, 0, 5, 13};

1- Bubble Sort; 2- Insertion Sort; 3- Selection Sort

Copilot

To sort the array int arr[6] = {8, 22, 7, 0, 5, 13} in ascending order, let’s analyze the
number of swappings required for each sorting algorithm and explain the process step by step:

1. Bubble Sort: Bubble Sort repeatedly compares adjacent elements and swaps them if they are
in the wrong order. The process continues until the entire array is sorted.
Original array: [8, 22, 7, 0, 5, 13]
Pass 1:
- Compare 8 and 22, swap needed: [22, 8, 7, 0, 5, 13]
- Compare 8 and 7, no swap needed
- Compare 7 and 0, swap needed: [22, 7, 8, 0, 5, 13]
- Compare 8 and 0, swap needed: [22, 7, 0, 8, 5, 13]
- Compare 8 and 5, swap needed: [22, 7, 0, 5, 8, 13]
- Compare 8 and 13, swap needed: [22, 7, 0, 5, 13, 8]
Pass 2 to Pass 5:
- Continue the process until no more swaps are needed
Total swaps = 5

2. Insertion Sort: Insertion Sort builds the sorted array one element at a time by shifting
elements to make room for each new element at its correct position.
Original array: [8, 22, 7, 0, 5, 13]
- 8 is already in place
- Insert 22: Shift 8 to the right, array becomes [8, 8, 7, 0, 5, 13], insert 22: [22, 8, 7, 0, 5, 13]
- Insert 7: Shift 8 to the right, array becomes [22, 8, 8, 0, 5, 13], insert 7: [22, 7, 8, 0, 5, 13]
- Insert 0: No shifts needed, 0 is smaller than all sorted elements
- Insert 5: Shift 8 and 7 to the right, array becomes [22, 7, 7, 8, 8, 13], insert 5: [22, 7, 5, 7, 8, 13]
- Insert 13: Shift 8 to the right, array becomes [22, 7, 5, 7, 8, 8], insert 13: [22, 7, 5, 7, 13, 8]
- Continue the process until the array is fully sorted
Total swaps = 6
 3. Selection Sort: Selection Sort selects the smallest element from the unsorted portion and
swaps it with the first unsorted element.
Original array: [8, 22, 7, 0, 5, 13]
- Select 0 (smallest), swap with 8: [0, 22, 7, 8, 5, 13]
- Select 5 (next smallest), swap with 22: [0, 5, 7, 8, 22, 13]
- Select 7 (next smallest), no swap needed as it's already in the correct position
- Select 8 (next smallest), no swap needed as it's already in the correct position
- Select 13 (next smallest), swap with 22: [0, 5, 7, 8, 13, 22]
- Array is sorted
Total swaps = 3

In summary, to sort the array in ascending order:

● Bubble Sort requires 5 swaps.

● Insertion Sort requires 6 swaps.
● Selection Sort requires the least number of swaps, with only 3 swaps needed.

Please note that the number of swaps can vary depending on the implementation details of each
sorting algorithm. The provided steps are based on a general approach to each sorting method.

Let's go through each of these algorithms one by one:

Breadth-First Search (BFS):

15. BFS is a graph traversal algorithm that explores nodes in a level-wise manner. Starting
from a chosen node, it explores all of its neighbors before moving on to the next level of
nodes. BFS is typically implemented using a queue data structure to keep track of the
nodes to be visited next. This algorithm is commonly used to find the shortest path in an
unweighted graph, to find connected components, and to solve puzzles like the shortest
path in a maze.

Usage/Implementation:
 ● Shortest path finding in an unweighted graph.
● Finding connected components in a graph.
● Puzzle solving (e.g., finding the shortest solution in a maze).

Depth-First Search (DFS):

16. DFS is another graph traversal algorithm that explores as far as possible along each
branch before backtracking. It explores one branch of a tree-like graph structure as
deeply as possible before exploring the next branch. DFS can be implemented using a
stack data structure (or recursion). This algorithm is often used to detect cycles in a
graph, to generate topological orderings, and to solve puzzles like finding a path in a
maze.

Usage/Implementation:

● Detecting cycles in a graph.

● Generating topological orderings.
● Puzzle solving (e.g., finding a path in a maze).

Dijkstra's Algorithm:
17. Dijkstra's Algorithm is a graph search algorithm used to find the shortest path between
nodes in a weighted graph with non-negative edge weights. It maintains a set of nodes
whose shortest distance from the source node is already known and continuously
updates the shortest distance to all nodes from the source node. Dijkstra's Algorithm
uses a priority queue to select the node with the smallest distance as the next node to
visit. This algorithm is commonly used in routing and network traffic optimization.

Usage/Implementation:

● Finding the shortest path in a weighted graph with non-negative edge weights.
● Routing and network traffic optimization.

Topological Sort:
18. Topological Sort is an ordering of the nodes in a directed acyclic graph (DAG) such that
for every directed edge from node u to node v, node u comes before node v in the
ordering. Topological sorting is used when there are dependencies between tasks, and
the tasks need to be executed in a specific order without violating any dependencies. It
can be implemented using DFS.

Usage/Implementation:

● Dependency resolution in task scheduling.

● Building systems with a set of dependencies where certain tasks must be completed
before others can begin.

Minimum Spanning Tree (MST):

 19. A Minimum Spanning Tree of a connected, undirected graph is a subset of the edges
that form a tree that includes every vertex, where the sum of the weights of the edges is
minimized. MST algorithms find the subset of edges that form the minimum spanning
tree. Popular algorithms for finding the MST include Kruskal's algorithm and Prim's
algorithm.

Usage/Implementation:

● Designing networks where the cost of connecting all nodes is minimized.

● Clustering algorithms.
● Approximation algorithms for optimization problems.

2/2

Let's break down the differences between each of these tree data structures:

a. B-Tree:

● B-Tree is a self-balancing tree data structure that maintains sorted data and allows
searches, sequential access, insertions, and deletions in logarithmic time.
● B-Trees are designed to work well with disks and other secondary storage devices,
making them suitable for databases and file systems.
● B-Trees have a variable but often large number of child nodes per node, which allows
them to remain balanced even with large amounts of data.
● B-Trees are commonly used in databases and file systems for indexing.

b. Binary Tree:

● Binary Tree is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child.
● In a binary tree, each node can have zero, one, or two children.
●

c. Binary Search Tree (BST):

● All nodes of left subtree are less than the root node •All nodes of right subtree are more
than the root node •Both subtrees of each node are also BSTs i.e. they have the above
two propertie
●

d. Ternary Tree:
 ● Ternary Tree is a tree data structure in which each node has up to three children.
●

e. AVL Tree:

● AVL Tree is a self-balancing binary search tree in which the heights of the two child
subtrees of any node differ by at most one.