Lab 3: Sorting Algorithms (CLO-2)
Course: Data Structures & Algorithms
Instructor: Daniya Jadoon
Objective
• To understand and implement basic sorting techniques.
• To analyze Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort.
• To compare their time and space complexities.
Theoretical Background with Algorithms & Code
1. Bubble Sort
Compare adjacent elements, swap if in wrong order. After each pass, the largest element
“bubbles” to the end.
Algorithm (Ascending Order):
1. Start with an array of size n.
2. For i = 0 to n-1:
o For j = 0 to n-i-1:
§ If arr[j] > arr[j+1], swap them.
3. Stop when no swaps occur (array is sorted).
Time Complexity:
• Best: O(n)
• Worst: O(n²)
• Space: O(1)
Code Example (C++):
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
bool swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) break; // optimization
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
2. Selection Sort
Idea: Repeatedly find the smallest element from unsorted part and move it to the front.
Algorithm (Ascending Order):
1. Start with an array of size n.
2. For i = 0 to n-2:
o Set minIndex = i.
o For j = i+1 to n-1:
§ If arr[j] < arr[minIndex], update minIndex = j.
o Swap arr[i] and arr[minIndex].
Time Complexity:
• Best: O(n²)
• Worst: O(n²)
• Space: O(1)
Code Example (C++):
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
3. Insertion Sort
Idea: Build a sorted list one element at a time by inserting each element into its proper place.
Algorithm (Ascending Order):
1. Start with an array of size n.
2. For i = 1 to n-1:
o Set key = arr[i].
o Set j = i-1.
o While j >= 0 and arr[j] > key:
§ Move arr[j] to arr[j+1].
§ Decrement j.
o Place key at arr[j+1].
Time Complexity:
• Best: O(n)
• Worst: O(n²)
• Space: O(1)
Code Example (C++):
#include <iostream>
using namespace std;
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;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
4. Merge Sort
Idea: Divide the array into two halves, sort each half recursively, then merge them.
This is a Divide and Conquer algorithm.
Algorithm (Ascending Order):
1. If array has 1 element → already sorted.
2. Find middle index m.
3. Recursively apply Merge Sort on left half and right half.
4. Merge the two halves:
o Compare elements from both halves.
o Place smaller one in new array.
o Repeat until all elements are merged.
Time Complexity:
• Best: O(n log n)
• Worst: O(n log n)
• Space: O(n)
Code Example (C++):
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n-1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
Practice Tasks
1. Modify Bubble Sort to arrange elements in descending order.
2. Count and print the number of comparisons and swaps in Bubble Sort.
3. Implement Selection Sort for sorting student names (strings).
4. Use Insertion Sort to sort an array of floating-point numbers.
5. Trace Merge Sort step by step for {38, 27, 43, 3, 9, 82, 10}.
6. Compare execution times of all four algorithms on arrays of size 10, 100, 1000.