Parallel and Distributed

Computing

Parallel Algorithms
(Parallel Searching and Sorting)

By:
Muhammad Imran
Assistant Prof. of Computer Science
Govt. Millat Degree College Mumtazabad, Multan

Lecturer (Visiting Faculty) of I.T

University of Education (Multan Campus) Multan
2 Parallel Algorithms

Parallel Algorithms:
What is a Parallel Algorithm?

A parallel algorithm is an algorithm that divides a problem into smaller tasks and executes them
simultaneously using multiple processors.

Goals of Parallel Algorithms

 Reduce execution time

 Increase efficiency
 Handle large datasets
 Improve scalability

What is Parallel Search?

Parallel search is a searching technique in which multiple processors search different parts of
data simultaneously.

Instead of one processor checking all data sequentially, many processors work together.

Objectives of Parallel Search

 Reduce searching time
 Improve performance
 Handle very large datasets
 Utilize multiple processors efficiently

Types of Parallel Search

1. Parallel Linear Search
2. Parallel Binary Search
3. Parallel Tree Search
4. Parallel Graph Search
5. Distributed Search

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
3 Parallel Algorithms

1. Parallel Linear Search

Definition

In parallel linear search, data is divided into multiple parts, and each processor searches its
assigned part simultaneously.

Working Principle

Steps

1. Divide array into chunks

2. Assign each chunk to a processor
3. Processors search simultaneously
4. Return result if element is found

Example of Parallel Linear Search

Problem

Search number 55 in array:

[10, 22, 35, 40, 55, 60, 70, 90]

Division

 Processor P1 → [10, 22]

 Processor P2 → [35, 40]
 Processor P3 → [55, 60]
 Processor P4 → [70, 90]

Execution

 P1 searches first block

 P2 searches second block
 P3 finds 55
 Search stops

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
4 Parallel Algorithms

C Program Example (OpenMP)

#include <stdio.h>

#include <omp.h>

int main() {

int arr[8] = {10,22,35,40,55,60,70,90};

int key = 55;

int found = 0;

#pragma omp parallel for

for(int i=0;i<8;i++) {

if(arr[i] == key) {

found = 1;

printf("Element found at index %d\n", i);

if(!found)

printf("Element not found\n");

return 0;

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
5 Parallel Algorithms

Advantages of Parallel Linear Search

 Faster than sequential search

 Easy implementation
 Good for unsorted data

Disadvantages

 Communication overhead
 Synchronization required

2. Parallel Binary Search

Definition

Parallel binary search performs binary search using multiple processors.

It works only on sorted data.

Binary Search Formula

The middle index is calculated using:

\frac{low +

Working Steps

1. Divide sorted data

2. Multiple processors examine sections
3. Compare middle elements
4. Narrow search range

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
6 Parallel Algorithms

Example

Sorted Array
[5,10,15,20,25,30,35,40]

Search key = 30

Execution

 Mid = 20
 30 > 20
 Search right half
 Find 30

Parallel Binary Search C Example

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key) {

while(low <= high) {

int mid = (low + high)/2;

if(arr[mid] == key)

return mid;

if(arr[mid] < key)

low = mid + 1;

else

high = mid - 1;

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
7 Parallel Algorithms

return -1;

int main() {

int arr[] = {5,10,15,20,25,30,35,40};

int result = binarySearch(arr,0,7,30);

if(result != -1)

printf("Element found at index %d", result);

else

printf("Element not found");

return 0;

3. Parallel Tree Search

Definition

Processors search different branches of a tree simultaneously.

Applications

 Artificial intelligence
 Game trees
 File systems

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
8 Parallel Algorithms

 Decision trees

Example

In chess AI:

 Each processor analyzes different moves simultaneously.

4. Parallel Graph Search

Definition

Multiple processors explore graph nodes simultaneously.

Applications

 Network routing
 Social networks
 Web crawling

Example

Breadth First Search (BFS) can be parallelized by exploring multiple neighboring nodes
together.

5. Distributed Search
Definition

Search operation distributed across multiple machines connected by network.

Example

Search engines like Google:

 Different servers search different indexes simultaneously.

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
9 Parallel Algorithms

Performance Analysis of Parallel Search

Advantages of Parallel Search

 Reduced search time
 Efficient for large datasets
 Better processor utilization
 Scalable

Disadvantages of Parallel Search

 Synchronization complexity
 Communication overhead
 Load balancing issues

Real-Life Applications of Parallel Search

 Search engines
 Database systems
 Cybersecurity scanning
 DNA sequence matching
 AI systems

What is Parallel Sorting?

Parallel sorting is a sorting technique where multiple processors sort different parts of data
simultaneously.

Need for Parallel Sorting

Sorting huge datasets sequentially takes significant time.

Parallel sorting improves:

 Speed
 Scalability
 Performance

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
10 Parallel Algorithms

Types of Parallel Sorting Algorithms

1. Parallel Bubble Sort
2. Parallel Merge Sort
3. Parallel Quick Sort
4. Odd-Even Transposition Sort
5. Bitonic Sort
6. Distributed Sorting

1. Parallel Bubble Sort

Definition

Multiple processors compare and swap adjacent elements simultaneously.

Example

Initial Array
[8,4,6,2]

Step 1

 Compare 8 and 4 → Swap

 Compare 6 and 2 → Swap

Result:

[4,8,2,6]

C Program Example
#include <stdio.h>

#include <omp.h>

int main() {

int arr[5] = {5,1,4,2,8};

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
11 Parallel Algorithms

for(int i=0;i<5;i++) {

#pragma omp parallel for

for(int j=0;j<4;j++) {

if(arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

printf("Sorted Array:\n");

for(int i=0;i<5;i++)

printf("%d ", arr[i]);

return 0;

Advantages
 Simple implementation
 Easy understanding

Disadvantages
 Inefficient for large datasets
 High synchronization cost

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
12 Parallel Algorithms

2. Parallel Merge Sort

Definition

Merge sort divides data recursively and sorts parts simultaneously.

Working Principle

1. Divide array into halves

2. Sort halves in parallel
3. Merge sorted halves

Example

Array
[8,3,6,2,7,1]

Division
[8,3,6] [2,7,1]

Sorted Halves
[3,6,8] [1,2,7]

Final Merge
[1,2,3,6,7,8]

Advantages

 Efficient for large datasets

 Good scalability
 Stable sorting algorithm

Disadvantages

 Extra memory required

 Complex implementation

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
13 Parallel Algorithms

3. Parallel Quick Sort

Definition

Quick sort selects a pivot and partitions data into smaller sections processed simultaneously.

Working Steps

1. Choose pivot
2. Partition array
3. Sort partitions in parallel

Example

Array
[9,4,7,3,10,5]

Pivot = 7

Left:

[4,3,5]

Right:

[9,10]

Parallel sorting performed on both sides.

Advantages

 Very fast average performance

 Efficient for large systems

Disadvantages

 Worst-case complexity possible

 Load balancing problems

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.