Laboratory 8 – Sorting Arrays of Long Integers

Laboratory Overview

What is new in this laboratory.

In this laboratory, you will move from file processing to a new family of problems: sorting. Instead of solving one isolated exercise, you will implement two complete sorting algorithms, test them on different kinds of arrays, and then add them to your existing array library.

Main idea of this lab:

algorithm → test on static array → test on dynamic array → library function

The selected data type for this laboratory is long. This keeps the comparison logic simple, so that the main focus remains on the algorithms themselves and on writing clean reusable functions.

Learning Outcomes

explain the basic idea of bubble sort and insertion sort,
implement sorting functions for arrays of long,
test sorting algorithms on static arrays,
test sorting algorithms on dynamic arrays allocated with malloc or calloc,
reuse previously written library functions such as randomize_l,
extend array.h and libarray.a with new functions,
print arrays before and after sorting and verify correctness experimentally.

How this laboratory continues Lab 7

You will reuse the array module created in Laboratory 7 and extend it with sorting functions.

Part from Lab 7	Used in Lab 8 for
`array.h`	Adding declarations of `bsort_l` and `isort_l`.
`print_l`	Printing arrays before and after sorting.
`randomize_l`	Generating test data for dynamic arrays.
`libarray.a`	Rebuilding the library with new sorting object files.

File numbering convention: Laboratory 7 ended with ex25.c. This laboratory continues the numbering with ex26–ex29.

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 8

mkdir lab8
cd lab8

Step 4 — General rules

Work only in ~/I2PL/lab8.
Do not use global variables.
Keep all function declarations in array.h.
Store each sorting function in a separate source file.
Compile with warnings enabled.

gcc -Wall program.c -o program

This laboratory continues the library-oriented workflow from previous labs: separate declarations, separate definitions, object files, and a reusable static library.

Task 1 — Read about the selected algorithms

Shown. Before coding, understand the logic of the two algorithms used in this lab.

Step 1 — Bubble sort

Bubble sort repeatedly compares neighbouring elements and swaps them if they are in the wrong order. Larger values “bubble” toward the end of the array.

Step 2 — Insertion sort

Insertion sort grows a sorted prefix of the array. In each step, one element is inserted into the correct position among the already sorted values.

Both algorithms are simple enough to implement by hand and good for learning, even though they are not the fastest methods for large inputs.

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

Complete. Add declarations for the new sorting functions working on arrays of long.

Step 1 — Open the header file

nano array.h

Step 2 — Add declarations

void bsort_l(long tab[], int size);
void isort_l(long tab[], int size);

Use the suffix _l to make it clear that these functions sort arrays of type long.

Task 3 — Implement bubble sort for `long`

Implement yourself. Write the first sorting function and store it in its own source file.

Step 1 — Create the file

nano bsort_l.c

Step 2 — Include the header

#include "array.h"

Step 3 — Implement bubble sort

A good starting point is the following structure:

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

Use long for the temporary variable as well. Do not accidentally reduce the type to int.

Task 4 — Implement insertion sort for `long`

Implement yourself. Write the second sorting function and compare its logic with bubble sort.

Step 1 — Create the file

nano isort_l.c

Step 2 — Implement insertion sort

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

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

        tab[j + 1] = value;
    }
}

Bubble sort is based on repeated swapping. Insertion sort is based on shifting values and inserting one element.

Task 5 — Test sorting on a static array

Implement yourself. Create two testing programs that sort static arrays of long.

Step 1 — Create the first test program

nano ex26_bubble_long.c

Step 2 — Define a static array

long array[] = { 12, 10, -12, 3, 4, 3, 1, -100, -12 };

Step 3 — Compute its size with `sizeof`

int size = sizeof(array) / sizeof(long);

Step 4 — Print before and after sorting

Display the whole array before sorting, call bsort_l, then display the sorted array.

Step 5 — Create the second test program

nano ex27_insertion_long.c

Repeat the same idea, but use isort_l.

The testing program names should contain the algorithm name so that their purpose is immediately visible.

Task 6 — Test sorting on a dynamic array

Implement yourself. Create two programs that allocate arrays dynamically and fill them with random values.

Step 1 — Create the first dynamic test

nano ex28_bubble_long.c

Step 2 — Ask the user for the size

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

Step 3 — Allocate memory

long *array = malloc(size * sizeof(long));

or:

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

Step 4 — Fill the array with random values

Reuse the randomize function from your library.

randomize_l(array, size, -100, 100);

Step 5 — Print, sort, print again

Display the array before sorting and after sorting.

Step 6 — Free memory correctly

free(array);
array = NULL;

Step 7 — Prepare the second dynamic test

nano ex29_insertion_long.c

Repeat the same idea, but use isort_l.

Dynamic memory must always be released. After calling free, set the pointer to NULL.

Task 7 — Print arrays in a reusable way

To avoid duplication, create a helper function for displaying arrays.

Step 1 — Write a helper function

void print_long_array(long tab[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%ld ", tab[i]);
    }
    printf("\n");
}

This function does not belong to the sorting library yet. It may stay inside the testing programs.

Task 8 — Compile the object files and update the library

Shown. Compile each source file separately and rebuild libarray.a.

Step 1 — Compile the sorting functions

gcc -Wall -c bsort_l.c
gcc -Wall -c isort_l.c

Step 2 — Update the library archive

ar rcs libarray.a bsort_l.o isort_l.o

Step 3 — Compile a testing program with the library

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

Review the meaning of the -L and -l options used by gcc.

Task 9 — Compare the algorithms experimentally

Run both algorithms on the same data and observe the result.

Step 1 — Use the same input values

For static arrays, this is automatic. For dynamic arrays, use the same random range and similar sizes.

Step 2 — Check correctness first

The first goal is not speed but correctness. Make sure both programs always produce sorted output.

Step 3 — Reflect on the difference

Which algorithm was easier to implement?
Which one is easier to explain?
Which one seems to perform fewer unnecessary moves?

This laboratory is not about benchmarking yet. It is about understanding how sorting algorithms operate.

Checklist before submission

array.h contains declarations of bsort_l and isort_l,
bsort_l.c and isort_l.c compile without warnings,
you have two test programs for static arrays,
you have two test programs for dynamic arrays,
each test displays the array before and after sorting,
dynamic memory is released correctly,
libarray.a has been updated with the new object files.

Quick Summary

Main topic: sorting arrays of long
Algorithms: bubble sort, insertion sort
Input data: static and dynamic arrays
Module: array.h + separate .c files
Library: extend libarray.a from Lab 7

Suggested File Set

array.h

bsort_l.c
isort_l.c

ex26_bubble_long.c
ex27_insertion_long.c
ex28_bubble_long.c
ex29_insertion_long.c

bsort_l.o
isort_l.o
libarray.a

Recommended Compile Sequence

gcc -Wall -c bsort_l.c
gcc -Wall -c isort_l.c

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

gcc -Wall ex26_bubble_long.c -L. -larray -o ex26_bubble_long
gcc -Wall ex27_insertion_long.c -L. -larray -o ex27_insertion_long
gcc -Wall ex28_bubble_long.c -L. -larray -o ex28_bubble_long
gcc -Wall ex29_insertion_long.c -L. -larray -o ex29_insertion_long

Connection from Lab 7

Laboratory 7 created the reusable array module. Laboratory 8 adds sorting functions to the same module.

print_l prints test arrays
randomize_l creates dynamic test data
bsort_l sorts using repeated swaps
isort_l sorts using insertion into a sorted prefix

Important Concepts

sorting changes the array in place
array size is still passed separately
static arrays can use sizeof in the same block
dynamic arrays require free
library functions should be reusable and type-consistent

Laboratory Overview

Learning Outcomes

How this laboratory continues Lab 7

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 8

Step 4 — General rules

Task 1 — Read about the selected algorithms

Step 1 — Bubble sort

Step 2 — Insertion sort

Task 2 — Extend array.h with sorting declarations

Step 1 — Open the header file

Step 2 — Add declarations

Task 3 — Implement bubble sort for long

Step 1 — Create the file

Step 2 — Include the header

Step 3 — Implement bubble sort

Task 4 — Implement insertion sort for long

Step 1 — Create the file

Step 2 — Implement insertion sort

Task 5 — Test sorting on a static array

Step 1 — Create the first test program

Step 2 — Define a static array

Step 3 — Compute its size with sizeof

Step 4 — Print before and after sorting

Step 5 — Create the second test program

Task 6 — Test sorting on a dynamic array

Step 1 — Create the first dynamic test

Step 2 — Ask the user for the size

Step 3 — Allocate memory

Step 4 — Fill the array with random values

Step 5 — Print, sort, print again

Step 6 — Free memory correctly

Step 7 — Prepare the second dynamic test

Task 7 — Print arrays in a reusable way

Step 1 — Write a helper function

Task 8 — Compile the object files and update the library

Step 1 — Compile the sorting functions

Step 2 — Update the library archive

Step 3 — Compile a testing program with the library

Task 9 — Compare the algorithms experimentally

Step 1 — Use the same input values

Step 2 — Check correctness first

Step 3 — Reflect on the difference

Checklist before submission

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

Task 3 — Implement bubble sort for `long`

Task 4 — Implement insertion sort for `long`

Step 3 — Compute its size with `sizeof`