Practice: Arrays and Functions
No matter how many techniques you learn, they are just theory until you step into the ring. This chapter integrates arrays, functions, and pointers through four hands-on projects to test your real skills.
Project 1: Bubble Sort
Bubble sort is the most basic sorting algorithm. The idea is to repeatedly traverse the array, comparing adjacent elements and swapping them if they are in the wrong order, until no swaps occur. Each pass "bubbles" the current largest value to the end.
Algorithm Steps
- Start from the first element and compare each pair of adjacent elements
- If the left element is greater than the right, swap them
- After one pass, the largest value is in its correct position
- Repeat for the remaining portion until fully sorted
Implementation
C
#include <stdio.h>
void bubble_sort(int *arr, int len) {
int i, j;
int swapped;
for (i = 0; i < len - 1; i++) {
swapped = 0;
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break;
}
}
void print_array(const int *arr, int len) {
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void) {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int len = sizeof(data) / sizeof(data[0]);
printf("Before: ");
print_array(data, len);
bubble_sort(data, len);
printf("After: ");
print_array(data, len);
return 0;
}
TEXT
Before: 64 34 25 12 22 11 90
After: 11 12 22 25 34 64 90
The swapped flag optimization: if no swaps occur during a pass, the array is already sorted and the algorithm terminates early. In the best case (already sorted), the time complexity drops to O(n).
💡 Tip: Bubble sort has average and worst-case time complexity of O(n^2), suitable only for small datasets or teaching. Use
qsort in real projects.
Example
Sort scores in descending order using bubble sort:
C
#include <stdio.h>
void sort_desc(int *arr, int len) {
int i, j, swapped;
for (i = 0; i < len - 1; i++) {
swapped = 0;
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break;
}
}
int main(void) {
int scores[] = {85, 92, 78, 95, 88};
int len = sizeof(scores) / sizeof(scores[0]);
int i;
sort_desc(scores, len);
printf("Ranking: ");
for (i = 0; i < len; i++) {
printf("%d ", scores[i]);
}
printf("\n");
return 0;
}
TEXT
Ranking: 95 92 88 85 78
For descending order, simply change the comparison from > to <.
Project 2: Binary Search
Binary search efficiently locates a target value in a sorted array by halving the search range each step.
Algorithm Steps
- Set the search range to
[low, high] - Calculate the middle position:
mid = (low + high) / 2 - If
arr[mid]equals the target, it is found - If
arr[mid]is less than the target, search the right half - If
arr[mid]is greater than the target, search the left half - If the range shrinks to empty without finding, the target does not exist
Implementation
C
#include <stdio.h>
int binary_search(const int *arr, int len, int target) {
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main(void) {
int data[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 78};
int len = sizeof(data) / sizeof(data[0]);
int targets[] = {23, 7, 78, 1};
int num = sizeof(targets) / sizeof(targets[0]);
int i;
for (i = 0; i < num; i++) {
int pos = binary_search(data, len, targets[i]);
if (pos >= 0) {
printf("%d found at index %d\n", targets[i], pos);
} else {
printf("%d not found\n", targets[i]);
}
}
return 0;
}
TEXT
23 found at index 5
7 not found
78 found at index 9
1 not found
💡 Tip: Use
low + (high - low) / 2 instead of (low + high) / 2 to avoid integer overflow. This is a classic binary search detail.
Time complexity is O(log n); 1 billion elements require at most 30 comparisons.
Example
Find the position of the first element greater than or equal to the target (lower bound search):
C
#include <stdio.h>
int lower_bound(const int *arr, int len, int target) {
int low = 0;
int high = len;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int main(void) {
int data[] = {1, 3, 3, 5, 7, 7, 7, 9, 11};
int len = sizeof(data) / sizeof(data[0]);
int pos = lower_bound(data, len, 7);
printf("First >= 7 at index %d, value=%d\n", pos, data[pos]);
return 0;
}
TEXT
First >= 7 at index 4, value=7
Lower bound search is extremely common in competitive programming and the STL.
Project 3: String Reversal
Swap the front and back characters of a string, e.g., "hello" becomes "olleh". Use the two-pointer technique for in-place operation, no extra array needed.
Implementation
C
#include <stdio.h>
#include <string.h>
void str_reverse(char *s) {
char *left = s;
char *right = s + strlen(s) - 1;
while (left < right) {
char temp = *left;
*left = *right;
*right = temp;
left++;
right--;
}
}
int main(void) {
char s1[] = "Hello World";
char s2[] = "ABCDE";
char s3[] = "racecar";
str_reverse(s1);
str_reverse(s2);
str_reverse(s3);
printf("%s\n", s1);
printf("%s\n", s2);
printf("%s\n", s3);
return 0;
}
TEXT
dlroW olleH
EDCBA
racecar
Note: you must use a character array (modifiable), not a pointer to a string literal.
Example
Check whether a string is a palindrome (skipping non-alphanumeric characters, ignoring case):
C
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int is_palindrome(const char *s) {
const char *left = s;
const char *right = s + strlen(s) - 1;
while (left < right) {
while (left < right && !isalnum((unsigned char)*left)) left++;
while (left < right && !isalnum((unsigned char)*right)) right--;
if (tolower((unsigned char)*left) != tolower((unsigned char)*right)) {
return 0;
}
left++;
right--;
}
return 1;
}
int main(void) {
printf("%d\n", is_palindrome("racecar"));
printf("%d\n", is_palindrome("hello"));
printf("%d\n", is_palindrome("A man a plan a canal Panama"));
return 0;
}
TEXT
1
0
1
Project 4: Character Frequency Analysis
Count how many times each character appears in a string -- a fundamental text analysis operation.
Implementation
C
#include <stdio.h>
#include <string.h>
void char_freq(const char *s, int *freq, int size) {
int i;
for (i = 0; i < size; i++) freq[i] = 0;
while (*s != '\0') {
unsigned char ch = (unsigned char)*s;
if (ch < (unsigned)size) freq[ch]++;
s++;
}
}
int main(void) {
char text[] = "Hello World!";
int freq[256] = {0};
int i;
char_freq(text, freq, 256);
for (i = 32; i < 127; i++) {
if (freq[i] > 0) printf("'%c': %d ", i, freq[i]);
}
printf("\n");
return 0;
}
TEXT
' ': 1 '!': 1 'H': 1 'W': 1 'd': 1 'e': 1 'l': 3 'o': 2 'r': 1
Using ASCII values as array subscripts, a single pass completes the count. 256 slots cover all 8-bit characters.
Example
Count letter frequencies and find the most frequent letter:
C
#include <stdio.h>
#include <ctype.h>
#include <string.h>
void letter_freq(const char *s, int *freq) {
int i;
for (i = 0; i < 26; i++) freq[i] = 0;
while (*s != '\0') {
if (isalpha((unsigned char)*s)) {
freq[tolower((unsigned char)*s) - 'a']++;
}
s++;
}
}
char find_max(const int *freq, int size) {
int max_idx = 0;
int i;
for (i = 1; i < size; i++) {
if (freq[i] > freq[max_idx]) max_idx = i;
}
return 'a' + max_idx;
}
int main(void) {
const char *text = "The quick brown fox jumps over the lazy dog";
int freq[26];
letter_freq(text, freq);
char max_ch = find_max(freq, 26);
printf("Most frequent letter: %c (%d times)\n", max_ch, freq[max_ch - 'a']);
return 0;
}
TEXT
Most frequent letter: o (4 times)
❓ FAQ
Q Which is better, bubble sort or selection sort?
A Both have O(n^2) time complexity, but bubble sort has an early termination optimization with O(n) best case. The practical difference is small; neither is suitable for large datasets.
Q What are the prerequisites for binary search?
A The array must be sorted and support random access. Linked lists cannot use binary search because you cannot access the middle element in O(1).
Q Is there a library function for string reversal?
A The C standard library does not have a direct reverse function. C++ has
std::reverse in <algorithm>; in C, you must implement it yourself.Q Why use a 256-element array for frequency counting?
A unsigned char ranges from 0 to 255, totaling 256 values. Using the character's ASCII value as an index, 256 slots cover all possible characters, and a single pass completes the count.
📖 Summary
- Bubble sort sorts by swapping adjacent elements; the swapped flag enables early termination
- Binary search requires a sorted array; O(log n) efficiency far exceeds linear search
- The two-pointer technique reverses strings in-place with O(1) space complexity
- Character frequency analysis uses ASCII values as array subscripts, completing in one pass
- These projects demonstrate the three core skills: array storage, function encapsulation, and pointer manipulation
📝 Exercises
- Enhance bubble sort: implement a function that can sort in either ascending or descending order, controlled by a function pointer parameter.
- Implement a recursive version of binary search:
int bin_search_rec(const int *arr, int low, int high, int target). - Write an enhanced character frequency analyzer: read a line of user input, then output the top 3 most frequent characters and their counts.