Subject: Data Structure and Algorithms

SORTING AND SEARCHING

by
Dr. Swapnil Gundewar
DEPARTMENT OF AIDS/AIML/CSD/CSME/CSE

FACULTY OF ENGINEERING
 Course outcomes
Topic CO
Introduction to Sorting and Searching 1
Insertion Sort 2
Quick Sort, Merge Sort 3
Heap Sort 3
Sorting on several keys 3
List and Table sort 3
Comparison of sorting algorithms 4
 SPECIFIC LEARNING OBJECTIVES

S/No Learning objectives Level

1 Understand the basic concepts of sorting and searching. Must know

2 Learn the types of sorting and searching Must know

3 Understand various applications of sorting and searching Must know

 Searching Algorithms
• Search is a process of finding a value in a list of values. In other words, searching is the process of
locating given value position in a list of values.
• Searching is the fundamental process of locating a specific element or item within a collection of
data.
• This collection of data can take various forms, such as arrays, lists, trees, or other structured
representations.
• The primary objective of searching is to determine whether the desired element exists within the
data, and if so, to identify its precise location or retrieve it.
 Searching terminologies:
1. 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.
2. Search Space:
The search space refers to the entire collection of data within which you are looking for
the target element. Depending on the data structure used, the search space may vary in
size and organization.
3. Complexity:
Searching can have different levels of complexity depending on the data structure and the
algorithm used. The complexity is often measured in terms of time and space
requirements.
 Deterministic vs. Non-deterministic:

• Some searching algorithms, like binary search, are

deterministic, meaning they follow a clear, systematic
approach. Others, such as linear search, are non-deterministic,
as they may need to examine the entire search space in the
worst case.
 Applications of Searching:
• Information Retrieval: Search engines like Google, Bing, and Yahoo use sophisticated searching
algorithms to retrieve relevant information from vast amounts of data on the web.
• Database Systems: Searching is fundamental in database systems for retrieving specific data records
based on user queries, improving efficiency in data retrieval.
• E-commerce: Searching is crucial in e-commerce platforms for users to find products quickly based on
their preferences, specifications, or keywords.
• Artificial Intelligence: Searching algorithms play a vital role in AI applications, such as problem-
solving, game playing (e.g., chess), and decision-making processes
• Pattern Recognition: Searching algorithms are used in pattern matching tasks, such as image
recognition, speech recognition, and handwriting recognition.
 Linear Search Algorithm (Sequential Search Algorithm)

• Linear search algorithm finds a given element in a list of elements with O(n) time
complexity where n is total number of elements in the list.
• This search process starts comparing search element with the first element in the
list.
• If both are matched then result is element found otherwise search element is
compared with the next element in the list.
• Repeat the same until search element is compared with the last element in the list,
if that last element also doesn't match, then the result is "Element not found in the
list". That means, the search element is compared with element by element in the
list.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

# Example usage
arr = [3, 5, 2, 4, 9]
target = 4
result = linear_search(arr, target)

if result != -1:
print(f"Element found at index {result}")
else:
print("Element not found in the array")
 Binary Search Algorithm

• Binary search algorithm finds a given element in a list of elements with O(log n) time
complexity where n is total number of elements in the list.
• The binary search algorithm can be used with only a sorted list of elements. That
means the binary search is used only with a list of elements that are already
arranged in an order.
• The binary search can not be used for a list of elements arranged in random order.
• This search process starts comparing the search element with the middle element in
the list. If both are matched, then the result is "element found". Otherwise, we check
whether the search element is smaller or larger than the middle element in the list.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 4
result = binary_search(arr, target)

if result != -1:
print(f"Element found at index {result}")
else:
print("Element not found in the array")
 Sorting Algorithms

• 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.
• Stable sorting: When two same data appear in the same order in sorted data
without changing their position is called stable sort. Examples: Merge Sort, Insertion
Sort, Bubble Sort.
• Unstable sorting: When two same data appear in the different order in sorted data it
is called unstable sort. Examples: Quick Sort, Heap Sort, Shell Sort.
 Insertion Sort Algorithm
• Insertion sort algorithm arranges a list of elements in a particular order. In insertion
sort algorithm, every iteration moves an element from unsorted portion to sorted
portion until all the elements are sorted in the list.

Step by Step Process

• Step 1 - Assume that first element in the list is in sorted portion and all the remaining
elements are in unsorted portion.
• Step 2: Take first element from the unsorted portion and insert that element into the
sorted portion in the order specified.
• Step 3: Repeat the above process until all the elements from the unsorted portion
are moved into the sorted portion.
 Selection Sort Algorithm
• Selection Sort algorithm is used to arrange a list of elements in a particular order
(Ascending or Descending).
• In selection sort, the first element in the list is selected and it is compared
repeatedly with all the remaining elements in the list.
• If any element is smaller than the selected element (for Ascending order), then both
are swapped so that first position is filled with the smallest element in the sorted
order.
• Next, we select the element at a second position in the list and it is compared with
all the remaining elements in the list.
• If any element is smaller than the selected element, then both are swapped. This
procedure is repeated until the entire list is sorted.
 Step by Step Process

• Step 1 - Select the first element of the list (i.e., Element at first position in the list).

• Step 2: Compare the selected element with all the other elements in the list.

• Step 3: In every comparison, if any element is found smaller than the selected
element (for Ascending order), then both are swapped.

• Step 4: Repeat the same procedure with element in the next position in the list till
the entire list is sorted.
Sort the list in ascending order
 Radix Sort Algorithm

• Radix sort is one of the sorting algorithms used to sort a list of integer numbers in
order.
• In radix sort algorithm, a list of integer numbers will be sorted based on the digits of
individual numbers.
• Sorting is performed from least significant digit to the most significant digit.
• Radix sort algorithm requires the number of passes which are equal to the number
of digits present in the largest number among the list of numbers.
• For example, if the largest number is a 3 digit number then that list is sorted with 3
passes.
 Step by Step Process

• Step 1 - Define 10 queues each representing a bucket for each digit from 0 to 9.
• Step 2 - Consider the least significant digit of each number in the list which is to be
sorted.
• Step 3 - Insert each number into their respective queue based on the least significant
digit.
• Step 4 - Group all the numbers from queue 0 to queue 9 in the order they have
inserted into their respective queues.
• Step 5 - Repeat from step 3 based on the next least significant digit.
• Step 6 - Repeat from step 2 until all the numbers are grouped based on the most
significant digit.
 Merge Sort

• Merge sort is a sorting algorithm that follows the divide-and-conquer

approach.
• It works by recursively dividing the input array into smaller subarrays and
sorting those subarrays then merging them back together to obtain the
sorted array.
• In simple terms, we can say that the process of merge sort is to divide
the array into two halves, sort each half, and then merge the sorted
halves back together.
• This process is repeated until the entire array is sorted.
 Bubble Sort Algorithm

• 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.
 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.
Input: arr[] = {6, 0, 3, 5}

First Pass:
The largest element is placed in its correct position, i.e., the end of the array.
 Second Pass:

Place the second largest element at correct position

Third Pass:

Place the remaining two elements at their correct positions.

 Heap Data Structure

• A heap is a binary tree-based data structure that satisfies the heap property: the
value of each node is greater than or equal to the value of its children.
• This property makes sure that the root node contains the maximum or minimum
value (depending on the type of heap), and the values decrease or increase as you
move down the tree.
• Types of Heaps
• There are two main types of heaps:
• Max Heap: The root node contains the maximum value, and the values decrease as
you move down the tree.
• Min Heap: The root node contains the minimum value, and the values increase as
you move down the tree.
• Every heap data structure has the following properties...

• Property #1 (Ordering): Nodes must be arranged in an order according to their

values based on Max heap or Min heap.

• Property #2 (Structural): All levels in a heap must be full except the last level and all
nodes must be filled from left to right strictly.
 Max Heap

• Max heap is a specialized full binary tree in which every parent node contains greater
or equal value than its child nodes.
 Operations on Max Heap

• The following operations are performed on a Max heap data structure...

• Finding Maximum
• Insertion
• Deletion
 Finding Maximum Value Operation in Max Heap

• Finding the node which has maximum value in a max heap is very simple. In a max
heap, the root node has the maximum value than all other nodes. So, directly we can
display root node value as the maximum value in max heap.
 Insertion Operation in Max Heap

• Insertion Operation in max heap is performed as follows...

• Step 1 - Insert the newNode as last leaf from left to right.

• Step 2 - Compare newNode value with its Parent node.
• Step 3 - If newNode value is greater than its parent, then swap both of them.
• Step 4 - Repeat step 2 and step 3 until newNode value is less than its parent node
(or) newNode reaches to root.
Consider the below max heap. Insert a new node with value
85.
• Step 1 - Insert the new Node with value 85 as last leaf from left to right. That means
new Node is added as a right child of node with value 75. After adding max heap is as
follows...
Step 2 - Compare new Node value (85) with its Parent node
value (75). That means 85 > 75
Step 3 - Here new Node value (85) is greater than its parent
value (75), then swap both of them. After swapping, max heap
is as follows...
Step 4 - Now, again compare newNode value (85) with its
parent node value (89).
Here, new Node value (85) is smaller than its parent node value
(89). So, we stop insertion process. Finally, max heap after
insertion of a new node with value 85 is as follows...
 Deletion Operation in Max Heap

• Consider the below max heap. Delete root node (90) from the max heap.
Step 1 - Swap the root node (90) with last node 75 in max heap.
After swapping max heap is as follows...
Delete last node. Here the last node is 90. After deleting node
with value 90 from heap, max heap is as follows...
Step 3 - Compare root node (75) with its left child (89).
Step 4 - Here, left child value (89) is larger than its right sibling
(70), So, swap root (75) with left child (89).
Step 5 - Now, again compare 75 with its left child (36).
Here, node with value 75 is larger than its left child. So, we
compare node 75 with its right child 85.
Step 6 - Here, node with value 75 is smaller than its right child
(85). So, we swap both of them. After swapping max heap is as
follows...
Step 7 - Now, compare node with value 75 with its left child
(15).
Here, node with value 75 is larger than its left child (15) and it
does not have right child. So we stop the process.

Finally, max heap after deleting root node (90) is as follows...

 Heap Tree Construction

1. Insert key one by one in given order

Time complexity O(nlogn)

2. Heapify Method
Time complexity O(n)
Prepare max heap from given sequence using Insert key one by
one in given order 14,24,12,11,25,8,35
Prepare min heap from given sequence using heapify method
145,40,25,65,12,48,18,1,100,27,7,3,45,9,3
 Heap Sort Algorithm

• Heap sort is one of the sorting algorithms used to arrange a list of elements in order.
Heapsort algorithm uses one of the tree concepts called Heap Tree.
• In this sorting algorithm, we use Max Heap to arrange list of elements in Descending
order and Min Heap to arrange list elements in Ascending order.
 Quick Sort Algorithm

1. Quick sort is a fast sorting algorithm used to sort a list of elements

2. The quick sort algorithm attempts to separate the list of elements into two parts
and then sort each part recursively. That means it use divide and conquer
strategy. In quick sort, the partition of the list is performed based on the element
called pivot. Here pivot element is one of the elements in the list.
3. The list is divided into two partitions such that "all elements to the left of pivot
are smaller than the pivot and all elements to the right of pivot are greater than
or equal to the pivot".
 Step by Step Process

• Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in
the list).
• Step 2 - Define two variables i and j. Set i and j to first and last elements of the list
respectively.
• Step 3 - Increment i until list[i] > pivot then stop.
• Step 4 - Decrement j until list[j] < pivot then stop.
• Step 5 - If i < j then exchange list[i] and list[j].
• Step 6 - Repeat steps 3,4 & 5 until i > j.
• Step 7 - Exchange the pivot element with list[j] element.
 FOR PRACTICE:

• 35,50,15,25,80,20,90,45
Bubble sort 64, 25, 12, 22, 11

Merge sort [38, 27, 43, 3, 9, 82, 10]

Heap sort 12, 11, 13, 5, 6, 7

Radix sort 170, 45, 75, 90, 802, 24, 2, 66

 Summary
• Insertion Sort, Bubble sort, selection sort, radix sort, Quick Sort, Merge
Sort, Heap Sort, Sorting On
• Several Keys, List and Table Sort, Linear Search, Binary Search,
Comparison of Sorting Algorithms,
• Comparison of searching Algorithms .
 References
1. Data structure using C and C++-AM Tanenbaum, Y Langsam&amp; MJ
Augustein,Prentice Hall India.
2. Data structures & Program Design in C -Robert Kruse, Bruse Leung,Pearson
Education.
 Expected Questions
BAQ
1.Define searching.
2.Define sorting.
SAQ
1. Differentiate bubble sort and insertion sort.
2.Differentiate linear and binary search.
LAQ
1.Explain the concept of a pivot element in quicksort
2.Explain the concept of a pivot element in quicksort.