Scribd
Upload
10 views8 pages

DSA Code

The document contains a C++ program that implements various sorting algorithms including insertion sort, merge sort, and quick sort, along with functions to generate random, ascending, and descending lists. It measures and compares the execution time of these sorting algorithms on lists of varying sizes and types, providing results in a tabular format. The program is designed to run multiple tests for accuracy and presents the average time taken for each sorting method.

Uploaded by

Kale'ab Lemma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views8 pages

DSA Code

The document contains a C++ program that implements various sorting algorithms including insertion sort, merge sort, and quick sort, along with functions to generate random, ascending, and descending lists. It measures and compares the execution time of these sorting algorithms on lists of varying sizes and types, providing results in a tabular format. The program is designed to run multiple tests for accuracy and presents the average time taken for each sorting method.

Uploaded by

Kale'ab Lemma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

#include<iostream>

#include<vector>
#include<algorithm>
#include<chrono>
#include<random>
#include<numeric>
void insertionSort(std::vector<int>& arr) {
int n= arr.size();
for( int i=1; i<n; ++i) {
int key=arr[i];
int j=i-1;
while(j>=0 && arr[j]>key) {
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=key;
}
}
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1= mid-left +1;
int n2=right-mid;
std::vector<int>L(n1);
std::vector<int>R(n2);
for (int i=0; i<n1; ++i) L[i]=arr[left + i];
for (int j=0; j<n2; ++j) R[j]=arr[mid + 1 + j];
int i=0;
int j=0;
int 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++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left>= right) return;
int mid= left + (right-left)/2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
int partition(std::vector<int>&arr, int low, int high) {
int pivot=arr[high];
int i= (low-1);
for (int j=low; j<=high-1; ++j) {
if (arr[j]<= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i+1], arr[high]);
return(i+1);
}
void quickSort(std::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);
}
}
std::vector<int> generateRandomList(int size, int max_val=1000000) {
std::vector<int> arr(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distrib(0, max_val);
for (int i=0; i<size; ++i) {
arr[i]=distrib(gen);
}
return arr;
}
std::vector<int> generateAscendingList(int size) {
std::vector<int> arr(size);
std::iota(arr.begin(), arr.end(), 0);
return arr;
}
std::vector<int> generateDescendingList(int size) {
std::vector<int> arr(size);
std::iota(arr.rbegin(), arr.rend(), 0);
return arr;
}
int main () {
std::vector<int> list_sizes_large= {1000, 2000, 3000, 4000, 5000,
6000, 7000, 8000, 9000, 10000};
std::vector<int> list_sizes_small= {10, 50, 100, 200, 500};
int num_runs_per_test=5;

std::cout<<"--- Part 1: Computing Running Time in Milliseconds ---\n\


n";
std::cout<<"Note: Times are averaged over " << num_runs_per_test << "
runs.\n";
std::cout<<"\n--- Large Lists (1,000 - 10,000 items) ---\n";
std::cout<<"List Type | List Size | Insertion Sort (ms) | Merge
Sort (ms) | Quick Sort (ms)\n";

std::cout<<"-------------------------------------------------------------
--------------------\n";
for (int size : list_sizes_large) {
double total_insertion_time= 0.0;
double total_merge_time= 0.0;
double total_quick_time=0.0;

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


std::vector<int> arr_copy;

arr_copy= generateRandomList(size);
auto start=std::chrono::high_resolution_clock::now();
insertionSort(arr_copy);
auto end= std::chrono::high_resolution_clock::now();
total_insertion_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy=generateRandomList(size);
start= std::chrono::high_resolution_clock::now();
mergeSort(arr_copy, 0, arr_copy.size() -1);
end= std::chrono::high_resolution_clock::now();
total_merge_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
arr_copy=generateRandomList(size);
start= std::chrono::high_resolution_clock::now();
quickSort(arr_copy, 0, arr_copy.size() -1);
end= std::chrono::high_resolution_clock::now();
total_quick_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
}
std::cout<<"Random | " << size << " | "
<<total_insertion_time/num_runs_per_test << " | "
<<total_merge_time/ num_runs_per_test << " | "
<<total_quick_time/ num_runs_per_test <<"\n";
}
for (int size: list_sizes_large) {
double total_insertion_time= 0.0;
double total_merge_time= 0.0;
double total_quick_time= 0.0;

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


std::vector<int> arr_copy;

arr_copy= generateAscendingList(size);
auto start= std::chrono::high_resolution_clock::now();
insertionSort(arr_copy);
auto end= std::chrono::high_resolution_clock::now();
total_insertion_time +=
std::chrono::duration_cast<std::chrono::microseconds>(end-start).
count()/1000.0;

arr_copy= generateAscendingList(size);
start= std::chrono::high_resolution_clock::now();
mergeSort(arr_copy,0, arr_copy.size() -1);
end= std::chrono::high_resolution_clock::now();
total_merge_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy=generateAscendingList(size);
start= std::chrono::high_resolution_clock::now();
quickSort(arr_copy, 0, arr_copy.size() -1);
end= std::chrono::high_resolution_clock::now();
total_quick_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
}
std::cout<< "Ascending | " << size << " | "
<<total_insertion_time/num_runs_per_test<<" | "
<<total_merge_time/num_runs_per_test<<" | "
<<total_quick_time/ num_runs_per_test<<"\n";
}
for (int size: list_sizes_large) {
double total_insertion_time=0.0;
double total_merge_time=0.0;
double total_quick_time=0.0;

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


std::vector<int> arr_copy;

arr_copy=generateDescendingList(size);
auto start= std::chrono::high_resolution_clock::now();
insertionSort(arr_copy);
auto end= std::chrono::high_resolution_clock::now();
total_insertion_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy= generateDescendingList(size);
start= std::chrono::high_resolution_clock::now();
mergeSort(arr_copy, 0, arr_copy.size()-1);
end= std::chrono::high_resolution_clock::now();
total_merge_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy= generateDescendingList(size);
start= std::chrono::high_resolution_clock::now();
quickSort(arr_copy, 0, arr_copy.size()-1);
end= std::chrono::high_resolution_clock::now();
total_quick_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
}
std::cout<<"Descending | " << size << " | "
<<total_insertion_time/ num_runs_per_test<<" | "
<<total_merge_time/ num_runs_per_test<<" | "
<<total_quick_time/num_runs_per_test<<"\n";
}

std::cout<<"-------------------------------------------------------------
--------------------\n";
std::cout<<"\n--- Few Items (10 - 500 items) ---\n";
std::cout<<"List Type | List Size | Insertion Sort (ms) | Merge
Sort (ms) | Quick Sort (ms)\n";

std::cout<<"-------------------------------------------------------------
--------------------\n";

for (int size: list_sizes_small) {


double total_insertion_time=0.0;
double total_merge_time=0.0;
double total_quick_time=0.0;

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


std::vector<int> arr_copy;

arr_copy=generateRandomList(size);
auto start= std::chrono::high_resolution_clock::now();
insertionSort(arr_copy);
auto end= std::chrono::high_resolution_clock::now();
total_insertion_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy= generateRandomList(size);
start= std::chrono::high_resolution_clock::now();
mergeSort(arr_copy, 0, arr_copy.size()-1);
end= std::chrono::high_resolution_clock::now();
total_merge_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy= generateRandomList(size);
start= std::chrono::high_resolution_clock::now();
quickSort(arr_copy, 0, arr_copy.size()-1);
end= std::chrono::high_resolution_clock::now();
total_quick_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
}
std::cout<<"Random | " << size << " | "
<<total_insertion_time/ num_runs_per_test<<" | "
<<total_merge_time/ num_runs_per_test<<" | "
<<total_quick_time/num_runs_per_test<<"\n";
}
for (int size: list_sizes_small) {
double total_insertion_time=0.0;
double total_merge_time=0.0;
double total_quick_time=0.0;

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


std::vector<int> arr_copy;

arr_copy= generateAscendingList(size);
auto start= std::chrono::high_resolution_clock::now();
insertionSort(arr_copy);
auto end= std::chrono::high_resolution_clock::now();
total_insertion_time +=
std::chrono::duration_cast<std::chrono::microseconds>(end-start).
count()/1000.0;

arr_copy= generateAscendingList(size);
start= std::chrono::high_resolution_clock::now();
mergeSort(arr_copy,0, arr_copy.size() -1);
end= std::chrono::high_resolution_clock::now();
total_merge_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy=generateAscendingList(size);
start= std::chrono::high_resolution_clock::now();
quickSort(arr_copy, 0, arr_copy.size() -1);
end= std::chrono::high_resolution_clock::now();
total_quick_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
}
std::cout<< "Ascending | " << size << " | "
<<total_insertion_time/num_runs_per_test<<" | "
<<total_merge_time/num_runs_per_test<<" | "
<<total_quick_time/ num_runs_per_test<<"\n";
}
for (int size: list_sizes_small) {
double total_insertion_time=0.0;
double total_merge_time=0.0;
double total_quick_time=0.0;

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


std::vector<int> arr_copy;
arr_copy=generateDescendingList(size);
auto start= std::chrono::high_resolution_clock::now();
insertionSort(arr_copy);
auto end= std::chrono::high_resolution_clock::now();
total_insertion_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy= generateDescendingList(size);
start= std::chrono::high_resolution_clock::now();
mergeSort(arr_copy, 0, arr_copy.size()-1);
end= std::chrono::high_resolution_clock::now();
total_merge_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;

arr_copy= generateDescendingList(size);
start= std::chrono::high_resolution_clock::now();
quickSort(arr_copy, 0, arr_copy.size()-1);
end= std::chrono::high_resolution_clock::now();
total_quick_time+=
std::chrono::duration_cast<std::chrono::microseconds>(end-
start).count()/1000.0;
}
std::cout<<"Descending | " << size << " | "
<<total_insertion_time/ num_runs_per_test<<" | "
<<total_merge_time/ num_runs_per_test<<" | "
<<total_quick_time/num_runs_per_test<<"\n";
}
std::cout <<
"------------------------------------------------------------------------
---------\n";
return 0;
}

You might also like