Sorting and searching

Dr. M. Sohail
Week 12 (Feb 10…14)
Objectives
• Today’s lecture objectives include:

– Sorting
• Merge Sort

• Quick Sort

Data Structures & Algorithms 2

Merge Sort
• Divide an array into halves
– Sort the two halves

– Merge them into one sorted array

Data Structures & Algorithms 3

Merge Sort

Data Structures & Algorithms 4

Merge Sort – Cont…
Merging two sorted arrays into one sorted array.

Data Structures & Algorithms 5

Merge Sort Example – Cont…

Data Structures & Algorithms 6

Data Structures & Algorithms 7
Quick Sort (Divide and Conquer)
• Divides the array into two pieces
– Not necessarily halves of the array

– An element of the array is selected as the pivot

• Elements are rearranged so that:

– The pivot is in its final position in sorted array

– Elements in positions before pivot are less than the pivot

– Elements after the pivot are greater than the pivot

Data Structures & Algorithms 8

Quick Sort – Cont…
• Find the pivot value that will partition the list in such a
way that:

Data Structures & Algorithms 9

Quick Sort Algorithm – Cont…
1. If First < Last THEN
{
2. Partition the elements in the subarray
First..Last so that the pivot value is
in place (in position PivIndex)
3. Apply QuickSort to the first subarray
First..PivIndex-1
4. Apply QuickSort to the second subarray
PivIndex+1..Last
End

Data Structures & Algorithms 10

Quick Sort – How to Partition
1. Define the pivot value as the contents of
Table[First]
2. Initialize Up to First and Down to Last
3. Repeat
4. Increment Up until Up selects the first
element greater than the pivot value
5. Decrement Down until it selects the first
element less than or equal to the pivot value
6. If Up < Down exchange their values until Up
meets or passes Down
7. Exchange Table[First] and Table[Down]
8. Define PivIndex as Down

Data Structures & Algorithms 11

 Quick Sort Algorithm
1.Choose a Pivot: Select an element as the pivot (can be the first, last,
middle, or random).
2.Partition: Rearrange elements so that elements smaller than the pivot
are on the left and elements greater than the pivot are on the right.
3.Recursively Apply Quick Sort: Apply the same logic to the left and right
subarrays.

Data Structures & Algorithms 12

Example: Sorting [8, 3, 1, 7, 0, 10, 2]
Step 1: Choose a Pivot
•Let's take the last element as the pivot: 2
•Rearrange so that numbers less than 2 go to the left, and greater go to the right.
Step 2: Partition the Array
•Compare each element with pivot (2) and swap accordingly:
• [0, 1] (less than 2) | pivot = 2 | [8, 3, 7, 10] (greater than 2)
• New array: [0, 1, 2, 8, 3, 7, 10]
Step 3: Recursively Apply Quick Sort
•Left subarray: [0, 1]
• Pivot = 1
• Partition: [0] | 1 | [] (already sorted)
•Right subarray: [8, 3, 7, 10]
• Pivot = 10
• Partition: [8, 3, 7] | 10 | []
• Sorting [8, 3, 7] (pivot = 7):
• Partition: [3] | 7 | [8] (sorted)
Final Sorted Array
[0, 1, 2, 3, 7, 8, 10]

Data Structures & Algorithms 13

Example

Data Structures & Algorithms 14

Data Structures & Algorithms 15
Data Structures & Algorithms 16
Data Structures & Algorithms 17
Quick Sort Example

• Has First exceeded Last? NO

• Define the value in position First to be the Pivot
Pivot = 44

Data Structures & Algorithms 18

Quick Sort Example – Cont…
• Define Up to be First and Down to be Last

• Move Up to the First value > Pivot

Data Structures & Algorithms 19

Quick Sort Example – Cont…
• Move Down to the First value <= Pivot

• Exchange these values

Data Structures & Algorithms 20

Quick Sort Example – Cont…
• Again move Up to the First value > Pivot

• Move Down to the First value <= Pivot

Data Structures & Algorithms 21

Quick Sort Example – Cont…
• Exchange them

• Again move Up to the First value > Pivot and

• Move Down to the First value <= Pivot

Data Structures & Algorithms 22

Quick Sort Example – Cont…
• Up and Down have passed each other, so
– Exchange the pivot value and the value in Down

Data Structures & Algorithms 23

Quick Sort Example – Cont…
• Note that all values below PivIndex are <= Pivot

• And all values above PivIndex are > Pivot

Data Structures & Algorithms 24

Quick Sort Example – Cont…
• This gives us two subarrays to partition

Data Structures & Algorithms 25

 Searching
Sequential Search Technique (Step by Step)
Sequential search (also known as linear search)
simple searching technique
where we check each element in a list one by one
until we find the target or reach the end.

Step 1: Understand the Algorithm

1.Start from the first element of the list.
2.Compare each element with the target value.
3.If a match is found, return the index.
4.If the target is not found, return -1 (or an appropriate message).
5.This method works on both sorted and unsorted lists.

Data Structures & Algorithms 26

#include <iostream>
using namespace std;

// Function for Sequential Search

int sequentialSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Return index if found
} }
return -1; // Return -1 if not found }

int main() {
int arr[] = {10, 25, 30, 45, 50, 60};
int size = sizeof(arr) / sizeof(arr[0]);
int target;

cout << "Enter the number to search: ";

cin >> target;

int result = sequentialSearch(arr, size, target);

if (result != -1)
cout << "Element found at index: " << result << endl;
else
cout << "Element not found in the array." << endl;

return 0; }

Data Structures & Algorithms 27

Step 3: Explanation of the Code
Function sequentialSearch():
Loops through the array.
Compares each element with the target.
Returns the index if found, otherwise returns -1.
Inside main():Declares an array.
Takes user input for the target.
Calls the function and displays the result.

Data Structures & Algorithms 28

Data Structures & Algorithms 29
 Applications of Sequential Searching in
Computer Science
1.Searching in Small Data Sets – Used when the dataset is small and doesn't require
complex search algorithms.
2.Unsorted Data Searches – Works well when data is not sorted, unlike binary search which
requires sorted data.
3.Symbol Table Lookup – Used in compilers and interpreters for searching variable names,
function names, etc.
4.Database Queries – Applied in simple database searches when indexing is not available.
5.Pattern Matching – Used in string searching algorithms like brute-force pattern matching.
6.Web Scraping – Helps in scanning HTML documents for specific tags or data elements.
7.Memory Management – Used in garbage collection for finding unreferenced objects.
8.Artificial Intelligence – Helps in traversing lists of possible solutions in heuristic searches.
9.Security and Cryptography – Used for brute-force attacks in password cracking and
cryptographic key searches.
10.Data Validation – Helps in checking for duplicate entries or verifying data integrity.

Data Structures & Algorithms 30

 Binary Search
• An efficient searching algorithm
• Used for finding an element in a sorted list.
• It follows a divide and conquer approach
• By repeatedly dividing the search interval in half.

Data Structures & Algorithms 31

 Algorithm Steps
1.Initialize Variables
•Set two pointers low (starting index) and high (last index).
2.Find the Middle Element:
•Calculate mid = (low + high) / 2.
3.Compare the Middle Element with the Target:
•If arr[mid] == target, return the index.
•If arr[mid] > target, search the left half (high = mid - 1).
•If arr[mid] < target, search the right half (low = mid + 1).
• Repeat Steps 2 & 3 until low > high.
5.Return -1 if the element is not found.

Data Structures & Algorithms 32

Data Structures & Algorithms 33
 Applications of Binary Search

1.Searching in Large Sorted Lists (Databases, Phonebooks, etc.).

2.Finding Elements in Sorted Arrays (e.g., Searching in log files).

3.Dictionary Lookup (Auto-correct and word suggestions).

4.Finding Upper and Lower Bounds in range queries.

5.Solving Mathematical Problems (Square root approximation, etc.).

Data Structures & Algorithms 34

 THANK YOU

https://runestone.academy/ns/books/published/pythonds/index.html

Data Structures & Algorithms 35