Sorting | Time and Space Analysis | Lecture 11 | C Programming

Sorting Algorithms in C are important techniques for organising data efficiently and improving the performance of searching and data-processing operations. Understanding how different sorting methods work helps programmers write optimised and scalable applications. In this lecture, you'll explore Bubble Sort, Selection Sort, and Insertion Sort, along with their implementation, space and time complexity, stability, and real-world use cases.

What are Sorting Algorithms in C?

When managing raw data arrays, a core challenge is structuring them logically. Unordered values slow down search operations and look disorganised. The definitive solution is implementing sorting algorithms to rearrange data sequentially into ascending or descending orders.

Choosing the right approach relies heavily on space and time complexity analysis. These performance indicators ensure your software operates smoothly even as input data scales up dramatically.

Space and Time Complexity of Sorting Algorithms in C

To build software like a professional programmer, you must evaluate code performance scientifically instead of measuring execution time in seconds. A single script will execute much faster on a top-tier modern processor than on an older machine. Programmers use Big O notation to evaluate software fairly based on how the total number of operations grows alongside input sizes.

Measuring Execution with Big O Notation

Big O notation evaluates the performance of a code pattern relative to an input size of N elements. While evaluating algorithms, we isolate the highest algebraic degree and discard unnecessary constant multipliers. For example:

• Linear growth: A simple single loop running N times simplifies straight to O(N).

• Quadratic growth: A nested structure where a secondary loop runs N times inside a primary loop running N times scales at O(N²).

• Constant behavior: Code that executes a fixed number of operations regardless of array size is denoted as O(1).

Space Efficiency vs Auxiliary Memory

Optimising your architecture is a trade-off between memory usage and raw speed. Space Complexity of an Algorithm: It is the memory space required by an algorithm for execution.

If the operational approach includes the program creating a secondary array of length N equal to the source for data manipulation, its spatial scaling is O(N). But if the algorithm swaps values in place in the existing source locations, it needs no additional storage. This zero-allocation mechanism takes $O(1)$ constant space.

How to Implement Bubble Sorting Algorithms in C

The bubble sort strategy works by comparing adjacent items sequentially in an array. If the left hand element is bigger than its right hand partner they swap places. The array has repeating sequences of matches, so the largest values bubble up to the highest indexes.

C

#include <stdio.h>

#include <stdbool.h>

void bubbleSort(int arr[], int n) {

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

       bool flag = true; // Tracks if swaps happen

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

           if (arr[j] > arr[j + 1]) {

               int temp = arr[j];

               arr[j] = arr[j + 1];

               arr[j + 1] = temp;

               flag = false; // Swap occurred

           }

       }

       if (flag) break; // Exit early if already sorted

   }

}

Performance Profiles of Bubble Sort

• Worst-Case Time Complexity: O(N²) occurs when the data set starts in exact reverse order.

• Best-Case Time Complexity: O(N) is achieved when the input array arrives completely presorted, allowing our optimised flag variable to trigger an early exit after one pass.

• Space Analysis: O(1) auxiliary storage because all data mutations happen directly inside the original array block.

• Algorithm Stability: Highly stable. Items with identical values preserve their initial relative alignment because the conditional operation ignores equal variables.

How to Implement Selection Sorting Algorithms in C

Selection sort conceptually divides an array into a sorted boundary and an unsorted boundary. Then the program in each iteration goes through the rest of the unsorted values to find the absolute smallest value. When this minimum value is found, it is swapped with the first element of the unsorted section, and the boundary of the sorted section is increased by one.

C

#include <stdio.h>

#include <limits.h>

void selectionSort(int arr[], int n) {

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

       int minIdx = i;

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

           if (arr[j] < arr[minIdx]) {

               minIdx = j;

           }

       }

       int temp = arr[minIdx];

       arr[minIdx] = arr[i];

       arr[i] = temp;

   }

}

Performance Profiles of Selection Sort

• Worst-Case Time Complexity: O(N²) occurs as the program must scan the unsorted section to find the minimum value, regardless of the initial order.

• Best-Case Time Complexity: O(N²) remains unchanged because the code always scans every unsorted element to confirm it has found the true minimum value.

• Space Complexity Analysis: O(1) since data modifications happen strictly within the original indices.

• Algorithm Stability: Unstable. The long-distance swapping mechanism can jump equal values over one another, altering their original relative order.

How to Implement Insertion Sorting Algorithms in C

The insertion sort technique builds a sorted array section element by element. It picks the next unsorted value and shifts it backward through the sorted section until it reaches its correct relative position, matching how a card player orders a hand of playing cards.

C

#include <stdio.h>

void insertionSort(int arr[], int n) {

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

       int j = i;

       while (j >= 1 && arr[j] < arr[j - 1]) {

           int temp = arr[j];

           arr[j] = arr[j - 1];

           arr[j - 1] = temp;

           j--;

       }

   }

}

Performance Profiles of Insertion Sort

• Worst-Case Time Complexity: O(N²) occurs when an array is completely reversed, forcing every element to shift backward through the entire sorted section.

• Best-Case Time Complexity: O(N) is achieved when the data is pre-sorted. The interior conditional check fails immediately on each pass, preventing unnecessary value shifts.

• Memory Requirements: O(1) memory footprint since elements are sorted in place.

• Algorithm Stability: Extremely stable. Equal values stop shifting as soon as they encounter an identical partner, preserving their original order.

Sorting Algorithms in C Comparison

When choosing between sorting techniques, an absolute comparison matrix will make clear which sorting technique is the best fit for the particular computational requirements.

The following data table shows the trade-offs for these standard algorithms in operation: