Main Contents Page
CTEC1401 Programming in C
 Quick Reference
Week 19: Searching
Week 20: Sorting
 Week 21: Structures

  1. Before the lab session read CFTTP Chapter 12 on sorting and study the solved exercises 12.5 to 12.10 very carefully.

  2. bubblesort

    Copy the following code into a file called bubblesort.c. 

    #include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include <time.h>

#define DEFAULT_SIZE 100
#define NL  printf("\n")

/******************************************************************************
 Housekeeping methods...
 *****************************************************************************/
inline void SWAP(int *a, int j, int k)
{
    if (j!=k) {a[j] ^= a[k]; a[k] ^= a[j]; a[j] ^= a[k];}
}

void printArrayP(int * a, int N, int p)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        if (i==p)
           printf(" |%5i", a[i]);
        else
           printf("%7i", a[i]);
        i++;
    }
    NL;
}
void printArray(int * a, int N)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        printf("%7i", a[i]);
        i++;
    }
    NL;
}
/******************************************************************************
 Sort the array a with size N using a BUBBLE SORT algorithm
 *****************************************************************************/
void bubbleSort( int a[], int N )
{
    int i,j;
    for (i=N-1; i>0; i--) {
        
        #ifdef SHOW
        printf("Bubbling...\n");
        #endif
        
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
                SWAP(a,j,j+1);
            
            #ifdef SHOW
            printArrayP(a,N,i);printf("\n");
            #endif
        }
    }
}

/**
 * Bubblesort - Uncluttered version without all the SHOW stuff
 */
void bubbleSort_( int a[], int N )
{
    int i,j;
    for (i=N-1; i>0; i--)
        for (j=0; j<i; j++)
            if (a[j] > a[j+1])
                SWAP(a,j,j+1);
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*N);
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;


    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");

    bubbleSort(nums,N);
    
    // Print out the sorted sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
}

    This program performs a bubble sort. You saw this earlier because it was used to sort the array in binarysearch1. Note the following points:

    • We have used conditional compilation so that you can switch on/off the display of the array at each stage of the sorting process. If you look at the sorting function you will see the relevant #ifdef / #endif directives.
    • The main program creates an array of random numbers and uses bubble sort to sort them into numerical order.
    • The program has a number of helper functions that are used to swap values and print arrays etc. Without these it would be very difficult to demonstrate what is going on.

    Compile the program and run it with a variety of different array sizes. NB: Start small if you switch the SHOW option on - it will print the array at every stage of the bubble sort. We would suggest an array of size five to get you started.

    gcc bubblesort.c -DSHOW -o bubblesort

  3. selectionsort

    Copy the following code into a file called selectionsort.c. 

    #include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include <time.h>

#define DEFAULT_SIZE 100
#define NL  printf("\n")

/******************************************************************************
 Housekeeping methods...
 *****************************************************************************/
inline void SWAP(int *a, int j, int k)
{
    if (j!=k) {a[j] ^= a[k]; a[k] ^= a[j]; a[j] ^= a[k];}
}

void printArrayP(int * a, int N, int p)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        if (i==p)
           printf(" |%5i", a[i]);
        else
           printf("%7i", a[i]);
        i++;
    }
    NL;
}
void printArray(int * a, int N)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        printf("%7i", a[i]);
        i++;
    }
    NL;
}


/******************************************************************************
 Find the index of the smallest element in the array a with size N
 The search begins at location lo
 *****************************************************************************/
int smallest(int a[], int lo, int N)
{
    int s = lo, i;
    for (i=lo+1; i<N; i++)
        if (a[i] < a[s]) s = i;
    return s;
}
/******************************************************************************
 Sort the array a with size N using a SELECTION SORT algorithm
 *****************************************************************************/
void selectSort( int a[], int N )
{
    int i,s;
    for (i=0; i<N; i++) {
        s = smallest(a,i,N);
        SWAP(a,i,s);
        #ifdef SHOW
          printArrayP(a,N,i+1);printf("\n");
        #endif
    }
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*N);
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;


    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");

    selectSort(nums,N);
    
    // Print out the sorted sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
}

    This program performs a selection sort. It works by selecting the smallest item in the array and then swapping it with the element at the "front" of the partition. This ensures that the items to the left of the partition are in order and the items to the right are unordered. When the partition reaches the end of the array it is completely sorted.

    The structure of the main program should be familiar to you by now so you can go ahead and compile and run the program. 

    gcc selectionsort.c -DSHOW -o selectionsort

  4. selectionsort2

    Make another copy of the selectionsort program and call it selectionsort2.

    Modify the program such that it can sort in ascending or descending order depending on user preference. To do this you will need to:

    • Copy the smallest function and change it to find the largest value in the array.
    • Consider how the user may choose the direction of the sort. Perhaps you could use a command line argument; maybe you ask the user to enter this information when the program runs; it is up to you.
    You should make sure your program works properly sorting numbers in ascending and descending order.

  5. insertionsort

    Copy the following code into a file called insertionsort.c. 

    #include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include <time.h>

#define DEFAULT_SIZE 100
#define NL  printf("\n")

/******************************************************************************
 Housekeeping methods...
 *****************************************************************************/
inline void SWAP(int *a, int j, int k)
{
    if (j!=k) {a[j] ^= a[k]; a[k] ^= a[j]; a[j] ^= a[k];}
}

void printArrayP(int * a, int N, int p)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        if (i==p)
           printf(" |%5i", a[i]);
        else
           printf("%7i", a[i]);
        i++;
    }
    NL;
}
void printArray(int * a, int N)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        printf("%7i", a[i]);
        i++;
    }
    NL;
}


/******************************************************************************
 Insert the element x in (ascending) order in the array 'a' within the prefix
 portion 0..hi.
 *****************************************************************************/
void insert(int a[], int x, int hi)
{
    int i = 0, j;
    while (i<hi && a[i]<x) i++;
    /* i is the insertion position (i may be hi: the last possible location)
       Before inserting at i make room by shunting: a[i..hi-1] -> a[i+1..hi]
     */
    for (j=hi; j>i; j--) a[j] = a[j-1];
    a[i] = x;
}
/******************************************************************************
 Sort the array a with size N using an INSERTION SORT algorithm
 *****************************************************************************/
void insertSort( int a[], int N )
{
    int i,s;
    for (i=0; i<N; i++) {
        insert(a,a[i],i);
        #ifdef SHOW
        printArrayP(a,N,i+1);printf("\n");
        #endif
    }
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*N);
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;


    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");

    insertSort(nums,N);
    
    // Print out the sorted sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
}

    This program performs an insertion sort. It works by selecting the next item in the array and then inserting it into the correct place in the partition to the left. When the partition reaches the end of the array it is completely sorted.

    Compile and run the program. Take note of how the partition of sorted elements grows. 

    gcc insertionsort.c -DSHOW -o insertionsort

    6. Supplementary Exercises

  6. quicksort

    Copy the following code into a file called quicksort.c. 

    #include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

#define DEFAULT_SIZE 100
#define NL  printf("\n")

/******************************************************************************
 Housekeeping methods...
 *****************************************************************************/
inline void SWAP(int *a, int j, int k)
{
    if (j!=k) {a[j] ^= a[k]; a[k] ^= a[j]; a[j] ^= a[k];}
}

void printArrayP(int * a, int N, int p)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        if (i==p)
           printf(" |%5i", a[i]);
        else
           printf("%7i", a[i]);
        i++;
    }
    NL;
}
void printArray(int * a, int N)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        printf("%7i", a[i]);
        i++;
    }
    NL;
}

/******************************************************************************
 Sort the array a with size N using a QUICKSORT algorithm
 *****************************************************************************/
void q_sort( int *a, int left, int right)
{
    int i, last, pivot;
    if (left >= right)
        return;
    #ifdef PIVOT1
    pivot = left;
    #else
    pivot = (left+right)/2;
    #endif
    #ifdef SHOW
    printArray(a+left,right-left+1);printf("\n");
    printf("***Left = %i; ***Rght = %i; *** Pivot = %i\n", left, right, a[pivot]);
    #endif
    SWAP(a, left, pivot);
    last = left;
    for( i=left+1; i<=right; i++ )
    {
        if (a[i] < a[left])
        {
            SWAP(a, ++last, i);
        }
    #ifdef SHOW
    printArray(a+left,right-left+1);printf("\n");
    printf("++++ last = %2i, i = %2i\n", last, i);
    #endif
    }
    SWAP(a, left, last);
    q_sort(a, left, last-1);
    q_sort(a, last+1, right);
}
 
void quickSort(int a[], int N)
{
    q_sort(a,0,N-1);
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*(N+1));
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;


    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");

    quickSort(nums,N);
    
    // Print out the sorted sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
}

    This program performs a version of quick sort.

    Compile and run the program. 

    gcc quicksort.c -DSHOW -o quicksort

  7. heapsort

    Copy the following code into a file called heapsort.c. 

    #include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

#define DEFAULT_SIZE 100
#define NL  printf("\n")

/******************************************************************************
 Housekeeping methods...
 *****************************************************************************/
inline void SWAP(int *a, int j, int k)
{
    if (j!=k) {a[j] ^= a[k]; a[k] ^= a[j]; a[j] ^= a[k];}
}

void printArrayP(int * a, int N, int p)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        if (i==p)
           printf(" |%5i", a[i]);
        else
           printf("%7i", a[i]);
        i++;
    }
    NL;
}
void printArray(int * a, int N)
{
    int i = 0;
    while (i < N)
    {
        if ( i % 10 == 0 ) printf("\n%7i ]", i);
        printf("%7i", a[i]);
        i++;
    }
    NL;
}

/******************************************************************************
 The heapsort algorithm superimposes a balanced binary tree onto the array. To
 visualise this we construct a function, printNodes, for printing a (sideways)
 view of the tree.
 *****************************************************************************/
#define LCHILD(i) (((i+1)*2)-1)
#define RCHILD(i)  ((i+1)*2)
#define PARENT(i) (((i+1)%2)-1)
void printNodes(int a[], int tab, int n, int N)
{
    int i;
    if (n<N) {
        if (RCHILD(n) < N)
            printNodes(a,tab+1,RCHILD(n),N);
        for (i=0; i<tab; i++) 
            printf("%8c",' ');
        printf("%8i\n",a[n]);
        if (LCHILD(n) < N)
            printNodes(a,tab+1,LCHILD(n),N);
    }
}
void printTree(int a[], int N)
{
    printNodes(a, 0, 0, N);
}
/******************************************************************************
 The main component of heapsort is the sift-down algorithm that allows a node
 to travel down a path in the tree and find its rightful place - thus
 re-establishing a heap.
 *****************************************************************************/
void siftDown( int a[], int k, int N )
{
    int parent=k;
    int child;
    while(1) {
       child = LCHILD(parent);
       if (child >= N) /* no children - we are at a leaf node */
           break;         /* so exit the loop, we are done */
       else {
           if (child+1 < N            /* are there two children?    */
               && a[child+1] > a[child]) /* and is r-child is greater? */
               child++;                  /* then set child to r-child  */
           /* so now child is the index of the largest (or only) child */
           if (a[parent] > a[child])     /* nothing else to do         */
               break;
           else {
               SWAP(a,parent,child);
               parent = child;          /* and sift down from here...  */
           }
       }
    }
}
void makeHeap( int a[], int N )
{
    int k = (N-1) / 2;
    while (k>=0) {
        siftDown(a,k,N);
        k--;
    }
}
/******************************************************************************
 Sort the array a with size N using a HEAPSORT algorithm
 *****************************************************************************/
void heapSort( int a[], int N )
{
    int k = N-1;
    makeHeap(a, N);
        #ifdef SHOW
        printf("\nInitial Heap: \n");
        printArray(a,N);printf("\n");
        printTree(a,N); printf("\n");
        #endif
    while (k>0) {
        SWAP(a, 0, k);              /* largest is now at the end */
        #ifdef SHOW
        printf("**** Before sift down (%i):\n",k-1);
        printArrayP(a,N,k);printf("\n");
        printTree(a,k); printf("\n");
        #endif
        siftDown(a, 0, k);        /* find rightful place for swapped item */
        #ifdef SHOW
        printf("**** After  sift down:\n");
        printArrayP(a,N,k);printf("\n");
        printTree(a,k); printf("\n");
        #endif
        k--;
    }
}


main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*(N+1));
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;


    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");

    heapSort(nums,N);
    
    // Print out the sorted sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
}

    This program performs a version of heap sort.

    Compile and run the program. 

    gcc heapsort.c -DSHOW -o heapsort