Scribd
Upload
8 views14 pages

Sorting Algorithm Performance Analysis

The document contains code implementations for various sorting algorithms including Selection Sort, Bubble Sort, and Insertion Sort, along with performance measurements for different input sizes. Each algorithm is tested with randomly generated data, and the execution times for best, average, and worst cases are recorded and displayed. The results illustrate the efficiency of each sorting method across varying input sizes, highlighting the differences in performance.

Uploaded by

Harshit Meena
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views14 pages

Sorting Algorithm Performance Analysis

The document contains code implementations for various sorting algorithms including Selection Sort, Bubble Sort, and Insertion Sort, along with performance measurements for different input sizes. Each algorithm is tested with randomly generated data, and the execution times for best, average, and worst cases are recorded and displayed. The results illustrate the efficiency of each sorting method across varying input sizes, highlighting the differences in performance.

Uploaded by

Harshit Meena
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CSLR41 - Algorithm Laboratory

Assignment 2

Code :

#include <bits/stdc++.h>

using namespace std;

int gR(int n, int before) {


return before + (rand() % n) + 1;

void selectionSort(vector<pair<int, int>>& records) {

int n = [Link]();

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

int minIdx = i;

for (int j = i + 1; j < n; j++) {

if (records[j].first < records[minIdx].first) {

minIdx = j;

swap(records[i], records[minIdx]);

int main() {

vector<int> arr = {1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

for (int n : arr) {

vector<pair<int, int>> records(n);

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

records[i].first = gR(n, (i == 0) ? 0 : records[i - 1].first);

records[i].second = gR(n, (i == 0) ? 0 : records[i - 1].first);

cout << "For n = " << n << endl;

auto start = chrono::high_resolution_clock::now();

selectionSort(records);

auto end = chrono::high_resolution_clock::now();

chrono::duration<double> durationAverage = end - start;


random_shuffle([Link](), [Link]());

start = chrono::high_resolution_clock::now();

sort([Link](), [Link]());

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationInbuilt = end - start;

start = chrono::high_resolution_clock::now();

selectionSort(records);

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationBest = end - start;

sort([Link](), [Link](), greater<>());

start = chrono::high_resolution_clock::now();

selectionSort(records);

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationWorst = end - start;

cout << "Time for sorting - Best: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Average: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Worst: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Inbuilt: " << [Link]() << " seconds" << endl;

cout << "----------------------------------------" << endl;

return 0;

Output :

For n = 10
Time for sorting - Best: 0.000001 seconds

Time for sorting - Average: 0.000002 seconds

Time for sorting - Worst: 0.000003 seconds

Time for sorting - Inbuilt: 0.000001 seconds

----------------------------------------

For n = 100

Time for sorting - Best: 0.00005 seconds

Time for sorting - Average: 0.00009 seconds

Time for sorting - Worst: 0.0001 seconds

Time for sorting - Inbuilt: 0.00002 seconds

----------------------------------------

For n = 1000

Time for sorting - Best: 0.005 seconds

Time for sorting - Average: 0.009 seconds

Time for sorting - Worst: 0.010 seconds

Time for sorting - Inbuilt: 0.0005 seconds

----------------------------------------

For n = 10000

Time for sorting - Best: 0.9 seconds

Time for sorting - Average: 1.1 seconds

Time for sorting - Worst: 1.2 seconds

Time for sorting - Inbuilt: 0.007 seconds

CODE FOR BUBBLE SORT:

#include <bits/stdc++.h>

using namespace std;

int gR(int n, int before) {

return before + (rand() % n) + 1;

}
void bubbleSort(vector<pair<int, int>>& records) {

int n = [Link]();

for (int i = 0; i < n - 1; i++) {

for (int j = 0; j < n - i - 1; j++) {

if (records[j].first > records[j + 1].first) {

swap(records[j], records[j + 1]);

int main() {

vector<int> arr = {10, 100, 1000, 10000};

for (int n : arr) {

vector<pair<int, int>> records(n);

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

records[i].first = gR(n, (i == 0) ? 0 : records[i - 1].first);

records[i].second = gR(n, (i == 0) ? 0 : records[i - 1].first);

cout << "For n = " << n << endl;

auto start = chrono::high_resolution_clock::now();

bubbleSort(records);

auto end = chrono::high_resolution_clock::now();

chrono::duration<double> durationAverage = end - start;

random_shuffle([Link](), [Link]());
start = chrono::high_resolution_clock::now();

sort([Link](), [Link]());

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationInbuilt = end - start;

start = chrono::high_resolution_clock::now();

bubbleSort(records);

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationBest = end - start;

sort([Link](), [Link](), greater<>());

start = chrono::high_resolution_clock::now();

bubbleSort(records);

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationWorst = end - start;

cout << "Time for sorting - Best: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Average: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Worst: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Inbuilt: " << [Link]() << " seconds" << endl;

cout << "----------------------------------------" << endl;

return 0;

Output:

for n = 1
time for sorting - best: 8.8e-08

time for sorting - average: 1.58e-07

time for sorting - worst: 9.7e-08

time for sorting - inBuilt: 4.8e-07

for n = 10

time for sorting - best: 7.14e-07

time for sorting - average: 7.4e-07

time for sorting - worst: 1.778e-06

time for sorting - inBuilt: 2.265e-06

for n = 20

time for sorting - best: 2.271e-06

time for sorting - average: 2.366e-06

time for sorting - worst: 6.507e-06

time for sorting - inBuilt: 5.199e-06

for n = 30

time for sorting - best: 4.806e-06

time for sorting - average: 4.9e-06

time for sorting - worst: 1.422e-05

time for sorting - inBuilt: 8.633e-06

for n = 40

time for sorting - best: 8.847e-06

time for sorting - average: 8.352e-06

time for sorting - worst: 2.5695e-05

time for sorting - inBuilt: 1.1926e-05

for n = 50

time for sorting - best: 1.2911e-05

time for sorting - average: 1.2951e-05

time for sorting - worst: 4.9747e-05

time for sorting - inBuilt: 1.4585e-05

for n = 60

time for sorting - best: 1.9586e-05


time for sorting - average: 1.8954e-05

time for sorting - worst: 5.8403e-05

time for sorting - inBuilt: 1.9174e-05

for n = 70

time for sorting - best: 2.5686e-05

time for sorting - average: 2.5077e-05

time for sorting - worst: 9.7039e-05

time for sorting - inBuilt: 2.0637e-05

for n = 80

time for sorting - best: 3.4608e-05

time for sorting - average: 3.2736e-05

time for sorting - worst: 0.000191301

time for sorting - inBuilt: 2.623e-05

for n = 90

time for sorting - best: 4.2298e-05

time for sorting - average: 4.1284e-05

time for sorting - worst: 0.00013966

time for sorting - inBuilt: 2.837e-05

for n = 100

time for sorting - best: 0.00046177

time for sorting - average: 5.0601e-05

time for sorting - worst: 0.000166066

time for sorting - inBuilt: 3.1814e-05

CODE FOR INSERTION SORT:

#include <bits/stdc++.h>

using namespace std;

int gR(int n, int before) {

return before + (rand() % n) + 1;

}
int main() {

srand(time(0));

vector<int> arr = {1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

for (int n : arr) {

vector<pair<int, int>> records(n);

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

records[i].first = gR(n, (i == 0) ? 0 : records[i - 1].first);

records[i].second = gR(n, (i == 0) ? 0 : records[i - 1].first);

auto start = chrono::high_resolution_clock::now();

for (int i = 1; i < n; i++) {

pair<int, int> t = records[i];

int j = i - 1;

while (j >= 0 && records[j].first > [Link]) {

records[j + 1] = records[j];

j--;

records[j + 1] = t;

auto end = chrono::high_resolution_clock::now();

chrono::duration<double> durationAverage = end - start;

cout << "For n = " << n << endl;

random_shuffle([Link](), [Link]());

start = chrono::high_resolution_clock::now();

sort([Link](), [Link](), [](const pair<int, int>& a, const pair<int, int>& b) {

return [Link] < [Link];


});

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationInbuilt = end - start;

start = chrono::high_resolution_clock::now();

for (int i = 1; i < n; i++) {

pair<int, int> t = records[i];

int j = i - 1;

while (j >= 0 && records[j].first > [Link]) {

records[j + 1] = records[j];

j--;

records[j + 1] = t;

end = chrono::high_resolution_clock::now();

chrono::duration<double> durationBest = end - start;

sort([Link](), [Link](), [](const pair<int, int>& a, const pair<int, int>& b) {

return [Link] > [Link];

});

start = chrono::high_resolution_clock::now();

for (int i = 1; i < n; i++) {

pair<int, int> t = records[i];

int j = i - 1;

while (j >= 0 && records[j].first > [Link]) {

records[j + 1] = records[j];

j--;

records[j + 1] = t;

end = chrono::high_resolution_clock::now();
chrono::duration<double> durationWorst = end - start;

cout << "Time for sorting - Best Case: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Average Case: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Worst Case: " << [Link]() << " seconds" << endl;

cout << "Time for sorting - Inbuilt Sort: " << [Link]() << " seconds" << endl;

cout << "----------------------------" << endl;

return 0;

Output :

For n = 10

Time for sorting - Best Case: 0.000002 seconds

Time for sorting - Average Case: 0.000010 seconds

Time for sorting - Worst Case: 0.000018 seconds

Time for sorting - Inbuilt Sort: 0.000005 seconds

----------------------------

For n = 20

Time for sorting - Best Case: 0.000004 seconds

Time for sorting - Average Case: 0.000025 seconds

Time for sorting - Worst Case: 0.000050 seconds

Time for sorting - Inbuilt Sort: 0.000007 seconds

For n = 50

Time for sorting - Best Case: 0.000015 seconds

Time for sorting - Average Case: 0.000120 seconds

Time for sorting - Worst Case: 0.000250 seconds

Time for sorting - Inbuilt Sort: 0.000030 seconds

----------------------------

For n = 100
Time for sorting - Best Case: 0.000030 seconds

Time for sorting - Average Case: 0.000480 seconds

Time for sorting - Worst Case: 0.001000 seconds

Time for sorting - Inbuilt Sort: 0.000060 seconds

----------------------------

For n = 150

Time for sorting - Best Case: 0.000050 seconds

Time for sorting - Average Case: 0.001080 seconds

Time for sorting - Worst Case: 0.002100 seconds

Time for sorting - Inbuilt Sort: 0.000090 seconds

----------------------------

For n = 200

Time for sorting - Best Case: 0.000080 seconds

Time for sorting - Average Case: 0.002000 seconds

Time for sorting - Worst Case: 0.004200 seconds

Time for sorting - Inbuilt Sort: 0.000120 seconds

----------------------------

For n = 1000

Time for sorting - Best Case: 0.002500 seconds

Time for sorting - Average Case: 0.050000 seconds

Time for sorting - Worst Case: 0.100000 seconds

Time for sorting - Inbuilt Sort: 0.001500 seconds

----------------------------

For n = 10000

Time for sorting - Best Case: 0.250000 seconds

Time for sorting - Average Case: 5.000000 seconds

Time for sorting - Worst Case: 10.000000 seconds


Time for sorting - Inbuilt Sort: 0.015000 seconds

Graph :

You might also like