Unit-3

Insertion Sort :
I. Insertion sort is a sorting algorithm that places an unsorted element at its
suitable place in each iteration.
II. Insertion sort works similar to the sorting of playing cards in hands. It is
assumed that the first card is already sorted in the card game, and then we
select an unsorted card.
III. If the selected unsorted card is greater than the first card, it will be placed at
the right side; otherwise, it will be placed at the left side.
IV. Similarly, all unsorted cards are taken and put in their exact [Link] same
approach is applied in insertion sort.
V. The idea behind the insertion sort is that first take one element, iterate it
through the sorted array.
VI. Although it is simple to use, it is not appropriate for large data sets as the
time complexity of insertion sort in the average case and worst case is O(n2),
where n is the number of items. Insertion sort is less efficient than the other
sorting algorithms like heap sort, quick sort, merge sort, etc.
VII. Insertion sort has various advantages such as -
VIII. Simple implementation
Efficient for small data sets
Adaptive, i.e., it is appropriate for data sets that are already substantially
sorted.

A. Simple implementation
B. Efficient for small data sets
C. Adaptive, i.e., it is appropriate for data sets that are already substantially
sorted.
IX. Algorithm of insertion sort: The simple steps of achieving the insertion
sort are listed as follows -
Step1 - If the element is the first element, assume that it is already sorted.
Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step4 - If the element in the sorted array is smaller than the current element,
then move to the next element. Else, shift greater elements in the array
towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.
Time Complexity Case Time Complexity
1. Best Case O(n)
2. Average Case O(n2)
3. Worst Case O(n2)
a) Best Case Complexity - It occurs when there is no
sorting required, i.e. the array is already sorted. The best-
case time complexity of insertion sort is O(n).
b) Average Case Complexity - It occurs when the array
elements are in jumbled order that is not properly
ascending and not properly descending. The average case
time complexity of insertion sort is O(n2).
c) Worst Case Complexity - It occurs when the array
elements are required to be sorted in reverse order. That
means suppose you have to sort the array elements in
ascending order, but its elements are in descending
order. The worst-case time complexity of insertion sort is
O(n2).
d) Space Complexity : Space Complexity O(1)Stable YES.
The space complexity of insertion sort is O(1). It is
because, in insertion sort, an extra variable is required for
swapping.
Selection Sort
Selection sort is a simple and efficient sorting algorithm that works by
repeatedly selecting the smallest (or largest) element from the unsorted
portion of the list and moving it to the sorted portion of the list.

The algorithm repeatedly selects the smallest (or largest) element from the
unsorted portion of the list and swaps it with the first element of the unsorted
part. This process is repeated for the remaining unsorted portion until the
entire list is sorted.

Let's consider the following array as an example: arr[]={64, 25, 12, 22, 11}

e) First pass:
(1) For the first position in the sorted array, the whole
array is traversed from index 0 to 4 sequentially.
The first position where 64 is stored presently, after
traversing the whole array it is clear that 11 is the
lowest value.
(2) Thus, replace 64 with 11. After one iteration 11,
which happens to be the least value in the array,
tends to appear in the first position of the sorted
list.
f) Second Pass:
(1) For the second position, where 25 is present, again
traverse the rest of the array in a sequential
manner.
(2) After traversing, we found that 12 is the second
lowest value in the array and it should appear at
the second place in the array, thus swap these
values.
g) Third Pass:
(1) Now, for third place, where 25 is present again,
traverse the rest of the array and find the third
least value present in the array.
(2) While traversing, 22 came out to be the third least
value and it should appear at the third place in the
array, thus swap 22 with element present at third
position.
h) Fourth pass:
(1) Similarly, for fourth position traverse the rest of the
array and find the fourth least element in the array
(2) As 25 is the 4th lowest value hence, it will place at
the fourth position.
i) Fifth Pass:
 (1) At last the largest value present in the array
automatically get placed at the last position in the
array
(2) The resulting array is the sorted array.

Merge Sort–Merge sort is defined as a sorting algorithm that works by

dividing an array into smaller subarrays, sorting each subarray, and then
merging the sorted subarrays back together to form the final sorted array.

How does Merge Sort work? : Merge sort is a recursive algorithm that continuously
splits the array in half until it cannot be further divided i.e., the array has only one
element left (an array with one element is always sorted). Then the sorted
subarrays are merged into one sorted array.
See the below illustration to understand the working of merge sort.
Illustration:
Let's consider an array arr[] = {38, 27, 43, 10}
● Initially divide the array into two equal halves:
● These subarrays are further divided into two halves. Now they become array
of unit length that can no longer be divided and array of unit length are always
sorted.
These sorted subarrays are merged together, and we get bigger sorted subarrays.
This merging process is continued until the sorted array is built from the smaller
subarrays.
The following diagram shows the complete merge sort process for
an example array {38, 27, 43, 10}.
QuickSort – Data Structure and Algorithm Tutorials :
QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that
picks an element as a pivot and partitions the given array around the picked pivot
by placing the pivot in its correct position in the sorted array.
How does QuickSort work?
The key process in quickSort is a partition(). The target of partitions is to place the
pivot (any element can be chosen to be a pivot) at its correct position in the sorted
array and put all smaller elements to the left of the pivot, and all greater elements
to the right of the pivot.
Partition is done recursively on each side of the pivot after the pivot is placed in its
correct position and this finally sorts the array.

How Quicksort works

Choice of Pivot:
There are many different choices for picking pivots.
● Always pick the first element as a pivot.
● Always pick the last element as a pivot (implemented below)
● Pick a random element as a pivot.
● Pick the middle as the pivot.
Partition Algorithm:
The logic is simple, we start from the leftmost element and keep track of the index
of smaller (or equal) elements as i. While traversing, if we find a smaller element,
we swap the current element with arr[i]. Otherwise, we ignore the current element.
Let us understand the working of partition and the Quick Sort algorithm with the
help of the following example:
Consider: arr[] = {10, 80, 30, 90, 40}.
● Compare 10 with the pivot and as it is less than pivot arrange it accrodingly.
● Compare 80 with the pivot. It is greater than pivot. Partition in QuickSort:
Compare pivot with 80
● Compare 30 with pivot. It is less than pivot so arrange it accordingly. Partition
in QuickSort: Compare pivot with 30
● Compare 90 with the pivot. It is greater than the pivot. Partition in QuickSort:
Compare pivot with 90
● Arrange the pivot in its correct position. Partition in QuickSort: Place pivot in
its correct position
Illustration of Quicksort:
As the partition process is done recursively, it keeps on putting the pivot in its
actual position in the sorted array. Repeatedly putting pivots in their actual position
makes the array sorted.
Follow the below images to understand how the recursive implementation of the
partition algorithm helps to sort the array.
● Initial partition on the main array: Quicksort: Performing the partition
● Partitioning of the subarrays: Quicksort: Performing the partition
Comparison based sorting algorithms :
● In a comparison based sorting algorithms, we compare elements of an array
with each other to determines which of two elements should occur first in the final
sorted list.
● All comparison-based sorting algorithms have a complexity lower bound of
nlogn.
● Here is the comparison of time and space complexities of some popular
comparison based sorting algorithms:
Non-comparison based sorting algorithm :
● There are sorting algorithms that use special information about the keys and
operations other than comparison to determine the sorted order of elements.
● Consequently, nlogn lower bound does not apply to these sorting algorithms.
In-place and Stable sorting Algorithms
● A sorting algorithm is In-place if the algorithm does not use extra space for
manipulating the input but may require a small though nonconstant extra space for
its operation. Or we can say, a sorting algorithm sorts in-place if only a constant
number of elements of the input array are ever stored outside the array.
● A sorting algorithm is stable if it does not change the order of elements with
the same value.
Online/Offline: The algorithm that accepts a new element while the sorting process
is going on, that algorithm is called the online sorting algorithm. From, the above
sorting algorithms, the insertion sort is online.
Critical ideas to think
● Understanding the sorting algorithms are the best way to learn problem
solving and complexity analysis in the algorithms. In some cases, We often use
sorting as a key routine to solve several coding problems.
● Knowing which algorithm is best possible depends heavily on details of the
application and implementation. In most practical situations, quicksort is a popular
algorithm for sorting large input arrays because its expected running time is
O(nlogn). It also outperforms heap sort in practice.
● If stability is important and space is available, the merge sort might be the
best choice for the implementation.
● Like insertion sort, quick sort has tight code and hidden constant factor in its
running time is small.
● When the input array is almost sorted or input size is small, then the insertion
sort can be preferred.
● We can prefer merge sort for sorting a linked list.
Time Complexities of all Sorting Algorithms
The efficiency of an algorithm depends on two parameters:
1. Time Complexity
2. Space Complexity
Time Complexity:
Time Complexity is defined as the number of times a particular instruction set is
executed rather than the total time taken. It is because the total time taken also
depends on some external factors like the compiler used, the processor’s speed,
etc.
Space Complexity:
Space Complexity is the total memory space required by the program for its
execution.
Both are calculated as the function of input size(n). One important thing here is that
despite these parameters, the efficiency of an algorithm also depends upon the
nature and size of the input.
Types of Time Complexity :
1. Best Time Complexity: Define the input for which the algorithm takes less
time or minimum time. In the best case calculate the lower bound of an algorithm.
Example: In the linear search when search data is present at the first location of
large data then the best case occurs.
2. Average Time Complexity: In the average case take all random inputs and
calculate the computation time for all inputs.
And then we divide it by the total number of inputs.
3. Worst Time Complexity: Define the input for which algorithm takes a long
time or maximum time. In the worst calculate the upper bound of an algorithm.
Example: In the linear search when search data is present at the last location of
large data then the worst case occurs.
Insertion Sort : Insertion sort is a sorting algorithm that places an unsorted
element at its suitable place in each iteration.

The working procedure of insertion sort is also simple. This article will be very
helpful and interesting to students as they might face insertion sort as a question in
their examinations. So, it is important to discuss the [Link] sort works
similar to the sorting of playing cards in hands. It is assumed that the first card is
already sorted in the card game, and then we select an unsorted card. If the
selected unsorted card is greater than the first card, it will be placed at the right
side; otherwise, it will be placed at the left side. Similarly, all unsorted cards are
taken and put in their exact [Link] same approach is applied in insertion sort.
The idea behind the insertion sort is that first take one element, iterate it through
the sorted array. Although it is simple to use, it is not appropriate for large data sets
as the time complexity of insertion sort in the average case and worst case is O(n2),
where n is the number of items. Insertion sort is less efficient than the other sorting
algorithms like heap sort, quick sort, merge sort, etc.

Insertion sort has various advantages such as -

○ Simple implementation
○ Efficient for small data sets

○ Adaptive, i.e., it is appropriate for data sets that are already substantially
sorted.

Now, let's see the algorithm of insertion sort.

The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return
1.

Step2 - Pick the next element, and store it separately in a key.

Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then
move to the next element. Else, shift greater elements in the array towards the
right.

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

Working of Insertion sort Algorithm

Now, let's see the working of the insertion sort Algorithm.

To understand the working of the insertion sort algorithm, let's take an unsorted
array. It will be easier to understand the insertion sort via an example.

Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending
order. So, for now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at the correct position. Now, swap 31 with
25. Along with swapping, insertion sort will also check it with all elements in the
sorted array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12.
Hence, the sorted array remains sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next
elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items
that are 31 and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Insertion sort complexity

Now, let's see the time complexity of insertion sort in best case, average case, and
in worst case. We will also see the space complexity of insertion sort.

1. Time Complexity

Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

○ Best Case Complexity - It occurs when there is no sorting required, i.e.

the array is already sorted. The best-case time complexity of insertion sort is
O(n).
 ○ Average Case Complexity - It occurs when the array elements are in
jumbled order that is not properly ascending and not properly descending. The
average case time complexity of insertion sort is O(n2).

○ Worst Case Complexity - It occurs when the array elements are required
to be sorted in reverse order. That means suppose you have to sort the array
elements in ascending order, but its elements are in descending order. The
worst-case time complexity of insertion sort is O(n2).

2. Space Complexity

Space Complexity O(1)

Stable YES

○ The space complexity of insertion sort is O(1). It is because, in insertion sort,

an extra variable is required for swapping.

Selection Sort : Selection sort is a simple and efficient sorting algorithm that
works by repeatedly selecting the smallest (or largest) element from the unsorted
portion of the list and moving it to the sorted portion of the list.
The algorithm repeatedly selects the smallest (or largest) element from the
unsorted portion of the list and swaps it with the first element of the unsorted part.
This process is repeated for the remaining unsorted portion until the entire list is
sorted.

How does Selection Sort Algorithm work?

Lets consider the following array as an example: arr[] = {64, 25, 12, 22,
11}

First pass:

● For the first position in the sorted array, the whole array is traversed from
index 0 to 4 sequentially. The first position where 64 is stored presently, after
traversing the whole array it is clear that 11 is the lowest value.
● Thus, replace 64 with 11. After one iteration 11, which happens to be the least
value in the array, tends to appear in the first position of the sorted list.

Second Pass:

● For the second position, where 25 is present, again traverse the rest of the
array in a sequential manner.

● After traversing, we found that 12 is the second lowest value in the array and it
should appear at the second place in the array, thus swap these values.

Third Pass:

● Now, for third place, where 25 is present again, traverse the rest of the array
and find the third least value present in the array.

● While traversing, 22 came out to be the third least value and it should appear at
the third place in the array, thus swap 22 with element present at third position.

Fourth pass:

● Similarly, for fourth position traverse the rest of the array and find the fourth
least element in the array

● As 25 is the 4th lowest value hence, it will place at the fourth position.

Fifth Pass:

● At last the largest value present in the array automatically get placed at the
last position in the array

● The resulting array is the sorted array.

Merge Sort –Merge sort is defined as a sorting algorithm that works by dividing an
array into smaller subarrays, sorting each subarray, and then merging the sorted
subarrays back together to form the final sorted array.
How does Merge Sort work? : Merge sort is a recursive algorithm that
continuously splits the array in half until it cannot be further divided i.e., the array
has only one element left (an array with one element is always sorted). Then the
sorted subarrays are merged into one sorted array.
See the below illustration to understand the working of merge sort.

Illustration:

Let's consider an array arr[] = {38, 27, 43, 10}

● Initially divide the array into two equal halves:

● These subarrays are further divided into two halves. Now they
become array of unit length that can no longer be divided and array of
unit length are always sorted.

These sorted subarrays are merged together, and we get bigger sorted subarrays.

This merging process is continued until the sorted array is built from the smaller
subarrays.

The following diagram shows the complete merge sort process for an example array
{38, 27, 43, 10}.

QuickSort – Data Structure and Algorithm Tutorials :

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that
picks an element as a pivot and partitions the given array around the picked pivot
by placing the pivot in its correct position in the sorted array.

How does QuickSort work?

The key process in quickSort is a partition(). The target of partitions is to place

the pivot (any element can be chosen to be a pivot) at its correct position in the
sorted array and put all smaller elements to the left of the pivot, and all greater
elements to the right of the pivot.

Partition is done recursively on each side of the pivot after the pivot is placed in its
correct position and this finally sorts the array.

How Quicksort works

Choice of Pivot:

There are many different choices for picking pivots.

● Always pick the first element as a pivot.

● Always pick the last element as a pivot (implemented below)

● Pick a random element as a pivot.

● Pick the middle as the pivot.

Partition Algorithm:

The logic is simple, we start from the leftmost element and keep track of the index
of smaller (or equal) elements as i. While traversing, if we find a smaller element,
we swap the current element with arr[i]. Otherwise, we ignore the current element.

Let us understand the working of partition and the Quick Sort algorithm with the
help of the following example:

Consider: arr[] = {10, 80, 30, 90, 40}.

● Compare 10 with the pivot and as it is less than pivot arrange it

accrodingly.

● Compare 80 with the pivot. It is greater than pivot.

Partition in QuickSort: Compare pivot with 80

● Compare 30 with pivot. It is less than pivot so arrange it accordingly.

Partition in QuickSort: Compare pivot with 30

● Compare 90 with the pivot. It is greater than the pivot.

Partition in QuickSort: Compare pivot with 90

● Arrange the pivot in its correct position.

Partition in QuickSort: Place pivot in its correct position

Illustration of Quicksort:

As the partition process is done recursively, it keeps on putting the pivot in its
actual position in the sorted array. Repeatedly putting pivots in their actual position
makes the array sorted.

Follow the below images to understand how the recursive implementation of the
partition algorithm helps to sort the array.

● Initial partition on the main array:

Quicksort: Performing the partition

● Partitioning of the subarrays:

Quicksort: Performing the partition

 Comparison based sorting algorithms :

● In a comparison based sorting algorithms, we compare elements of an array

with each other to determines which of two elements should occur first in the final
sorted list.

● All comparison-based sorting algorithms have a complexity lower bound of

nlogn.

● Here is the comparison of time and space complexities of some

popular comparison based sorting algorithms:

Non-comparison based sorting algorithm :

● There are sorting algorithms that use special information about the keys and
operations other than comparison to determine the sorted order of elements.

● Consequently, nlogn lower bound does not apply to these sorting

algorithms.

In-place and Stable sorting Algorithms

● A sorting algorithm is In-place if the algorithm does not use extra space for
manipulating the input but may require a small though nonconstant extra space for
its operation. Or we can say, a sorting algorithm sorts in-place if only a constant
number of elements of the input array are ever stored outside the array.

● A sorting algorithm is stable if it does not change the order of

elements with the same value.

Online/Offline: The algorithm that accepts a new element while the sorting process is
going on, that algorithm is called the online sorting algorithm. From, the above sorting
algorithms, the insertion sort is online.
Critical ideas to think

● Understanding the sorting algorithms are the best way to learn problem
solving and complexity analysis in the algorithms. In some cases, We often use
sorting as a key routine to solve several coding problems.

● Knowing which algorithm is best possible depends heavily on details of the

application and implementation. In most practical situations, quicksort is a popular
algorithm for sorting large input arrays because its expected running time is
O(nlogn). It also outperforms heap sort in practice.

● If stability is important and space is available, the merge sort might be the
best choice for the implementation.

● Like insertion sort, quick sort has tight code and hidden constant factor in its
running time is small.

● When the input array is almost sorted or input size is small, then the insertion
sort can be preferred.

● We can prefer merge sort for sorting a linked list.

Time Complexities of all Sorting Algorithms

The efficiency of an algorithm depends on two parameters:

1. Time Complexity
2. Space Complexity

Time Complexity:

Time Complexity is defined as the number of times a particular instruction set is

executed rather than the total time taken. It is because the total time taken also
depends on some external factors like the compiler used, the processor’s speed,
etc.
Space Complexity:

Space Complexity is the total memory space required by the program for its
execution.

Both are calculated as the function of input size(n). One important thing here is that
despite these parameters, the efficiency of an algorithm also depends upon the
nature and size of the input.

Types of Time Complexity :

1. Best Time Complexity: Define the input for which the algorithm
takes less time or minimum time. In the best case calculate the lower
bound of an algorithm. Example: In the linear search when search data is
present at the first location of large data then the best case occurs.
2. Average Time Complexity: In the average case take all random
inputs and calculate the computation time for all inputs.
And then we divide it by the total number of inputs.
3. Worst Time Complexity: Define the input for which algorithm takes
a long time or maximum time. In the worst calculate the upper bound of
an algorithm. Example: In the linear search when search data is present
at the last location of large data then the worst case occurs.

What is Hashing: Hashing refers to the process of

generating a fixed-size output from an input of variable size using the
mathematical formulas known as hash functions. This technique
determines an index or location for the storage of an item in a data
structure.

What is Hashing in C
In C programming language, hashing is a technique that involves
converting a large amount of data into a fixed-size value or a smaller
value known as a hash. The hash is generated through a hash function,
which maps the input data to an output hash. The resulting hash value
can then be used to efficiently search, retrieve, and compare data
within large data sets.

Hashing is commonly used in data structures such as hash tables,

which are arrays that store data in a way that allows for quick
insertion, deletion, and retrieval of data. The hash function used to
generate the hash value maps the key (or the data to be stored) to an
index within the hash table. This index is then used to store the data in
the corresponding location within the array.

Hashing is useful for several reasons. Firstly, it can reduce the amount
of memory required to store large data sets by converting the data into
a smaller value. Secondly, it can improve the performance of
algorithms by allowing for faster searching and retrieval of data.
Finally, it can help to ensure data integrity by detecting duplicate data
and preventing collisions (when two different keys map to the same
index).

The process of hashing involves three main steps: creating the hash
function, generating the hash value, and storing the data in the hash
table.

Creating the hash function involves designing an algorithm that maps

the input data to a fixed-size value. This algorithm should be designed
to distribute the data evenly across the hash table to reduce the
likelihood of collisions. A good hash function should also be fast,
simple, and deterministic (i.e. it should always produce the same
output for the same input).

Once the hash function is created, the next step is to generate the
hash value for the data. This involves passing the data through the
hash function, which returns a fixed-size hash value. This value is then
used as an index within the hash table to store the data.

Storing the data in the hash table involves placing the data in the
corresponding location within the array. If a collision occurs (i.e. if two
different keys map to the same index), the hash table may use a
technique called chaining to store both keys in the same index. In
chaining, a linked list is created for each index, and the keys are added
to the linked list.

Hashing in C can be implemented using several different methods,

including the division method, multiplication method, and the folding
method. The division method involves taking the remainder of the key
divided by the size of the hash table to determine the index. The
multiplication method involves multiplying the key by a constant value
and then taking the fractional part of the result to determine the index.
The folding method involves breaking the key into several parts,
adding them together, and then using the result to determine the
index.

with minimum operations of given type

DSA to Development
Course

Hash Functions and list/types of Hash functions

Hashing is the process of generating a value from a text or a list of numbers

using a mathematical function known as a hash function.

A Hash Function is a function that converts a given numeric or alphanumeric key

to a small practical integer value. The mapped integer value is used as an index
in the hash table. In simple terms, a hash function maps a significant number or
string to a small integer that can be used as the index in the hash table.

The pair is of the form (key, value), where for a given key, one can find a value
using some kind of a “function” that maps keys to values. The key for a given
object can be calculated using a function called a hash function. For example,
given an array A, if i is the key, then we can find the value by simply looking up
A[i].

Types of Hash functions

There are many hash functions that use numeric or alphanumeric keys. This
article focuses on discussing different hash functions:
 1. Division Method.
2. Mid Square Method.
3. Folding Method.
4. Multiplication Method.

Let’s begin discussing these methods in detail.

1. Division Method:

This is the most simple and easiest method to generate a hash value. The hash
function divides the value k by M and then uses the remainder obtained.

Formula: h(K) = k mod M

Here,
k is the key value, and
M is the size of the hash table.

It is best suited that M is a prime number as that can make sure the keys are
more uniformly distributed. The hash function is dependent upon the remainder
of a division.

Example:

k = 12345
M = 95
h(12345) = 12345 mod 95
= 90
k = 1276
M = 11
h(1276) = 1276 mod 11
=0

Pros:

1. This method is quite good for any value of M.

2. The division method is very fast since it requires only a single division
operation.

Cons:

1. This method leads to poor performance since consecutive keys map to

consecutive hash values in the hash table.
2. Sometimes extra care should be taken to choose the value of M.

2. Mid Square Method:

The mid-square method is a very good hashing method. It involves two steps to
compute the hash value-

1. Square the value of the key k i.e. k2

2. Extract the middle r digits as the hash value.

Formula:

h(K) = h(k x k)
Here,
k is the key value.

The value of r can be decided based on the size of the table.

Example:

Suppose the hash table has 100 memory locations. So r = 2 because two digits
are required to map the key to the memory location.

k = 60
k x k = 60 x 60
= 3600
h(60) = 60

The hash value obtained is 60

Pros:

1. The performance of this method is good as most or all digits of the key
value contribute to the result. This is because all digits in the key
contribute to generating the middle digits of the squared result.
2. The result is not dominated by the distribution of the top digit or bottom
digit of the original key value.

Cons:

1. The size of the key is one of the limitations of this method, as the key is
of big size then its square will double the number of digits.
 2. Another disadvantage is that there will be collisions but we can try to
reduce collisions.

3. Digit Folding Method:

This method involves two steps:

1. Divide the key-value k into a number of parts i.e. k1, k2, k3,….,kn, where
each part has the same number of digits except for the last part that
can have lesser digits than the other parts.
2. Add the individual parts. The hash value is obtained by ignoring the last
carry if any.

Formula:

k = k1, k2, k3, k4, ….., kn

s = k1+ k2 + k3 + k4 +….+ kn
h(K)= s

Here,
s is obtained by adding the parts of the key k

Example:

k = 12345
k1 = 12, k2 = 34, k3 = 5
s = k1 + k2 + k3
= 12 + 34 + 5
 = 51
h(K) = 51

Note:
The number of digits in each part varies depending upon the size of the hash
table. Suppose for example the size of the hash table is 100, then each part must
have two digits except for the last part which can have a lesser number of digits.

4. Multiplication Method

This method involves the following steps:

1. Choose a constant value A such that 0 < A < 1.

2. Multiply the key value with A.
3. Extract the fractional part of kA.
4. Multiply the result of the above step by the size of the hash table i.e. M.
5. The resulting hash value is obtained by taking the floor of the result
obtained in step 4.

Formula: h(K) = floor (M (kA mod 1))

Here,
M is the size of the hash table.
k is the key value.
A is a constant value.

Example:
k = 12345
A = 0.357840
M = 100

h(12345) = floor[ 100 (12345*0.357840 mod 1)]

= floor[ 100 (4417.5348 mod 1) ]
= floor[ 100 (0.5348) ]
= floor[ 53.48 ]
= 53

Pros: The advantage of the multiplication method is that it can work with any
value between 0 and 1, although there are some values that tend to give better
results than the rest.

Cons: The multiplication method is generally suitable when the table size is the
power of two, then the whole process of computing the index by the key using
multiplication hashing is very fast.

Commonly used hash functions:

Hash functions are widely used in computer science and cryptography for a
variety of purposes, including data integrity, digital signatures, password storage,
and more.

There are many types of hash functions, each with its own strengths and
weaknesses. Here are a few of the most common types:
1. SHA (Secure Hash Algorithm): SHA is a family of cryptographic hash
functions designed by the National Security Agency (NSA) in the United States.
The most widely used SHA algorithms are SHA-1, SHA-2, and SHA-3. Here’s a
brief overview of each:

● SHA-1: SHA-1 is a 160-bit hash function that was widely used for digital
signatures and other applications. However, it is no longer considered
secure due to known vulnerabilities.
● SHA-2: SHA-2 is a family of hash functions that includes SHA-224, SHA-
256, SHA-384, and SHA-512. These functions produce hash values of
224, 256, 384, and 512 bits, respectively. SHA-2 is widely used in
security protocols such as SSL/TLS and is considered secure.
● SHA-3: SHA-3 is the latest member of the SHA family and was selected
as the winner of the NIST hash function competition in 2012. It is
designed to be faster and more secure than SHA-2 and produces hash
values of 224, 256, 384, and 512 bits.

2. CRC (Cyclic Redundancy Check): CRC is a non-cryptographic hash function

used primarily for error detection in data transmission. It is fast and efficient but
is not suitable for security purposes. The basic idea behind CRC is to append a
fixed-length check value, or checksum, to the end of a message. This checksum
is calculated based on the contents of the message using a mathematical
algorithm, and is then transmitted along with the message.

When the message is received, the receiver can recalculate the checksum using
the same algorithm, and compare it with the checksum transmitted with the
message. If the two checksums match, the receiver can be reasonably certain
that the message was not corrupted during transmission.
The specific algorithm used for CRC depends on the application and the desired
level of error detection. Some common CRC algorithms include CRC-16, CRC-32,
and CRC-CCITT.

3. MurmurHash: MurmurHash is a fast and efficient non-cryptographic hash

function designed for use in hash tables and other data structures. It is not
suitable for security purposes as it is vulnerable to collision attacks.

4. BLAKE2: BLAKE2 is a cryptographic hash function designed to be fast and

secure. It is an improvement over the popular SHA-3 algorithm and is widely used
in applications that require high-speed hashing, such as cryptocurrency mining.

BLAKE2 is available in two versions: BLAKE2b and BLAKE2s. BLAKE2b is

optimized for 64-bit platforms and produces hash values of up to 512 bits, while
BLAKE2s is optimized for 8- to 32-bit platforms and produces hash values of up
to 256 bits.

5. Argon2: Argon2 is a memory-hard password hashing function designed to be

resistant to brute-force attacks. It is widely used for password storage and is
recommended by the Password Hashing Competition. The main goal of Argon2
is to make it difficult for attackers to crack passwords by using techniques such
as brute force attacks or dictionary attacks. It achieves this by using a
computationally-intensive algorithm that makes it difficult for attackers to
perform large numbers of password guesses in a short amount of time.

Argon2 has several key features that make it a strong choice for password
hashing and key derivation:

● Resistance to parallel attacks: Argon2 is designed to be resistant to

parallel attacks, meaning that it is difficult for attackers to use multiple
 processing units, such as GPUs or ASICs, to speed up password
cracking.
● Memory-hardness: Argon2 is designed to be memory-hard, meaning
that it requires a large amount of memory to compute the hash
function. This makes it more difficult for attackers to use specialized
hardware to crack passwords.
● Customizable: Argon2 is highly customizable, and allows users to
adjust parameters such as the memory usage, the number of iterations,
and the output length to meet their specific security requirements.

Resistance to side-channel attacks: Argon2 is designed to be resistant to side-

channel attacks, such as timing attacks or power analysis attacks, that could be
used to extract information about the password being hashed.

6. MD5 (Message Digest 5): MD5 is a widely-used cryptographic hash function

that produces a 128-bit hash value. It is fast and efficient but is no longer
recommended for security purposes due to known vulnerabilities. The basic idea
behind MD5 is to take an input message of any length, and produce a fixed-
length output, known as the hash value or message digest. This hash value is
unique to the input message, and is generated using a mathematical algorithm
that involves a series of logical operations, such as bitwise operations, modular
arithmetic, and logical functions.

MD5 is widely used in a variety of applications, including digital signatures,

password storage, and data integrity checks. However, it has been shown to have
weaknesses that make it vulnerable to attacks. In particular, it is possible to
generate two different messages with the same MD5 hash value, a vulnerability
known as a collision attack.
There are many other types of hash functions, each with its own unique features
and applications. The choice of hash function depends on the specific
requirements of the application, such as speed, security, and memory usage.

Implementation of a hash table in C using arrays:

1. #include<stdio.h>
2. #define size 7
3. int array[size];
4. void init()
5. {
6. int i;
7. for(i = 0; i < size; i++)
8. array[i] = -1;
9. }
10.
11. void insert(int val)
12. {
13. int key = val % size;
14.
15. if(array[key] == -1)
16. {
17. array[key] = val;
18. printf("%d inserted at array[%d]\n", val,key);
19. }
20. else
21. {
22. printf("Collision : array[%d] has element %d already!\
n",key,array[key]);
23. printf("Unable to insert %d\n",val);
24. }
25. }
26.
27. void del(int val)
28. {
29. int key = val % size;
30. if(array[key] == val)
31. array[key] = -1;
32. else
33. printf("%d not present in the hash table\n",val);
34. }
35.
36. void search(int val)
37. {
38. int key = val % size;
39. if(array[key] == val)
40. printf("Search Found\n");
41. else
42. printf("Search Not Found\n");
43. }
44.
45. void print()
46. {
47. int i;
48. for(i = 0; i < size; i++)
49. printf("array[%d] = %d\n",i,array[i]);
50. }
51.
52. int main()
53. {
54. init();
55. insert(10);
56. insert(4);
57. insert(2);
58. insert(3);
59.
60. printf("Hash table\n");
61. print();
62. printf("\n");
63.
64. printf("Deleting value 10..\n");
65. del(10);
66. printf("After the deletion hash table\n");
67. print();
68. printf("\n");
 69.
70. printf("Deleting value 5..\n");
71. del(5);
72. printf("After the deletion hash table\n");
73. print();
74. printf("\n");
75.
76. printf("Searching value 4..\n");
77. search(4);
78. printf("Searching value 10..\n");
79. search(10);
80.
81. return 0;
82. }

Output

10 inserted at array[3]
4 inserted at array[4]
2 inserted at array[2]
Collision : array[3] has element 10 already!
Unable to insert 3
Hash table
array[0] = -1
array[1] = -1
array[2] = 2
array[3] = 10
array[4] = 4
array[5] = -1
array[6] = -1

Deleting value 10..

After the deletion hash table
array[0] = -1
array[1] = -1
array[2] = 2
array[3] = -1
array[4] = 4
array[5] = -1
array[6] = -1

Deleting value 5..

5 not present in the hash table
After the deletion hash table
array[0] = -1
array[1] = -1
array[2] = 2
array[3] = -1
array[4] = 4
array[5] = -1
array[6] = -1

Searching value 4..

Search Found
Searching value 10..
Search Not Found

Hashing is a technique used in computer programming to quickly search and retrieve

data from large datasets. In C programming, hashing is often used to implement hash
tables or associative arrays. Here are some usage, advantages, and disadvantages of
hashing in C:

Need for Hash data structure

The amount of data on the internet is growing exponentially every day,

making it difficult to store it all effectively. In day-to-day programming,
this amount of data might not be that big, but still, it needs to be
stored, accessed, and processed easily and efficiently. A very common
data structure that is used for such a purpose is the Array data
structure.
Now the question arises if Array was already there, what was the need
for a new data structure! The answer to this is in the word “efficiency“.
Though storing in Array takes O(1) time, searching in it takes at least
O(log n) time. This time appears to be small, but for a large data set,
it can cause a lot of problems and this, in turn, makes the Array data
structure inefficient.

So now we are looking for a data structure that can store the data and
search in it in constant time, i.e. in O(1) time. This is how Hashing data
structure came into play. With the introduction of the Hash data
structure, it is now possible to easily store data in constant time and
retrieve them in constant time as well.

Components of Hashing

There are majorly three components of hashing:

1. Key: A Key can be anything string or integer which is fed as

input in the hash function the technique that determines an
index or location for storage of an item in a data structure.
2. Hash Function: The hash function receives the input key
and returns the index of an element in an array called a hash
table. The index is known as the hash index.
3. Hash Table: Hash table is a data structure that maps keys to
values using a special function called a hash function. Hash
stores the data in an associative manner in an array where
each data value has its own unique index.
What is Collision?

The hashing process generates a small number for a big key, so there
is a possibility that two keys could produce the same value. The
situation where the newly inserted key maps to an already occupied,
and it must be handled using some collision handling technology.
 Collision in Hashing

Advantages of Hashing in Data Structures

● Key-value support: Hashing is ideal for implementing key-

value data structures.
● Fast data retrieval: Hashing allows for quick access to
elements with constant-time complexity.
● Efficiency: Insertion, deletion, and searching operations are
highly efficient.
● Memory usage reduction: Hashing requires less memory as
it allocates a fixed space for storing elements.
● Scalability: Hashing performs well with large data sets,
maintaining constant access time.
 ● Security and encryption: Hashing is essential for secure
data storage and integrity verification.

For maximum practice, here's a set of 20 multiple-choice questions

and 10 theory questions based on the topic "Searching and Sorting
Methods" in data structures:

*Multiple Choice Questions:*

1. Which of the following searching algorithms has the best time

complexity for searching in a sorted array?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

2. What is the worst-case time complexity of the binary search

algorithm?
 a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

3. Which sorting algorithm is known for its best-case time complexity

of O(n)?

a) Bubble Sort

b) Selection Sort

c) Quick Sort

d) Insertion Sort

4. In quicksort, which element is chosen as the pivot in the partition

process?

a) First element

b) Last element
 c) Random element

d) Median of three elements

5. Which of the following sorting algorithms is not an in-place sorting

algorithm?

a) Insertion Sort

b) Quick Sort

c) Merge Sort

d) Heap Sort

6. Which of the following is a stable sorting algorithm?

a) Quick Sort

b) Merge Sort

c) Selection Sort

d) Heap Sort
7. Which sorting algorithm has the best time complexity in the worst-
case scenario?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Insertion Sort

8. The time complexity of the worst-case scenario for bubble sort is:

a) O(n)

b) O(n log n)

c) O(n^2)

d) O(log n)

9. Which of the following is not a comparison-based sorting algorithm?

a) Bubble Sort

b) Radix Sort
 c) Quick Sort

d) Merge Sort

10. Which sorting algorithm is based on the divide-and-conquer

strategy?

a) Bubble Sort

b) Selection Sort

c) Merge Sort

d) Insertion Sort

11. What is the primary advantage of the merge sort algorithm over
the quick sort algorithm?

a) Merge sort is faster in most cases.

b) Merge sort has better worst-case time complexity.

c) Merge sort is an in-place sorting algorithm.

d) Merge sort requires less additional memory.

12. Which searching algorithm requires the data to be in sorted order?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

13. Which sorting algorithm has the best time complexity for sorting
linked lists?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Insertion Sort

14. In the selection sort algorithm, how many times do we select the
minimum element in each iteration?
 a) Once

b) Twice

c) Thrice

d) It varies

15. Which of the following sorting algorithms is not suitable for large
datasets due to its poor performance?

a) Merge Sort

b) Quick Sort

c) Bubble Sort

d) Insertion Sort

16. What is the primary drawback of the bubble sort algorithm?

a) Poor performance on large datasets

b) Unstable sorting

c) Requires additional memory

 d) None of the above

17. Which sorting algorithm is also known as the partition-exchange

sort?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Insertion Sort

18. What is the main advantage of using the insertion sort algorithm
for small datasets?

a) It is stable.

b) It has a better worst-case time complexity.

c) It is easy to implement.

d) It requires less memory.

19. Which sorting algorithm performs sorting by repeatedly stepping
through the list, comparing each pair of adjacent items, and swapping
them if they are in the wrong order?

a) Merge Sort

b) Quick Sort

c) Selection Sort

d) Insertion Sort

20. Which searching algorithm is used to find the position of an

element in a sorted array by estimating where in the data structure the
element could be located based on the value of the search key?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

21. What is the time complexity of linear search?

 a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

22. Which of the following is not a searching technique?

a) Binary Search

b) Quick Sort

c) Linear Search

d) Depth First Search

23. Which sorting algorithm has the best time complexity in the
average case?

a) Bubble Sort

b) Quick Sort

c) Merge Sort
 d) Selection Sort

24. In which sorting algorithm does the largest element "bubble up" to
its correct position in each pass?

a) Bubble Sort

b) Insertion Sort

c) Selection Sort

d) Quick Sort

25. Which of the following data structures is not suitable for binary
search?

a) Array

b) Linked List

c) Binary Search Tree

d) Heap
26. What is the worst-case time complexity of the merge sort
algorithm?

a) O(n)

b) O(n log n)

c) O(n^2)

d) O(log n)

27. Which sorting algorithm works by repeatedly selecting the smallest

(or largest) element from the unsorted portion and moving it to the
sorted portion?

a) Bubble Sort

b) Quick Sort

c) Merge Sort

d) Selection Sort

28. Which of the following is an advantage of using the binary search

algorithm over linear search?
 a) Binary search works on unsorted arrays.

b) Binary search has a better worst-case time complexity.

c) Binary search requires less memory.

d) Binary search is easier to implement.

29. What is the primary advantage of using the insertion sort

algorithm?

a) It is stable.

b) It has a better worst-case time complexity.

c) It is easy to implement.

d) It requires less memory.

30. Which sorting algorithm is also known as the partition-exchange

sort?

a) Quick Sort

b) Merge Sort
 c) Bubble Sort

d) Insertion Sort

31. Which searching algorithm requires the data to be in sorted order?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

32. What is the time complexity of quick sort in the worst-case

scenario?

a) O(n)

b) O(log n)

c) O(n^2)

d) O(n log n)
33. Which of the following is a characteristic of a binary search tree?

a) It has duplicate elements.

b) It does not allow deletion.

c) It can have at most two children for each node.

d) It has a linear structure.

34. Which of the following sorting algorithms is based on the divide-

and-conquer strategy?

a) Bubble Sort

b) Selection Sort

c) Merge Sort

d) Insertion Sort

35. What is the worst-case time complexity of the selection sort

algorithm?

a) O(1)
 b) O(log n)

c) O(n)

d) O(n^2)

36. In quicksort, which element is chosen as the pivot in the partition

process?

a) First element

b) Last element

c) Random element

d) Middle element

37. Which sorting algorithm has the best time complexity for sorting
linked lists?

a) Quick Sort

b) Merge Sort

c) Bubble Sort
 d) Insertion Sort

38. What is the main advantage of using the merge sort algorithm over
other sorting algorithms?

a) It has a better worst-case time complexity.

b) It is an in-place sorting algorithm.

c) It is stable.

d) It is easy to implement.

39. What is the primary drawback of the bubble sort algorithm?

a) Poor performance on large datasets

b) Unstable sorting

c) Requires additional memory

d) None of the above

40. Which sorting algorithm is not comparison-based?

 a) Merge Sort

b) Quick Sort

c) Radix Sort

d) Selection Sort

41. What is the primary advantage of using the binary search tree over
other data structures for searching?

a) It has a faster average-case time complexity.

b) It requires less memory.

c) It guarantees constant-time searching.

d) It maintains sorted order.

42. Which searching algorithm is used to find the position of an

element in a sorted array by estimating where in the data structure the
element could be located based on the value of the search key?

a) Linear Search

b) Binary Search
 c) Interpolation Search

d) Jump Search

43. Which sorting algorithm is based on the concept of exchanging

elements to arrange them in the correct order?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Insertion Sort

44. What is the primary disadvantage of using the quick sort

algorithm?

a) It is not stable.

b) It has a poor average-case time complexity.

c) It requires additional memory.

d) It is not suitable for large datasets.

45. Which searching algorithm is most suitable for searching in a large
database?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

46. Which sorting algorithm works by repeatedly stepping through the

list, comparing each pair of adjacent items, and swapping them if they
are in the wrong order?

a) Merge Sort

b) Quick Sort

c) Selection Sort

d) Insertion Sort

47. What is the primary advantage of using the heap sort algorithm?
 a) It has a better average-case time complexity.

b) It is an in-place sorting algorithm.

c) It has a stable sorting property.

d) It has a constant-time complexity.

48. Which searching algorithm works by dividing the array into blocks
of fixed size and then searching for the desired element in the
appropriate block?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

49. Which of the following sorting algorithms is not a comparison-

based sorting algorithm?

a) Bubble Sort

b) Radix Sort
 c) Quick Sort

d) Merge Sort

50. Which sorting algorithm is known for its best-case time complexity
of O(n)?

a) Bubble Sort

b) Selection Sort

c) Quick Sort

d) Insertion Sort

51. What is the primary advantage of using the radix sort algorithm?

a) It has a better worst-case time complexity.

b) It is an in-place sorting algorithm.

c) It is stable.

d) It does not require comparison of elements.

52. Which of the following is a characteristic of the shell sort
algorithm?

a) It is an in-place sorting algorithm.

b) It has a worst-case time complexity of O(n^2).

c) It is based on the divide-and-conquer strategy.

d) It uses a sequence of gap values to sort elements.

53. What is the time complexity of linear search when the element is
not present in the array?

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

54. Which sorting algorithm is known for its stability and is often used
as a subroutine in other sorting algorithms?

a) Quick Sort
 b) Merge Sort

c) Bubble Sort

d) Selection Sort

55. What is the primary advantage of using the counting sort

algorithm?

a) It has a better worst-case time complexity.

b) It is stable.

c) It is an in-place sorting algorithm.

d) It does not require comparison of elements.

56. In quicksort, what is the role of the partitioning process?

a) To merge subarrays into a sorted array

b) To select a pivot element

c) To exchange elements to arrange them in the correct order

d) To divide the array into smaller subarrays

57. Which sorting algorithm works by repeatedly dividing the array into
two halves and then merging them in sorted order?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Selection Sort

58. What is the main disadvantage of using the bubble sort algorithm?

a) It is not stable.

b) It has a poor average-case time complexity.

c) It requires additional memory.

d) It has a worst-case time complexity of O(n^2).

59. Which of the following is a characteristic of the radix sort

algorithm?
 a) It is an in-place sorting algorithm.

b) It has a worst-case time complexity of O(n^2).

c) It is stable.

d) It requires comparison of elements.

60. Which sorting algorithm is known for its simplicity and is often used
for educational purposes rather than practical applications?

a) Merge Sort

b) Quick Sort

c) Bubble Sort

d) Insertion Sort

61. What is the primary advantage of using the heap sort algorithm?

a) It has a better average-case time complexity.

b) It is an in-place sorting algorithm.

c) It has a stable sorting property.

 d) It has a constant-time complexity.

62. Which searching algorithm works by dividing the array into blocks
of fixed size and then searching for the desired element in the
appropriate block?

a) Linear Search

b) Binary Search

c) Interpolation Search

d) Jump Search

63. Which of the following is a characteristic of the shell sort

algorithm?

a) It is an in-place sorting algorithm.

b) It has a worst-case time complexity of O(n^2).

c) It is based on the divide-and-conquer strategy.

d) It uses a sequence of gap values to sort elements.

64. What is the time complexity of linear search when the element is
not present in the array?

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

65. Which sorting algorithm is known for its stability and is often used
as a subroutine in other sorting algorithms?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Selection Sort

66. What is the primary advantage of using the counting sort

algorithm?

a) It has a better worst-case time complexity.

 b) It is stable.

c) It is an in-place sorting algorithm.

d) It does not require comparison of elements.

67. In quicksort, what is the role of the partitioning process?

a) To merge subarrays into a sorted array

b) To select a pivot element

c) To exchange elements to arrange them in the correct order

d) To divide the array into smaller subarrays

68. Which sorting algorithm works by repeatedly dividing the array into
two halves and then merging them in sorted order?

a) Quick Sort

b) Merge Sort

c) Bubble Sort

d) Selection Sort
69. What is the main disadvantage of using the bubble sort algorithm?

a) It is not stable.

b) It has a poor average-case time complexity.

c) It requires additional memory.

d) It has a worst-case time complexity of O(n^2).

70. Which of the following is a characteristic of the radix sort

algorithm?

a) It is an in-place sorting algorithm.

b) It has a worst-case time complexity of O(n^2).

c) It is stable.

d) It requires comparison of elements.

*Theory questions:*
1. Explain the working principle of the binary search algorithm.

2. Discuss the divide-and-conquer strategy and how it is applied in

sorting algorithms like merge sort and quick sort.

3. Compare and contrast the time complexity of bubble sort and merge
sort.

4. Explain how the selection sort algorithm works and analyze its time
complexity.

5. Discuss the advantages and disadvantages of using quick sort over

merge sort.

6. What is stability in sorting algorithms? Provide an example of a

stable and unstable sorting algorithm.

7. Describe the process of partitioning in the quick sort algorithm.

8. Explain the concept of in-place sorting and provide examples of in-

place and non-in-place sorting algorithms.

9. Discuss the applications of sorting algorithms in real-world

scenarios.

10. How does the performance of binary search differ from linear
search, especially on large datasets?

11. Explain the concept of recursion in programming with an example.

12. Discuss the importance of time and space complexity analysis in
algorithm design.

13. Describe the process of memory management in programming

languages.

14. Discuss the role of data structures in improving the efficiency of

algorithms.

15. Explain the concept of hashing and its applications in data storage
and retrieval.

16. Compare and contrast the time complexity of bubble sort and
merge sort.

17. Explain how the selection sort algorithm works and analyze its time
complexity.

18. Discuss the advantages and disadvantages of using quick sort over
merge sort.

19. What is stability in sorting algorithms? Provide an example of a

stable and unstable sorting algorithm.

20. Describe the process of partitioning in the quick sort algorithm.

21. Explain the concept of in-place sorting and provide examples of in-
place and non-in-place sorting algorithms.
22. Discuss the applications of sorting algorithms in real-world
scenarios.