Data Structures and Algorithms Lab
CSL 221
Lab Journal
Student Name: Meerab Hanif
Enrolment No. 01-134251-041
Class and Section: BSCS 3A
Department of Computer Sciences
BAHRIA UNIVERSITY, ISLAMABAD
Lab Title : Sorting
Objectives:
To implement and compare the efficiency of different sorting techniques.
Tools Used:
Visual Studio
Submission Date:
5/15/2026
Evaluation: Signatures of Lab Instructor:
BUBBLE SORT:
#include<iostream>
using namespace std;
void bubble(int x[], int n) {
int hold, j, pass;
int switched = true;
for (pass = 0; pass < n - 1 && switched == true; pass++) {
switched = false;
for (j = 0; j < n - pass - 1; j++){
if (x[j] > x[j + 1]) {
switched = true;
hold = x[j];
x[j] = x[j + 1];
x[j + 1] = hold;
}
}
}
}
int main() {
int arr[5];
cout << "enter array elements: ";
for (int i = 0; i < 5; i++) {
cin >> arr[i];
}
bubble(arr, 5);
cout << "bubble sorted array: ";
for (int i = 0; i < 5; i++) {
cout << arr[i];
cout << endl;
}
return 0;
}
OUTPUT:
INSERT SORT:
#include<iostream>
using namespace std;
void insertionSort(int x[], int n) {
int j, k, y;
for (k = 1; k < n; k++) {
y = x[k];
for (j = k - 1; j >= 0 && y < x[j]; j--) {
x[j + 1] = x[j];
}
x[j + 1] = y;
}
}
int main() {
int arr[5];
cout << "enter array elements: ";
for (int i = 0; i < 5; i++) {
cin >> arr[i];
}
insertionSort(arr, 5);
cout << "sorted array: ";
for (int i = 0; i < 5; i++) {
cout << arr[i];
cout << endl;
}
return 0;
}
OUTPUT:
Time Execution:
#include<iostream>
#include<time.h>
using namespace std;
int main() {
time_t start, end;
char szInput[25];
double dif;
time(&start);
cout << "please, enter your name: ";
cin >> szInput;
time(&end);
dif = difftime(end, start);
cout << "Hi " << szInput;
cout << " it took you " << dif << " seconds to type your name." << endl;
return 0;
}
OUTPUT:
SELECTION SORT:
#include<iostream>
using namespace std;
void Selectionsort(int x[], int n)
{
int key;
for (int a = 0; a < n; a++)
{
key = a;
for (int b = a + 1; b < n; b++) {
if (x[b] < x[key]) key = b;
}
if (key > a) {
int temp = x[a];
x[a] = x[key];
x[key] = temp;
}
}
}
int main() {
int arr[5];
cout << "enter array elements: ";
for (int i = 0; i < 5; i++) {
cin >> arr[i];
}
Selectionsort(arr, 5);
cout << "selection sorted array: ";
for (int i = 0; i < 5; i++) {
cout << arr[i];
cout << endl;
}
return 0;
}
OUTPUT:
Exercise 13.1
Program:
#include<iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
int comparisons = 0;
int exchanges = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
exchanges++;
}
}
}
cout << "\nBubble Sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\nComparisons = " << comparisons;
cout << "\nExchanges = " << exchanges << endl;
}
void selectionSort(int arr[], int n) {
int comparisons = 0;
int exchanges = 0;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
comparisons++;
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
exchanges++;
}
}
cout << "\nSelection Sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\nComparisons = " << comparisons;
cout << "\nExchanges = " << exchanges << endl;
}
void insertionSort(int arr[], int n) {
int comparisons = 0;
int exchanges = 0;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0) {
comparisons++;
if (arr[j] > key) {
arr[j + 1] = arr[j];
exchanges++;
j--;
}
else {
break;
}
}
arr[j + 1] = key;
}
cout << "\nInsertion Sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\nComparisons = " << comparisons;
cout << "\nExchanges = " << exchanges << endl;
}
void heapify(int arr[], int n, int i, int& comparisons, int& exchanges) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n) {
comparisons++;
if (arr[left] > arr[largest]) {
largest = left;
}
}
if (right < n) {
comparisons++;
if (arr[right] > arr[largest]) {
largest = right;
}
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
exchanges++;
heapify(arr, n, largest, comparisons, exchanges);
}
}
void heapSort(int arr[], int n) {
int comparisons = 0;
int exchanges = 0;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i, comparisons, exchanges);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
exchanges++;
heapify(arr, i, 0, comparisons, exchanges);
}
cout << "\nHeap Sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\nComparisons = " << comparisons;
cout << "\nExchanges = " << exchanges << endl;
}
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int* arr = new int[n];
cout << "Enter array elements: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int* bubble = new int[n];
int* selection = new int[n];
int* insertion = new int[n];
int* heap = new int[n];
for (int i = 0; i < n; i++) {
bubble[i] = arr[i];
selection[i] = arr[i];
insertion[i] = arr[i];
heap[i] = arr[i];
}
bubbleSort(bubble, n);
selectionSort(selection, n);
insertionSort(insertion, n);
heapSort(heap, n);
delete[] arr;
delete[] bubble;
delete[] selection;
delete[] insertion;
delete[] heap;
return 0;
}
Output
Exercise 13.2
Program
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
void bubbleSort(int arr[], int n, long long& comparisons, long long& exchanges) {
comparisons = 0;
exchanges = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
exchanges++;
}
}
}
}
void selectionSort(int arr[], int n, long long& comparisons, long long& exchanges) {
comparisons = 0;
exchanges = 0;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
comparisons++;
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
exchanges++;
}
}
}
void insertionSort(int arr[], int n, long long& comparisons, long long& exchanges) {
comparisons = 0;
exchanges = 0;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0) {
comparisons++;
if (arr[j] > key) {
arr[j + 1] = arr[j];
exchanges++;
j--;
}
else {
break;
}
}
arr[j + 1] = key;
}
}
void heapify(int arr[], int n, int i,
long long& comparisons,
long long& exchanges) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n) {
comparisons++;
if (arr[left] > arr[largest]) {
largest = left;
}
}
if (right < n) {
comparisons++;
if (arr[right] > arr[largest]) {
largest = right;
}
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
exchanges++;
heapify(arr, n, largest, comparisons, exchanges);
}
}
void heapSort(int arr[], int n,
long long& comparisons,
long long& exchanges) {
comparisons = 0;
exchanges = 0;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i, comparisons, exchanges);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
exchanges++;
heapify(arr, i, 0, comparisons, exchanges);
}
}
void copyArray(int source[], int destination[], int n) {
for (int i = 0; i < n; i++) {
destination[i] = source[i];
}
}
int main() {
srand(time(0));
int sizes[] = { 10, 100, 1000, 5000, 10000, 20000, 50000 };
cout << "N\tBubble(C)\tBubble(E)\tSelection(C)\tSelection(E)\tInsertion(C)\tInsertion(E)\tHeap(C)\
tHeap(E)\n";
for (int s = 0; s < 7; s++) {
int n = sizes[s];
int* original = new int[n];
for (int i = 0; i < n; i++) {
original[i] = rand() % 100000;
}
int* bubble = new int[n];
int* selection = new int[n];
int* insertion = new int[n];
int* heap = new int[n];
copyArray(original, bubble, n);
copyArray(original, selection, n);
copyArray(original, insertion, n);
copyArray(original, heap, n);
long long bc, be;
long long sc, se;
long long ic, ie;
long long hc, he;
bubbleSort(bubble, n, bc, be);
selectionSort(selection, n, sc, se);
insertionSort(insertion, n, ic, ie);
heapSort(heap, n, hc, he);
cout << n << "\t"
<< bc << "\t\t"
<< be << "\t\t"
<< sc << "\t\t"
<< se << "\t\t"
<< ic << "\t\t"
<< ie << "\t\t"
<< hc << "\t"
<< he << endl;
delete[] original;
delete[] bubble;
delete[] selection;
delete[] insertion;
delete[] heap;
}
return 0;
}
Output
N Bubble(C Bubble( Selection( Selection( Insertion( Insertion( Heap( Heap(
) E) C) E) C) E) C) E)
10 45 22 45 8 28 22 40 26
100 4950 2504 4950 94 2598 2504 1030 592
1000 499500 251109 499500 995 252102 251109 16845 9083
5000 12497500 6329525 12497500 4985 6334514 6329525 107832 57165
1000 49995000 2492903 49995000 9989 24939030 24929039 235482 124218
0 9
2000 19999000 9991292 19999000 19990 99932915 99912928 510700 268313
0 0 8 0
5000 12499750 6227594 12499750 49984 62280945 62275947 140958 737347
0 00 71 00 7 1 1
Exercise 13.2
Program
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
void insertionSort(int arr[], int n) {
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--;
}
arr[j + 1] = key;
}
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void copyArray(int source[], int destination[], int n) {
for (int i = 0; i < n; i++) {
destination[i] = source[i];
}
}
int main() {
srand(time(0));
int sizes[] = { 10, 100, 1000, 5000, 10000, 20000, 50000 };
cout << "N\tBubble(s)\tSelection(s)\tInsertion(s)\tHeap(s)\n";
for (int s = 0; s < 7; s++) {
int n = sizes[s];
int* original = new int[n];
for (int i = 0; i < n; i++) {
original[i] = rand() % 100000;
}
int* bubble = new int[n];
int* selection = new int[n];
int* insertion = new int[n];
int* heap = new int[n];
copyArray(original, bubble, n);
copyArray(original, selection, n);
copyArray(original, insertion, n);
copyArray(original, heap, n);
clock_t start, end;
start = clock();
bubbleSort(bubble, n);
end = clock();
double bubbleTime = double(end - start) / CLOCKS_PER_SEC;
start = clock();
selectionSort(selection, n);
end = clock();
double selectionTime = double(end - start) / CLOCKS_PER_SEC;
start = clock();
insertionSort(insertion, n);
end = clock();
double insertionTime = double(end - start) / CLOCKS_PER_SEC;
start = clock();
heapSort(heap, n);
end = clock();
double heapTime = double(end - start) / CLOCKS_PER_SEC;
cout << n << "\t"
<< bubbleTime << "\t\t"
<< selectionTime << "\t\t"
<< insertionTime << "\t\t"
<< heapTime << endl;
delete[] original;
delete[] bubble;
delete[] selection;
delete[] insertion;
delete[] heap;
}
return 0;
}
Output