Computational Thinking for

Structured Design-II(303105151)
Mrs. Praptiba Solanki
Computer Science & Engineering Department (PIT)
 CHAPTER-6
SEARCHING AND SORTING
 Contents
• Selectionsort
• BubbleSort
• Insertion sort
• Linear Searching Techniques
• Binary Searching Techniques

Source:- solar school

 What is Sorting?
• 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.
• Sorting means reordering of all the elements either in ascending or in
descending order.
 What is Sorting?
Types of Sorting
1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Quick Sort
5. Merge Sort
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.
• Let's consider the following array as an example: arr[] = {64, 25, 12,
22, 11}
Selection Sort

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 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.
Selection Sort
• Selection Sort Algorithm | Swapping 1st element with the minimum in
array
 Selection Sort
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.
• Selection Sort Algorithm | swapping i=1 with the next minimum element
 Selection Sort
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.
• Selection Sort Algorithm | swapping i=2 with the next minimum element

Source:- cofounders town

 Selection Sort
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.
• Selection Sort Algorithm | swapping i=3 with the next minimum element

Source:- Britannica
 Selection Sort
Fifth Pass:
• At last the largest value present in the array automatically get placed at the
last position in the array
• The resulted array is the sorted array.

Source:- Britannica
 Selection Sort
Advantages of Selection Sort Algorithm
• Simple and easy to understand.
• Works well with small datasets
Disadvantages of the Selection Sort Algorithm
• Selection sort has a time complexity of O(n^2) in the worst and average
case.
• Does not work well on large datasets.
• Does not preserve the relative order of items with equal keys which means
it is not stable.
Source:- Britannica
Bubble Sort
• Bubble Sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in the wrong order.
• This algorithm is not suitable for large data sets as its average and worst-
case time complexity is quite high.
Bubble Sort
In Bubble Sort algorithm,
• traverse from left and compare adjacent elements and the higher one
is placed at right side.
• In this way, the largest element is moved to the rightmost end at first.
• This process is then continued to find the second largest and place it
and so on until the data is sorted.
Bubble Sort
• How does Bubble Sort Work?
• Let us understand the working of bubble sort with the help of the
following illustration: Input: arr[] = {6, 0, 3, 5}

First Pass:

The largest element is placed in its correct position, i.e., the end of the
array.
Bubble Sort Algorithm : Placing the largest element at correct position

Source:- medium
Bubble Sort

Source:- medium
Bubble Sort

Second Pass:
• Place the second largest element at correct position
• Bubble Sort Algorithm : Placing the second largest element at correct
position
Bubble Sort
 Bubble Sort
Third Pass:
• Place the remaining two elements at their correct positions.
• Bubble Sort Algorithm : Placing the remaining elements at their correct Positions

• Total no. of passes: n-1

• Total no. of comparisons: n*(n-1)/2
Bubble Sort
 Bubble Sort
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.
 Bubble Sort
Disadvantages of Bubble Sort:
• Bubble sort has a time complexity of O(N2) which makes it very slow for large data
sets.
• Bubble sort is a comparison-based sorting algorithm, which means that it requires
a comparison operator to determine the relative order of elements in the input
data set. It can limit the efficiency of the algorithm in certain cases.
Insertion Sort
• Insertion sort is a simple sorting algorithm that works by iteratively
inserting each element of an unsorted list into its correct position in a
sorted portion of the list.
• It is a stable sorting algorithm, meaning that elements with equal
values maintain their relative order in the sorted output.
• Insertion sort is like sorting playing cards in your hands.
• You split the cards into two groups: the sorted cards and the unsorted
cards.
• Then, you pick a card from the unsorted group and put it in the right
place in the sorted group.
 Insertion Sort
Working of Insertion Sort Algorithm: Consider an array having elements: {23, 1, 10,
5, 2}
 Insertion Sort
First Pass:
• Current element is 23
• The first element in the array is assumed to be sorted.
• The sorted part until 0th index is : [23]

Second Pass:
• Compare 1 with 23 (current element with the sorted part).
• Since 1 is smaller, insert 1 before 23.
• The sorted part until 1st index is: [1, 23]
Insertion Sort
Third Pass:
• Compare 10 with 1 and 23 (current element with the sorted part).
• Since 10 is greater than 1 and smaller than 23, insert 10 between 1 and
23.
• The sorted part until 2nd index is: [1, 10, 23]

Fourth Pass:
• Compare 5 with 1, 10, and 23 (current element with the sorted part).
• Since 5 is greater than 1 and smaller than 10, insert 5 between 1 and
10.
• The sorted part until 3rd index is: [1, 5, 10, 23]
Insertion Sort
Fifth Pass:
• Compare 2 with 1, 5, 10, and 23 (current element with the sorted part).
• Since 2 is smaller than all elements in the sorted part, insert 2 at the
• beginning.
• The sorted part until 4th index is: [2, 1, 5, 10, 23]

Final Array:
• The sorted array is: [2, 1, 5, 10, 23]
Insertion Sort
Advantages of Insertion Sort:
• Simple and easy to implement.
• Stable sorting algorithm.
• Efficient for small lists and nearly sorted lists.
• Space-efficient.

Disadvantages of Insertion Sort:

• Inefficient for large lists.
• Not as efficient as other sorting algorithms (e.g., merge sort, quick sort)
for most cases.
 Insertion Sort

Applications of Insertion Sort:

Insertion sort is commonly used in situations where:

• The list is small or nearly sorted.
• Simplicity and stability are important.
Searching algorithm
• Searching algorithms are essential tools in computer science used to
locate specific items within a collection of data.
• These algorithms are designed to efficiently navigate through data
structures to find the desired information, making them fundamental in
various applications such as databases, web search engines , and more.
Searching algorithm
Searching terminologies:
• Target Element: In searching, there is always a specific target element or
item that you want to find within the data collection. This target could be
a value, a record, a key, or any other data entity of interest.
Linear Search
• Linear Search is defined as a sequential search algorithm that starts at
one end and goes through each element of a list until the desired
element is found, otherwise the search continues till the end of the data
set. Time Complexy is O(n).
Linear Search
How Does Linear Search Algorithm Work?

In Linear Search Algorithm,

• Every element is considered as a potential match for the key and
checked for the same.
• If any element is found equal to the key, the search is successful and
the index of that element is returned.
• If no element is found equal to the key, the search yields “No match
found”.
 Linear Search
For example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and
key = 30

Step 1:
• Start from the first element (index 0) and compare key with each
element (arr[i]).
• Comparing key with first element arr[0]. SInce not equal, the iterator
moves to the next element as a potential match.
Linear Search
Comparing key with next element arr[1]. SInce not equal, the iterator
moves to the next element as a potential match.
Linear Search
Step 2:
Now when comparing arr[2] with key, the value matches. So the Linear
Search Algorithm will yield a successful message and return the index of
the element when key is found (here 2).
Linear Search
Advantages of Linear Search:
• Linear search can be used irrespective of whether the array is sorted or
not.
• It can be used on arrays of any data type.
• Does not require any additional memory.
• It is a well-suited algorithm for small datasets.

Drawbacks of Linear Search:

• Linear search has a time complexity of O(N), which in turn makes it slow
for
• large datasets.
• Not suitable for large arrays.
Linear Search
When to use Linear Search?
• When we are dealing with a small dataset.
• When you are searching for a dataset stored in contiguous memory.
Binary Search
• Binary Search is defined as a searching algorithm used in a sorted array
by repeatedly dividing the search interval in half .
• The idea of binary search is to use the information that the array is
sorted and reduce the time complexity to O(log N).

Conditions for when to apply Binary Search in a Data Structure:

• To apply Binary Search algorithm:
• The data structure must be sorted. Access to any element of the data
structure takes constant time.
Binary Search
• How does Binary Search work? To understand the working of binary
search, consider the following illustration:

• Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the
target = 23.
Binary Search
First Step:
• Calculate the mid and compare the mid element with the key. If the key
is less than mid element, move to left and if it is greater than the mid
then move search space to the right.
• Key (i.e., 23) is greater than current mid element (i.e., 16). The search
space moves to the right.
Binary Search
Key is less than the current mid 56. The search space moves to the left.
Binary Search
Second Step:
• If the key matches the value of the mid element, the element is found
and stop search.
Binary Search
How to Implement Binary Search?

The Binary Search Algorithm can be implemented in the following two ways
1. Iterative Binary Search Algorithm
2. Recursive Binary Search Algorithm

Applications of Binary Search:

• Binary search can be used as a building block for more complex
algorithms used in machine learning, such as algorithms for training
neural networks or finding the optimal hyperparameters for a model.
• It can be used for searching in computer graphics such as algorithms for
ray tracing or texture mapping.
• It can be used for searching a database.
Binary Search
Advantages of Binary Search:
• Binary search is faster than linear search, especially for large arrays.
• More efficient than other searching algorithms with a similar time
complexity, such as interpolation search or exponential search.
• Binary search is well-suited for searching large datasets that are stored
in external memory, such as on a hard drive or in the cloud.

Drawbacks of Binary Search:

• The array should be sorted.
• Binary search requires that the data structure being searched be stored
in contiguous memory locations.
• Binary search requires that the elements of the array be comparable,
meaning that they must be able to be ordered
www.paruluniversity.ac.in