Laboratory 9 – Sorting Arrays of Strings

Laboratory Overview

What is new in this laboratory.

In the previous lab, you sorted arrays of long. In this laboratory, you will sort arrays of strings. At first glance, the algorithm seems to be the same, but the comparison logic is different: strings must be compared using functions such as strcmp, not with operators like > or <.

Main idea of this lab:

same algorithm → new data type → correct comparison → reusable library function

This laboratory is an important bridge between type-specific sorting functions and the next step: fully universal sorting functions with an interface similar to qsort.

Learning Outcomes

explain the difference between sorting numbers and sorting strings,
use strcmp to compare text values correctly,
implement bubble sort and insertion sort for arrays of char *,
test sorting on static arrays of strings,
test sorting on dynamic arrays of strings,
allocate memory for an array of pointers and for individual strings,
free all dynamically allocated memory correctly,
extend array.h and libarray.a with new string-sorting functions.

How this laboratory continues Lab 8

The algorithmic idea stays almost the same, but the data type changes.

Lab 8	Lab 9
sorting arrays of `long`	sorting arrays of `char *`
comparison with `>`	comparison with `strcmp`
swapping numeric values	swapping pointers to strings
`bsort_l`, `isort_l`	`bsort_s`, `isort_s`

File numbering convention: Laboratory 8 ended with ex29. This laboratory continues the numbering with ex30–ex33.

Do not compare strings with > or <. These operators compare addresses, not alphabetical order. Use strcmp from <string.h>.

Task 0 — Reminder and preparation

Shown. Log in to the AGH server and prepare the working directory.

Step 1 — Log in to the AGH UNIX server

ssh your_login@student.agh.edu.pl

Step 2 — Go to the course directory

cd ~/I2PL

Step 3 — Create the directory for Laboratory 9

mkdir lab9
cd lab9

Step 4 — General rules

Work only in ~/I2PL/lab9.
Do not use global variables.
Keep function declarations in array.h.
Store each new sorting function in its own source file.
Compile with warnings enabled.
After free, set unused pointers to NULL.

gcc -Wall program.c -o program

This laboratory continues the library-based workflow from the previous lab, but the new challenge is working with char * safely and clearly.

Task 1 — Understand what is being sorted

Shown. Before writing code, make sure you understand the data representation.

Step 1 — Array of strings

A typical static array of strings may look like this:

char * array[] = { "Dog", "Cat", "Horse", "Pig", "Fish" };

Step 2 — Important observation

The array stores pointers to strings, not single characters and not one large text block. When sorting, you usually swap pointers, not the contents of whole strings.

The comparison array[i] > array[j] compares addresses, not alphabetical order. To compare strings lexicographically, use strcmp from string.h.

Task 2 — Extend `array.h` with string-sorting declarations

Complete. Add declarations for the new functions that sort arrays of char *.

Step 1 — Open the header file

nano array.h

Step 2 — Add declarations

void bsort_s(char * tab[], int size);
void isort_s(char * tab[], int size);

Use the suffix _s to indicate that these functions work on arrays of strings.

Task 3 — Implement bubble sort for strings

Implement yourself. Write a bubble sort function that uses strcmp for comparisons.

Step 1 — Create the file

nano bsort_s.c

Step 2 — Include required headers

#include <string.h>
#include "array.h"

Step 3 — Implement the algorithm

void bsort_s(char * tab[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (strcmp(tab[j], tab[j + 1]) > 0) {
                char * tmp = tab[j];
                tab[j] = tab[j + 1];
                tab[j + 1] = tmp;
            }
        }
    }
}

Bubble sort logic stays the same. Only the comparison changes from numeric comparison to strcmp(...).

Task 4 — Implement insertion sort for strings

Implement yourself. Write the second algorithm for arrays of char *.

Step 1 — Create the file

nano isort_s.c

Step 2 — Implement insertion sort

void isort_s(char * tab[], int size) {
    for (int i = 1; i < size; i++) {
        char * value = tab[i];
        int j = i - 1;

        while (j >= 0 && strcmp(tab[j], value) > 0) {
            tab[j + 1] = tab[j];
            j--;
        }

        tab[j + 1] = value;
    }
}

Again, you are moving pointers, not copying full strings character by character.

Task 5 — Test sorting on a static array of strings

Implement yourself. Create two testing programs using a static array of text values.

Step 1 — Create the first test program

nano ex30_bubble_string.c

Step 2 — Define a static array

char * array[] = { "Dog", "Cat", "Horse", "Pig", "Fish" };

Step 3 — Compute its size

int size = sizeof(array) / sizeof(char *);

Step 4 — Print before and after sorting

Display the array before sorting, call bsort_s, and display the result after sorting.

Step 5 — Create the second test program

nano ex31_insertion_string.c

Repeat the same idea, but call isort_s.

These tests are intentionally simple. At this stage, the goal is to verify that your sorting logic is correct before adding dynamic allocation.

Task 6 — Build dynamic arrays of strings

Shown + complete. Prepare the data structure needed for user-provided text values.

Step 1 — Ask for the array size

int size;
printf("Enter the size of the array: ");
scanf("%d", &size);

Step 2 — Allocate the array of pointers

char ** array = calloc(size, sizeof(char *));

Step 3 — Read individual strings

There are several valid approaches. One simple course-friendly solution is to use a temporary buffer, then allocate exactly enough space for each string.

char buffer[256];
scanf("%255s", buffer);

Step 4 — Allocate space for one string and copy it

array[i] = malloc(strlen(buffer) + 1);
strcpy(array[i], buffer);

If you store only the address of the temporary buffer, every element will refer to the same memory area. Each string needs its own allocated space.

Task 7 — Test sorting on a dynamic array of strings

Implement yourself. Create two testing programs that read strings from the user and sort them.

Step 1 — Create the first dynamic test program

nano ex32_bubble_string_dynamic.c

Step 2 — Read values from the user

Ask for the array size, then read each string in a loop and store it in dynamically allocated memory.

Step 3 — Print before and after sorting

Display the entered strings, call bsort_s, then display the sorted order.

Step 4 — Create the second dynamic test program

nano ex33_insertion_string_dynamic.c

Repeat the same idea, but use isort_s.

Step 5 — Release all allocated memory

for (int i = 0; i < size; i++) {
    free(array[i]);
    array[i] = NULL;
}
free(array);
array = NULL;

Freeing only the outer array is not enough. Each individual string was allocated separately.

Task 8 — Compile and extend `libarray.a`

Shown. Compile the new source files and add them to the static library.

Step 1 — Compile the sorting functions

gcc -Wall -c bsort_s.c
gcc -Wall -c isort_s.c

Step 2 — Update the library

ar rcs libarray.a print_l.o randomize_l.o statistics_l.o bsort_l.o isort_l.o bsort_s.o isort_s.o

Step 3 — Compile a testing program

gcc -Wall ex30_bubble_string.c -L. -larray -o ex30_bubble_string

The string-sorting functions now become part of the same library as your earlier array utilities.

Task 9 — Compare the string version with the numeric version

Reflect on what stayed the same and what changed.

Aspect	Sorting `long`	Sorting `char *`
Array element type	`long`	`char *`
Comparison	`a > b`	`strcmp(a, b) > 0`
Swap / move	values	pointers
Dynamic allocation	one block of numbers	array of pointers + strings

The sorting algorithm itself is still basically the same. The hard part is understanding the data model.

Task 10 — Suggested experiments

Use small experiments to verify that your understanding is correct.

Test strings that start with the same prefix, e.g. cat, catalog, caterpillar.
Test uppercase and lowercase words, e.g. Dog and dog.
Test duplicate values.
Test size 0 and size 1.
Test whether all allocated memory is released correctly.

A good test set should include not only “normal” input, but also edge cases and repeated values.

Summary

After this laboratory, your array library supports sorting both numbers and strings with two different algorithms. This is the last step before building universal sorting functions with a declaration similar to qsort.

Natural next step:

type-specific sorting → comparison function → void * + width + compar → qsort-like interface

Quick Summary

Main topic: sorting arrays of strings
Algorithms: bubble sort, insertion sort
New type: char *
Comparison: strcmp
Library: extend libarray.a from Lab 8

Suggested File Set

array.h

bsort_s.c
isort_s.c

ex30_bubble_string.c
ex31_insertion_string.c
ex32_bubble_string_dynamic.c
ex33_insertion_string_dynamic.c

bsort_s.o
isort_s.o
libarray.a

Recommended Compile Sequence

gcc -Wall -c bsort_s.c
gcc -Wall -c isort_s.c

ar rcs libarray.a print_l.o randomize_l.o statistics_l.o bsort_l.o isort_l.o bsort_s.o isort_s.o

gcc -Wall ex30_bubble_string.c -L. -larray -o ex30_bubble_string
gcc -Wall ex31_insertion_string.c -L. -larray -o ex31_insertion_string
gcc -Wall ex32_bubble_string_dynamic.c -L. -larray -o ex32_bubble_string_dynamic
gcc -Wall ex33_insertion_string_dynamic.c -L. -larray -o ex33_insertion_string_dynamic

Important Reminder

if (strcmp(tab[j], tab[j + 1]) > 0) {
    char * tmp = tab[j];
    tab[j] = tab[j + 1];
    tab[j + 1] = tmp;
}

Compare strings with strcmp, then swap the pointers.

Common Mistakes

using > instead of strcmp
forgetting #include <string.h>
freeing only the outer array
storing all strings in the same temporary buffer
forgetting the null terminator when allocating memory

Laboratory Overview

Learning Outcomes

How this laboratory continues Lab 8

Task 0 — Reminder and preparation

Step 1 — Log in to the AGH UNIX server

Step 2 — Go to the course directory

Step 3 — Create the directory for Laboratory 9

Step 4 — General rules

Task 1 — Understand what is being sorted

Step 1 — Array of strings

Step 2 — Important observation

Task 2 — Extend array.h with string-sorting declarations

Step 1 — Open the header file

Step 2 — Add declarations

Task 3 — Implement bubble sort for strings

Step 1 — Create the file

Step 2 — Include required headers

Step 3 — Implement the algorithm

Task 4 — Implement insertion sort for strings

Step 1 — Create the file

Step 2 — Implement insertion sort

Task 5 — Test sorting on a static array of strings

Step 1 — Create the first test program

Step 2 — Define a static array

Step 3 — Compute its size

Step 4 — Print before and after sorting

Step 5 — Create the second test program

Task 6 — Build dynamic arrays of strings

Step 1 — Ask for the array size

Step 2 — Allocate the array of pointers

Step 3 — Read individual strings

Step 4 — Allocate space for one string and copy it

Task 7 — Test sorting on a dynamic array of strings

Step 1 — Create the first dynamic test program

Step 2 — Read values from the user

Step 3 — Print before and after sorting

Step 4 — Create the second dynamic test program

Step 5 — Release all allocated memory

Task 8 — Compile and extend libarray.a

Step 1 — Compile the sorting functions

Step 2 — Update the library

Step 3 — Compile a testing program

Task 9 — Compare the string version with the numeric version

Task 10 — Suggested experiments

Summary

Task 2 — Extend `array.h` with string-sorting declarations

Task 8 — Compile and extend `libarray.a`