Data Structures

BCA SEM-II
1
2. Searching and Sorting
Techniques
1 Linear Search 5 Insertion Sort

2 Iterative Binary Search 6 Selection Sort

3 Recursions & Recursive Binary 7 Quick Sort

Search
4 Bubble Sort 8 Merge Sort
2
Sorting Algorithm:
A sorting algorithm is a well-defined computational procedure that
rearranges the elements of a finite sequence or collection into a
specified order, typically in ascending or descending sequence,
according to a defined comparison criterion (such as numerical
value, lexicographic order, or key value).
Examples of sorting in real-life scenarios:
● Telephone Directory − The telephone directory stores the
telephone numbers of people sorted by their names, so that the
names can be searched easily.
● Dictionary − The dictionary stores words in an alphabetical
order so that searching of any word becomes easy. 3
Types Based on Space Used :
● Sorting algorithms may require some extra space for
comparison and temporary storage of few data elements.
● The algorithms which do not require any extra space and
sorting is said to happen in-place, or for example, within the
array itself. This is called in-place sorting. Bubble sort is an
example of in-place sorting.
● However, in some sorting algorithms, the program requires
space which is more than or equal to the elements being sorted.
● Sorting which uses equal or more space is called not-in-place
sorting . Merge-sort is an example of not-in-place sorting.
4
Types

5
Bubble Sort Algorithm:
● Bubble sort is a simple sorting algorithm. This sorting algorithm
is comparison-based algorithm in which each pair of adjacent
elements is compared and the elements are swapped if they
are not in order.
● We assume list is an array of n elements:
● Step 1 − Check if the first element in the input array is greater
than the next element in the array.
● Step 2 − If it is greater, swap the two elements; otherwise move
the pointer forward in the array.
● Step 3 − Repeat Step 2 until we reach the end of the array.
6
Bubble Sort Algorithm:
● Step 4 − Check if the elements are sorted; if not, repeat the
same process (Step 1 to Step 3) from the last element of the
array to the first.
● Step 5 − The final output achieved is the sorted array.
Example :

7
2. Insertion Sort Algorithm:
● Insertion sort is a simple method to sort numbers in an
ascending or descending order. This method follows the
incremental method.
● This is an in-place comparison-based sorting algorithm. Here, a
sub-list is maintained which is always sorted.
● For example, the lower part of an array is maintained to be
sorted. An element which is to be 'inserted' in this sorted
sub-list, has to find its appropriate place and then it has to be
inserted there. Hence the name, insertion sort.
● The array is searched sequentially and unsorted items are
moved and inserted into the sorted sub-list (in the same array).
8
2. Insertion Sort Algorithm:
● Step 1 − If it is the first element, it is already sorted. return 1;
● Step 2 − Pick next element
● Step 3 − Compare with all elements in the sorted sub-list
● Step 4 − Shift all the elements in the sorted sub-list that is
greater than the value to be sorted
● Step 5 − Insert the value
● Step 6 − Repeat until list is sorted
Example:

9
3. Selection Sort Algorithm:
● Selection sort is a simple sorting algorithm. This sorting
algorithm, like insertion sort, is an in-place comparison-based
algorithm in which the list is divided into two parts, the sorted
part at the left end and the unsorted part at the right end.
Initially, the sorted part is empty and the unsorted part is the
entire list.
● The smallest element is selected from the unsorted array and
swapped with the leftmost element, and that element becomes
a part of the sorted array. This process continues moving
unsorted array boundaries by one element to the right. 10
3. Selection Sort Algorithm:
● This type of sorting is called Selection Sort as it works by
repeatedly sorting elements. That is: we first find the smallest
value in the array and exchange it with the element in the first
position, then find the second smallest element and exchange it
with the element in the second position, and we continue the
process in this way until the entire array is sorted.
Example:

11
4. Quick Sort Algorithm:
● Quick sort is a highly efficient sorting algorithm and is based
on partitioning of array of data into smaller arrays.
● A large array is partitioned into two arrays one of which holds
values smaller than the specified value, say pivot, based on
which the partition is made and another array holds values
greater than the pivot value.
● Quicksort partitions an array and then calls itself recursively
twice to sort the two resulting subarrays.
● Example :
12
4. Quick Sort Algorithm:
There are mainly three steps in the algorithm:
1. Choose a Pivot: Select an element from the array as the pivot.
The choice of pivot can vary (e.g., first element, last element,
random element, or median).
2. Partition the Array: Re arrange the array around the pivot. After
partitioning, all elements smaller than the pivot will be on its
left, and all elements greater than the pivot will be on its right.
3. Recursively Call: Recursively apply the same process to the
two partitioned sub-arrays.
4. Base Case: The recursion stops when there is only one
element left in the sub-array, as a single element is already 13
5. Merge Sort Algorithm:
Merge sort is a popular sorting algorithm known for its efficiency and
stability. It follows the Divide and Conquer approach.
It works by recursively dividing the input array into two halves,
recursively sorting the two halves and finally merging them back
together to obtain the sorted array. Steps for Merge Sort:
1. Divide: Divide the list or array recursively into two halves until it
can no more be divided.
2. Conquer: Each subarray is sorted individually using the merge
sort algorithm.
14
5. Merge Sort Algorithm:
3. Merge: The sorted subarrays are merged back together in sorted
order. The process continues until all elements from both subarrays
have been merged.

15
Linear Search Algorithm:
● Linear search is a type of sequential searching algorithm. In this
method, every element within the input array is traversed and
compared with the key element to be found.
● If a match is found in the array the search is said to be successful;
if there is no match found the search is said to be unsuccessful
and gives the worst-case time complexity.
Step 1 − Start from the 0th index of the input array, compare the key
value with the value present in the 0th index.
Step 2 − If the value matches with the key, return the position at
which the value was found. 16
Linear Search Algorithm:
Step 3 − If the value does not match with the key, compare the next
element in the array.
Step 4 − Repeat Step 3 until there is a match found. Return the
position at which the match was found.
Step 5 − If it is an unsuccessful search, print that the element is not
present in the array and exit the program.
Example:

17
Binary Search Algorithm:
Binary Search is a search algorithm that is used to find the position of an
element (target value ) in a sorted array. The array should be sorted prior to
applying a binary search.

Working of Binary Search: The binary search algorithm works by

comparing the element to be searched by the middle element of the array
and based on this comparison follows the required procedure.

Case 1 : element = middle, the element is found return the index.

Case 2 : element > middle, search for the element in the sub-array starting
from middle+1 index to n.
Case 3 : element < middle, search for element in the sub-array starting from
0 index to middle -1. 18
Binary Search Algorithm:

19
Examples:

20
Examples:

21
Iterative Search Algorithm:
The iterative approach to binary search follows a loop-based structure,
continuously narrowing the search space until the target is found or the
search space is exhausted.
Algorithm Steps:
1. Initialize low = 0 and high = n - 1 (where n is the array size).
2. Run a loop while low <= high:
1. Compute mid = (low + high) / 2.
2. If arr[mid] == target, return mid.
3. If arr[mid] < target, search in the right half (low = mid + 1).
4. If arr[mid] > target, search in the left half (high = mid - 1).
3. If the loop ends and the element is not found, return -1. 22
Iterative Search Algorithm:

23
Recursive Search Algorithm:
The recursive method breaks the problem into smaller subproblems by
making repeated function calls until the base condition is met.
Algorithm Steps:
1. Base Case: If low > high, return -1 (element not found).
2. Compute mid = (low + high) / 2.
3. Compare arr[mid] with the target:
1. If arr[mid] == target, return mid.
2. If arr[mid] < target, recursively search in the right half (low = mid +
1).
3. If arr[mid] > target, recursively search in the left half (high = mid - 1).
24
Examples:

25
Examples:

26
Difference between Recursion
and Iteration:
A program is called recursive when an entity calls itself. A program is called
iterative when there is a loop (or repetition).
● Iteration means repeatedly executing a set of instructions using loops
like for, while, or do-while. It continues until a specified condition
becomes false.
● In recursion, a function calls itself to solve smaller parts of a given
problem. It continues until a base condition is met to stop further calls.

27