A performance-optimized, parallel implementation of the Quicksort algorithm using MPI, emphasizing a median-based pivot selection mechanism.
Quicksort, though highly efficient in average-case scenarios, can be bottlenecked with large datasets. This project parallelizes the Quicksort algorithm with MPI and employs an optimal median-based pivot selection to enhance its performance, making it suitable for distributed environments.
-
Median-Based Pivot Selection:
- Extracts local medians from segments of data.
- Aggregates to decide an overall median, ensuring efficient partitioning.
-
Optimized Parallel Quicksort:
- Data Decomposition: Distributes data evenly across processes.
- Reduced Communication Overhead: Uses MPI functionalities to minimize inter-process communication.
- Dynamic Process Segregation: Segregates processes based on their relative data values to efficiently tackle data chunks.
Requirements: MPI installed
# Clone the repository
git clone https://github.com/vyom1611/Medianized-MPI-Quicksort.git
# Navigate into the directory
cd Medianized-MPI-Quicksort
# Compile the main file
mpicc -o mpi_qs main.c
# Run the program with desired number of processes and parameters
mpirun -np [Number of Processes] ./mpi_qs [Total Number of Integers] [Output File Name]
The project utilizes the median of medians strategy for pivot selection, resulting in more balanced partitions and efficient sorting. The time metrics showcase the speed-up gained from this parallel approach.
![Screenshot 2023-11-01 at 5 15 24 PM](https://private-user-images.githubusercontent.com/93402393/279814669-0d911a87-e3a3-4264-ba55-b90cf6482b24.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjM4Nzg2MTUsIm5iZiI6MTcyMzg3ODMxNSwicGF0aCI6Ii85MzQwMjM5My8yNzk4MTQ2NjktMGQ5MTFhODctZTNhMy00MjY0LWJhNTUtYjkwY2Y2NDgyYjI0LnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA4MTclMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwODE3VDA3MDUxNVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWQ0ZDgwNWY3NjNmZWM2ZGFkZjE4MmFjMGFmOTk5ZGIwMDYxZjJjMjA1Y2NhOWIxOGM4NDBlMjRjODAzOWJjOGMmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.8PlSb2hbV9wNo5Gl8Xo8u1vFNnm4wSyp4AUeEwxy73s)