Searching and Sorting

● Searching and sorting are fundamental operations in computer Common Interview Questions:
science and are used in many applications that deal with large 1. Why do we have various algorithms for tasks like
amounts of data searching?
● Searching algorithms find a particular value or set of values in a 2. How does binary search work?
data structure while sorting algorithms arrange data in a specific 3. Share use cases of binary search.
order. 4. Why is linear search not generally preferred?
● There are many types of searching and sorting algorithms 5. In which cases will you use linear search over binary
available, each with its strengths and weaknesses. search?
● Algorithms can be compared on the basis of time & space 6. Explain time & space complexity.
complexities. 7. Python has a .sort() function; which algorithm does it
● Searching algorithms include linear search, binary search, and hash uses?
tables while sorting algorithms include bubble sort, insertion sort, 8. Explain some sorting algorithms
and quicksort. 9. When will you prefer quicksort over merge sort?
● By understanding the different types of searching and sorting 10. Explain the bubble sort algorithm.
algorithms available, developers can choose the best algorithm for 11. Which sorting algorithm will you use if you have to sort in
their specific use case and optimise it for maximum efficiency. O(logn) time?

Space and Time Complexity

● Space complexity refers to the amount of memory or storage
required by an algorithm to solve a problem. Nowadays, space is
no longer a big limitation & hence space complexity isn't used
much.
● Time complexity refers to the time it takes for an algorithm to solve
a problem.
● Both space and time complexity are typically measured in terms of
the size of the input data, or the number of elements that need to
be processed.
● Big O notation is used to represent space & time complexity
● It is important to consider not only the worst-case scenario but
also the average-case and best-case scenarios.
Comparison of algortthm with different time complexities
 Searching and Sorting
Searching
Searching algorithms in computer science are methods used to
locate specific data items within a data structure or a set of
data.

Linear Search
● Works by sequentially checking each element in a list or
array.
● Suitable for small datasets and unordered lists.
● Has a time complexity of O(n), where n is the size of the list.
● Simple to implement and understand.
● Can be inefficient for large datasets or when the target
element is near the end of the list.
● Does not require the list to be sorted.

Binary Search
● Works by repeatedly dividing the search interval in half. Sorting Algorithm
● Suitable for large datasets and ordered lists. Sorting algorithms are methods used to arrange a set of data
● Has a time complexity of O(log n), where n is the list size. in a particular order, such as ascending or descending.
● More complex to implement and understand than linear
search.
● Very efficient for large datasets and when the target There are many different types of sorting algorithms, each
element is near the middle of the list. with its strengths and weaknesses. Some of the most
● Requires the list to be sorted before searching. common sorting algorithms include:

A binary search is always better unless either of these Bubble sort:

● Number of elements is very less This algorithm works by repeatedly swapping adjacent
● The data isn't sorted. elements if they are in the wrong order. It is simple to
implement but can be slow for large datasets.
 Searching and Sorting
Insertion sort: Comparison
This algorithm inserts each element into its proper position in The choice of sorting algorithm depends on the specific use
a sorted list. It is efficient for small datasets but can be slow case and the characteristics of the data being sorted.
for larger ones. It is important to consider factors such as the size of the
dataset, the degree of data randomness, and the available
Selection sort: memory and processing power when choosing a sorting
This algorithm works by repeatedly finding the smallest algorithm.
element in a list and swapping it with the next unsorted
element. It is simple to implement but can be slow for large •Bubble sort and selection sort has a time complexity of O(n^2)
datasets. and are generally inefficient for large datasets.

Quick sort: •Insertion sort is faster for small datasets or nearly sorted data.
This algorithm works by dividing the dataset into two smaller
sub-arrays and recursively sorting each sub-array. It is •Quick sort and merge sort have a time complexity of O(n log n)
efficient for large datasets but slow for nearly sorted data. and are more efficient for large datasets. Quick sort is in-place,
while merge sort requires additional memory for merging.
Merge sort:
This algorithm works by recursively dividing the dataset into •Heap sort is faster than merge sort for small datasets or when
two halves, sorting each half, and then merging the two memory usage is a concern.
sorted halves together. It is efficient for large datasets but
requires additional memory for the merging step. •The choice of sorting algorithm depends on factors such as the
size of the dataset, the degree of data randomness, and the
Heap sort: available memory and processing power.
This algorithm works by creating a heap data structure and
repeatedly extracting the largest element until the heap is •It's important to consider the time complexity, space
empty. It is efficient for large datasets but can be slower than complexity, stability, and ease of implementation when
other algorithms for small datasets. choosing a sorting algorithm.
 Searching and Sorting
Sorting Algorithm Comparison
Here is the table with the best, worst & average time complexity of algorithms discussed previously.