The textbook introduces several sorting algorithms, each with different approaches and performance characteristics.

2.1 Selection Sort

Selection sort involves sorting by selecting the smallest (or largest) element from the unsorted portion and placing it at the beginning. The algorithm repeatedly finds the minimum element from the unsorted part and puts it at the beginning.

Algorithm steps:

1. Find the minimum element in the unsorted portion
2. Swap it with the first unsorted element
3. Move the boundary of the sorted portion one element to the right
4. Repeat until the entire array is sorted

C++ Implementation:

#include <iostream>
using namespace std;

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = 5;
    
    cout << "Original array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    // Selection sort
    for(int i = 0; i < n-1; i++) {
        int min_idx = i;
        for(int j = i+1; j < n; j++) {
            if(arr[j] < arr[min_idx])
                min_idx = j;
        }
        // Swap
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
    
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

Time Complexity: O(n²) — The algorithm makes n(n-1)/2 comparisons regardless of input order.

2.2 Insertion Sort

Insertion sort divides a list into sorted and unsorted sublists. It takes elements from the unsorted sublist and places them in the correct position in the sorted sublist. This is similar to how you might sort playing cards in your hand.

Algorithm steps:

1. Consider the first element as a sorted sublist
2. Take the next element and compare it with elements in the sorted sublist
3. Shift elements that are greater than the key to the right
4. Insert the key in its correct position

C++ Implementation (from textbook):

#include <iostream>
using namespace std;

int main() {
    int studentMarks[12] = {20, 45, 28, 24, 91, 55, 73, 80, 58, 99, 49, 45};
    int n = 12;
    
    cout << "Input list: ";
    for(int i = 0; i < n; i++) cout << studentMarks[i] << "\t";
    cout << endl;
    
    // Insertion sort
    for(int k = 1; k < n; k++) {
        int temp = studentMarks[k];
        int j = k - 1;
        
        while(j >= 0 && temp <= studentMarks[j]) {
            studentMarks[j + 1] = studentMarks[j];
            j = j - 1;
        }
        studentMarks[j + 1] = temp;
    }
    
    cout << "Sorted list: ";
    for(int i = 0; i < n; i++) cout << studentMarks[i] << "\t";
    cout << endl;
    
    return 0;
}

Time Complexity: O(n²) worst case, but O(n) best case when array is already sorted.

2.3 Bubble Sort

Bubble sort is a comparison-based algorithm that compares adjacent elements and swaps them if they are in the wrong order. The process repeats until the entire array is sorted. It is called "bubble sort" because smaller elements "bubble" to the top of the array.

Algorithm steps:

1. Compare the first and second element
2. If first element > second element, swap them
3. Move to the next pair and repeat
4. After one pass, the largest element is at the end
5. Repeat for the remaining unsorted portion

C++ Implementation (from textbook):

#include <iostream>
using namespace std;

int main() {
    int arr[50], n, i, j, temp;
    
    cout << "Enter size of array: ";
    cin >> n;
    
    cout << "Enter " << n << " numbers: " << endl;
    for(i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // Bubble sort
    for(i = 0; i < (n - 1); i++) {
        for(j = 0; j < (n - i - 1); j++) {
            if(arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    
    cout << "The sorted array is: " << endl;
    for(i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

Example: Sorting (5, 1, 12, 6, 23):

• Step 1: (5, 1, 12, 6, 23) → (1, 5, 12, 6, 23)
• Step 2: (1, 5, 12, 6, 23) → (1, 5, 12, 6, 23)
• Step 3: (1, 5, 12, 6, 23) → (1, 5, 6, 12, 23)

Advantages: Simple to understand, easy to implement, detects already sorted lists Limitations: Very slow for large datasets (O(n²))

2.4 Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by building a max-heap (or min-heap) and then repeatedly extracting the root element.

Key concepts:

• Max-heap: Parent node is always greater than or equal to children
• Heapify: Process of maintaining the heap property

C++ Implementation (from textbook):

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int root) {
    int largest = root;
    int l = 2 * root + 1;
    int r = 2 * root + 2;
    
    if(l < n && arr[l] > arr[largest])
        largest = l;
    if(r < n && arr[r] > arr[largest])
        largest = r;
    
    if(largest != root) {
        swap(arr[root], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Build max heap
    for(int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // Extract elements from heap
    for(int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int heap_arr[] = {11, 9, 6, 13, 2, 8};
    int n = sizeof(heap_arr)/sizeof(heap_arr[0]);
    
    cout << "Input array: ";
    for(int i = 0; i < n; i++) cout << heap_arr[i] << " ";
    cout << endl;
    
    heapSort(heap_arr, n);
    
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++) cout << heap_arr[i] << " ";
    cout << endl;
    
    return 0;
}

Time Complexity: Always O(n log n) regardless of input order

2.5 Quick Sort

Quick sort uses the divide-and-conquer technique. It selects a pivot element and partitions the array around the pivot—elements smaller than pivot go to the left, and larger elements go to the right. The sub-arrays are then sorted recursively.

Algorithm steps:

1. Select a pivot element
2. Partition: reorder elements so those less than pivot come before it
3. Recursively apply quick sort to left and right sub-arrays

C++ Implementation:

#include <iostream>
using namespace std;

int partition(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;
}

void quickSort(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);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;
    
    cout << "Original array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    quickSort(arr, 0, n - 1);
    
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

Advantages: Fast in practice, efficient for large datasets Limitations: Worst-case O(n²) when poor pivot is selected

2.6 Merge Sort

Merge sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts each half, and then merges the sorted halves. It guarantees O(n log n) performance.

Algorithm steps:

1. Divide the array into two halves
2. Recursively sort each half
3. Merge the two sorted halves

C++ Implementation:

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], 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, 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++;
    }
}

void mergeSort(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);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = 7;
    
    cout << "Original array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    mergeSort(arr, 0, n - 1);
    
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

Advantages: Consistent O(n log n) time, stable sort Limitations: Requires O(n) extra memory

When implementing sorting algorithms, you must analyze their performance based on several factors.

3.1 Time Complexity Comparison

3.2 Other Factors to Consider

Stability: A sorting algorithm is stable if it maintains the relative order of equal elements. Stable algorithms: Merge Sort, Insertion Sort, Bubble Sort. Unstable: Heap Sort, Quick Sort, Selection Sort.

Memory Usage:

• In-place: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort (O(1) extra space)
• Not in-place: Merge Sort (O(n) extra space)

3.3 Creating a Performance Report

A good performance report should include:

1. Test Data: Different sizes (small, medium, large arrays)
2. Measurement Method: Use time.h or <chrono> in C++ to measure execution time
3. Comparison Tables: Present results in organized tables
4. Analysis: Explain why certain algorithms perform better in specific scenarios

Example Performance Measurement Code:

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    int arr[] = {64, 25, 12, 22, 11, 90, 45, 33, 77, 88};
    int n = 10;
    
    // Record start time
    auto start = high_resolution_clock::now();
    
    // Sorting algorithm (e.g., bubble sort)
    for(int i = 0; i < n-1; i++) {
        for(int j = 0; j < n-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
    
    // Record end time
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    
    cout << "Execution time: " << duration.count() << " microseconds" << endl;
    
    return 0;
}

The choice depends on several factors:

• Data size: Quick Sort and Merge Sort for large datasets
• Data order: Insertion Sort works well for nearly sorted data
• Stability requirement: Use stable algorithms like Merge Sort
• Memory constraints: Use in-place algorithms like Heap Sort
• Consistency needed: Merge Sort guarantees O(n log n) always

In Tanzania, sorting algorithms are used in everyday applications such as mobile banking systems like M-Pesa, where transaction records need to be sorted by date and amount for quick retrieval. For example, a shopkeeper at a local market in Arusha managing inventory using a simple computer program would need to sort product prices in ascending order to identify the cheapest items, or sort sales records to determine which items sell most frequently. Understanding sorting algorithms helps developers create efficient systems for small businesses that handle hundreds or thousands of transactions daily.