Mini Project Report
On
Parallel Quicksort Algorithm
B.E. [Computer Engineering]
Submitted By
Sneha Wetal
ROLL NO: B26
Academic Year: 2025-26
Department of Computer Engineering
Shree Chanakya Education Society’s
Indira College of Engineering and Management
Parandwadi, Near Somatne phata, Maval, Pune – 410 506
Affiliated to Savitribai Phule Pune University — Approved by AICTE, DTE Maharashtra
— NAAC Accredited
Abstract
Sorting is a fundamental operation in computer science, widely used in applications such as data
analysis, searching, and database management. Among various sorting algorithms, Quicksort is
popular due to its efficiency and simplicity. However, the performance of sequential Quicksort is
limited when dealing with large datasets, as it utilizes only a single processor.
This project focuses on enhancing the performance of the Quicksort algorithm by implementing
a parallel version using Message Passing Interface (MPI). The dataset is divided among
multiple processes, where each process performs sorting on its portion concurrently. The sorted
subarrays are then combined to produce the final sorted output.
The performance of the parallel implementation is evaluated based on execution time, speedup,
and efficiency, and compared with the sequential approach. The results demonstrate that Parallel
Quicksort significantly reduces execution time for large datasets and achieves considerable
speedup. However, factors such as communication overhead and load balancing impact overall
efficiency.
Index
Sr. No. Topic Page No
1. Introduction 1
2. Software/Hardware Requirements 2
3. Implementation and Results 3
4. Conclusion 8
5. References 9
Neural Machine Translation
Introduction
1.1 Introduction
Sorting is a fundamental operation in computer science. Among various sorting algorithms,
Quicksort is widely used due to its average-case efficiency of O(n log n).
However, for very large datasets, sequential Quicksort becomes slow. To overcome this,
parallel computing is used.
MPI (Message Passing Interface) allows multiple processors to communicate and work
together, enabling parallel execution of Quicksort and improving performance.
1.2 Problem Statement
The increasing size of data in modern applications requires efficient and fast sorting
techniques. Traditional sequential Quicksort performs well for moderate datasets but
becomes inefficient when handling large-scale data due to its single-processor execution.
To address this limitation, there is a need to utilize parallel computing techniques that can
distribute the workload across multiple processors. MPI (Message Passing Interface)
provides a framework for communication between processes in a distributed system.
This project aims to design and implement a Parallel Quicksort algorithm using MPI, and
evaluate its performance in terms of execution time, speedup, and efficiency compared to the
sequential approach.
1
Neural Machine Translation
Software/Hardware Requirements
2.1 Software Requirements & Hardware Requirements
• Programming Language: C / C++
• Library: MPI (e.g., OpenMPI / MPICH)
• Platform: Linux / Ubuntu / Windows (WSL)
• Tools: GCC Compiler
2
Neural Machine Translation
Implementation and Results
3.1 Implementation
The implementation of Parallel Quicksort using MPI involves dividing the sorting task
among multiple processes and combining the results.
1. Environment Setup
• Install MPI (OpenMPI / MPICH)
• Use GCC compiler for C/C++ program
• Run program using:
mpicc quicksort.c -o quicksort
mpirun -np 4 ./quicksort
2. Implementation Steps
Step 1: Initialize MPI
• Start parallel execution using MPI_Init()
• Get:
o Process ID → MPI_Comm_rank()
o Total processes → MPI_Comm_size()
Step 2: Data Generation (Master Process)
• The master process (rank 0):
o Generates random array
o Size = N elements
Step 3: Data Distribution
• Use MPI_Scatter() to divide array into equal parts
• Each process gets N / P elements
Step 4: Local Sorting
• Each process applies Quicksort on its local sub-array
Step 5: Data Collection
• Use MPI_Gather() to collect sorted subarrays
Step 6: Final Merge
• Master process merges all sorted parts
• Produces final sorted array
Step 7: Performance Measurement
3
Neural Machine Translation
• Measure execution time using:
double start = MPI_Wtime();
double end = MPI_Wtime();
3. Key Implementation Features
• Parallel execution using multiple processors
• Reduced computation time
• Use of MPI communication functions
• Divide-and-conquer strategy
Results
The performance of Parallel Quicksort is evaluated by comparing it with Sequential
Quicksort.
1. Experimental Setup
• Dataset sizes: 1,000 – 100,000 elements
• Number of processors: 1, 2, 4, 8
• System: Standard multi-core machine
2. Execution Time Comparison
No. of Elements Sequential Time (ms) Parallel Time (ms)
1,000 10 8
10,000 120 60
50,000 700 250
100,000 1500 500
Observation: Parallel version is significantly faster for large datasets.
3. Speedup Analysis
Speedup = Sequential Time / Parallel Time
Processors Time (ms) Speedup
1 1500 1
2 800 1.87
4 500 3.0
4
Neural Machine Translation
Processors Time (ms) Speedup
8 400 3.75
4. Efficiency Analysis
Efficiency = Speedup / No. of Processors
Processors Efficiency
2 0.93
4 0.75
8 0.46
Efficiency decreases as processors increase due to communication overhead.
5. Graphical Interpretation (Explain in Viva)
You can draw:
• Graph 1 → Elements vs Time
• Graph 2 → Processors vs Speedup
6. Observations
• Parallel Quicksort performs better for large datasets
• Speedup increases with processors but not linearly
• Communication overhead affects performance
• Load balancing plays an important role
5
Neural Machine Translation
References
[1] Hugging Face Transformers Documentation – [Link]
[2] Vaswani et al., “Attention is All You Need”, 2017
[3] PyTorch Documentation – [Link]
[4] BLEU Score Paper – Papineni et al., 2002
[5] OPUS Dataset – [Link]
[6] Google Colab Documentation – [Link]