4.
Sort a given set of n integer elements using Quick Sort method and
compute its time complexity. Run the program for varied values of n>
5000 and record the time taken to sort. Plot a graph of the time taken
versus n on graph sheet. The elements can be read from a file or can be
generated using the random number generator. Demonstrate using CPP
how the divide-and-conquer method works along with its time complexity
analysis: worst case, average case and best case.
PROGRAM:
#include <iostream>
#include <vector>
#include <cstdlib> // For srand() and rand()
#include <ctime> // For time()
#include <chrono> // For measuring time
using namespace std;
// Quick Sort Partition Function
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
++i;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
// Quick Sort Function
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to generate random data
vector<int> generateRandomData(int n) {
vector<int> data(n);
for (int i = 0; i < n; ++i) {
data[i] = rand() % 100000; // Random numbers between 0 and
99,999
}
return data;
}
// Main Function
int main() {
srand(time(0)); // Seed the random number generator
int nTimes;
cout << "Enter the number of times to run the sorting operation for
calculating average or best case: ";
cin >> nTimes;
if (nTimes <= 0) {
cerr << "Please enter a positive number of runs!" << endl;
return 1;
}
// Vector to store all sorted arrays
vector<vector<int>> sortedRuns;
// Step 1: Run QuickSort on randomly generated data
for (int run = 1; run <= nTimes; ++run) {
int n;
cout << "\nRun " << run << ": Enter the size of the array to sort (n >
5000): ";
cin >> n;
if (n <= 5000) {
cerr << "Please enter a value greater than 5000!" << endl;
return 1;
}
// Generate random data based on user input
vector<int> data = generateRandomData(n);
// Measure time taken for QuickSort on random data
auto start = chrono::high_resolution_clock::now();
quickSort(data, 0, [Link]() - 1);
auto end = chrono::high_resolution_clock::now();
// Store the sorted array
sortedRuns.push_back(data);
// Calculate time taken in milliseconds
chrono::duration<double, milli> duration = end - start;
cout << "Time taken to sort an array of size " << n << " (random
data): " << [Link]() << " ms\n";
}
// Step 2: Run QuickSort again using sortedRuns as input and
measure the time
cout << "\nRunning QuickSort on already sorted arrays(Worst-Case):"
<< endl;
for (size_t run = 0; run < [Link](); ++run) {
auto start = chrono::high_resolution_clock::now();
quickSort(sortedRuns[run], 0, sortedRuns[run].size() - 1);
auto end = chrono::high_resolution_clock::now();
// Calculate time taken in milliseconds
chrono::duration<double, milli> duration = end - start;
cout << "Time taken to sort Run " << run + 1 << " (sorted data): " <<
[Link]() << " ms\n";
}
return 0;
}
Output:
Here's the graph comparing QuickSort's performance in the Best Case
and Average Case (random data) vs. the Worst Case (sorted data). The
green line represents the best-case scenario, while the red line shows
the worst case. As expected, the worst-case time increases dramatically
due to Quicksort's degraded performance when sorting already sorted
data.
—---------------------------------------------------------------------------------------------
5. Sort a given set of n integer elements using Merge Sort method and
compute its time complexity. Run the program for varied values of n>
5000, and record the time taken to sort. Plot a graph of the time taken
versus n on graph sheet. The elements can be read from a file or can be
generated using the random number generator. Demonstrate using CPP
how the divide-and-conquer method works along with its time complexity
analysis: worst case, average case and best case.
PROGRAM:
#include <iostream>
#include <vector>
#include <cstdlib> // For srand() and rand()
#include <ctime> // For time()
#include <chrono> // For measuring time
using namespace std;
// Merge Function
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int i = 0; i < n2; ++i)
R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
++i;
} else {
arr[k] = R[j];
++j;
}
++k;
}
while (i < n1) {
arr[k] = L[i];
++i;
++k;
}
while (j < n2) {
arr[k] = R[j];
++j;
++k;
}
}
// Merge Sort Function
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Function to generate random data
vector<int> generateRandomData(int n) {
vector<int> data(n);
for (int i = 0; i < n; ++i) {
data[i] = rand() % 100000; // Random numbers between 0 and 99,999
}
return data;
}
// Main Function
int main() {
srand(time(0)); // Seed the random number generator
int nTimes;
cout << "Enter the number of times to run the sorting operation for
calculating average or best case: ";
cin >> nTimes;
if (nTimes <= 0) {
cerr << "Please enter a positive number of runs!" << endl;
return 1;
}
// Vector to store all sorted arrays
vector<vector<int>> sortedRuns;
// Step 1: Run MergeSort on randomly generated data
for (int run = 1; run <= nTimes; ++run) {
int n;
cout << "\nRun " << run << ": Enter the size of the array to sort (n >
5000): ";
cin >> n;
if (n <= 5000) {
cerr << "Please enter a value greater than 5000!" << endl;
return 1;
}
// Generate random data based on user input
vector<int> data = generateRandomData(n);
// Measure time taken for MergeSort on random data
auto start = chrono::high_resolution_clock::now();
mergeSort(data, 0, [Link]() - 1);
auto end = chrono::high_resolution_clock::now();
// Store the sorted array
sortedRuns.push_back(data);
// Calculate time taken in milliseconds
chrono::duration<double, milli> duration = end - start;
cout << "Time taken to sort an array of size " << n << " (random
data): " << [Link]() << " ms\n";
}
// Step 2: Run MergeSort again using sortedRuns as input and
measure the time
cout << "\nRunning MergeSort on already sorted arrays:" << endl;
for (size_t run = 0; run < [Link](); ++run) {
auto start = chrono::high_resolution_clock::now();
mergeSort(sortedRuns[run], 0, sortedRuns[run].size() - 1);
auto end = chrono::high_resolution_clock::now();
// Calculate time taken in milliseconds
chrono::duration<double, milli> duration = end - start;
cout << "Time taken to sort Run " << run + 1 << " (sorted data): " <<
[Link]() << " ms\n";
}
return 0;
}
Output:
Here's the graph comparing Merge Sort Performance Comparison the
best/average case (random data) vs. the worst case (sorted data). The
green line represents the best case, while the red line represents the
worst case. As expected, MergeSort maintains stable performance in
both cases due to its (O(n log n)) complexity.