Unit 4 of MAKAUT C Programming (PPS-II) contains high-weightage topics including 2D matrix mathematics, null-terminated string handling without library functions, and full implementations of 6 major sorting algorithms.

In MAKAUT semester exams, sorting algorithm derivations, time complexities, stability analyses, and matrix multiplication implementations carry up to 35 marks across Groups B and C.

---

1. 2D Arrays & Row-Major Memory Formulas

A 2D array is stored in Row-Major Order in C memory (rows stored sequentially).

Row-Major Address Formula:

Address(A[i][j]) = Base Address + (i × C + j) × sizeof(datatype)

where C is the total number of columns in the matrix.

Matrix Multiplication C Program (O(N^3))

*Exam Context: Group C (15 Marks)*

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3int main() {
4    int r1 = 2, c1 = 3, r2 = 3, c2 = 2;
5    int A[2][3] = {{1, 2, 3}, {4, 5, 6}};
6    int B[3][2] = {{7, 8}, {9, 1}, {2, 3}};
7    int C[2][2] = {0};
8 
9    if (c1 != r2) {
10        printf("Matrix multiplication invalid! Columns of A must equal Rows of B.\n");
11        return 1;
12    }
13 
14    // Matrix Multiplication Algorithm
15    for (int i = 0; i < r1; i++) {
16        for (int j = 0; j < c2; j++) {
17            for (int k = 0; k < c1; k++) {
18                C[i][j] += A[i][k] * B[k][j];
19            }
20        }
21    }
22 
23    printf("Resultant Product Matrix:\n");
24    for (int i = 0; i < r1; i++) {
25        for (int j = 0; j < c2; j++) {
26            printf("%d ", C[i][j]);
27        }
28        printf("\n");
29    }
30    return 0;
31}

---

2. String Manipulation Without Library Functions

In C, a string is a 1D char array terminated by null byte '\0'.

Custom strcpy and strcat Pointer Implementation

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3void customStrcpy(char *dest, const char *src) {
4    while (*src != '\0') {
5        *dest = *src;
6        dest++;
7        src++;
8    }
9    *dest = '\0';
10}
11 
12void customStrcat(char *dest, const char *src) {
13    while (*dest != '\0') dest++;
14    while (*src != '\0') {
15        *dest = *src;
16        dest++;
17        src++;
18    }
19    *dest = '\0';
20}

---

3. Masterclass: 6 Sorting Algorithms Implementations

1. Bubble Sort (Optimized with Swapped Flag)

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3void bubbleSort(int arr[], int n) {
4    for (int i = 0; i < n - 1; i++) {
5        int swapped = 0;
6        for (int j = 0; j < n - i - 1; j++) {
7            if (arr[j] > arr[j + 1]) {
8                int temp = arr[j];
9                arr[j] = arr[j + 1];
10                arr[j + 1] = temp;
11                swapped = 1;
12            }
13        }
14        if (!swapped) break; // Array is already sorted
15    }
16}

---

2. Selection Sort

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3void selectionSort(int arr[], int n) {
4    for (int i = 0; i < n - 1; i++) {
5        int minIdx = i;
6        for (int j = i + 1; j < n; j++) {
7            if (arr[j] < arr[minIdx]) minIdx = j;
8        }
9        int temp = arr[minIdx];
10        arr[minIdx] = arr[i];
11        arr[i] = temp;
12    }
13}

---

3. Insertion Sort

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3void insertionSort(int arr[], int n) {
4    for (int i = 1; i < n; i++) {
5        int key = arr[i];
6        int j = i - 1;
7        while (j >= 0 && arr[j] > key) {
8            arr[j + 1] = arr[j];
9            j--;
10        }
11        arr[j + 1] = key;
12    }
13}

---

4. Quick Sort (Lomuto Partitioning - Divide & Conquer)

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3int partition(int arr[], int low, int high) {
4    int pivot = arr[high];
5    int i = (low - 1);
6 
7    for (int j = low; j < high; j++) {
8        if (arr[j] < pivot) {
9            i++;
10            int temp = arr[i];
11            arr[i] = arr[j];
12            arr[j] = temp;
13        }
14    }
15    int temp = arr[i + 1];
16    arr[i + 1] = arr[high];
17    arr[high] = temp;
18    return (i + 1);
19}
20 
21void quickSort(int arr[], int low, int high) {
22    if (low < high) {
23        int pi = partition(arr, low, high);
24        quickSort(arr, low, pi - 1);
25        quickSort(arr, pi + 1, high);
26    }
27}

---

5. Merge Sort (Divide & Conquer)

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3void merge(int arr[], int l, int m, int r) {
4    int n1 = m - l + 1;
5    int n2 = r - m;
6    int L[n1], R[n2];
7 
8    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
9    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
10 
11    int i = 0, j = 0, k = l;
12    while (i < n1 && j < n2) {
13        if (L[i] <= R[j]) arr[k++] = L[i++];
14        else arr[k++] = R[j++];
15    }
16    while (i < n1) arr[k++] = L[i++];
17    while (j < n2) arr[k++] = R[j++];
18}
19 
20void mergeSort(int arr[], int l, int r) {
21    if (l < r) {
22        int m = l + (r - l) / 2;
23        mergeSort(arr, l, m);
24        mergeSort(arr, m + 1, r);
25        merge(arr, l, m, r);
26    }
27}

---

4. Master Comparison Table of Sorting Algorithms

AlgorithmBest TimeAverage TimeWorst TimeAuxiliary SpaceStability
Bubble SortO(N)O(N^2)O(N^2)O(1)Stable
Selection SortO(N^2)O(N^2)O(N^2)O(1)Unstable
Insertion SortO(N)O(N^2)O(N^2)O(1)Stable
Quick SortO(N \log N)O(N \log N)O(N^2)O(\log N)Unstable
Merge SortO(N \log N)O(N \log N)O(N \log N)O(N)Stable
Shell SortO(N \log N)O(N^{1.3})O(N^2)O(1)Unstable