Searching and Sorting Arrays

An array is a fixed-size, homogeneous data structure with random-access, where all elements can be selected at random and are equally accessible. An element of the array can be selected by giving its subscript, which is an integer indicating the position of the element in the array.

Arrays are represented in memory using sequential mapping.

A two dimensional array can be viewed as a one-dimensional array who elements are in turn one-dimensional arrays. We can view a two dimensional array as a single column of rows; this is called row-major representation.

An array can be viewed as a matrix. To add two matrices, we simply add the matching rows and columns to each other.

int * getArray(int row, int column);
void printArray(int *array, int row, int column);
void populateArray(int *array, int row, int column, char *name);
void addArray(int *arrOne, int *arrTwo, int row, int column);

int main()
{
    const int rSize = 3;
    const int cSize = 3;

    int *arrOne = getArray(rSize, cSize);
    int *arrTwo = getArray(rSize, cSize);

    populateArray(arrOne, rSize, cSize, "first");
    populateArray(arrTwo, rSize, cSize, "second");

    printArray(arrOne, rSize, cSize);
    printArray(arrTwo, rSize, cSize);

    addArray(arrOne, arrTwo, rSize, cSize);


    return 0;
}

void addArray(int *arrOne, int *arrTwo, int row, int column){
    int i = 0;
    int j = 0;
    int a, b;
    while(i < row){
        while(j < column){
            a = *(arrOne + (i*column) + j);
            b = *(arrTwo + (i*column) + j);
            printf("\n%d + %d = ", a, b);
            *(arrOne + (i*column) + j) += b;
            printf("%d\n", *(arrOne + (i * column) + j));
            j++;
        }
        j = 0;
        i++;
    }

    printArray(arrOne, row, column);

}

void populateArray(int *array, int row, int column, char *name){
    int i = 0;
    int j = 0;
    int val;
    printf("Please populate the %s array:\n", name);
    while(i < row){
        while(j < column){
            printf("Value for row %d, column %d\t", i, j);
            scanf("%d", &val);
            *(array + (i * column)+j) = val;
            j++;
        }
        j = 0;
        i++;
    }
}

void printArray(int *array, int row, int column){
    int i = 0;
    int j = 0;
    printf("\n");
    while(i < row){
        while(j < column){
            //use pointer arithmetic to get the array elements
            printf("%d\t", *(array + (i*column)+j));
            j++;
        }
        j = 0;
        i++;
        printf("\n");
    }
}

int * getArray(int row, int column){
    int *rArray = (int *)malloc(row * column * sizeof(int));
    return rArray;
}

The transpose of a matrix is a new matrix whose rows are the columns of the original, and whose columns are the rows of the original .


#define ROW_LENGTH 3
#define COL_LENGTH 3

void readArray(int *array, int rowLength, int colLength);
void displayArray(int *array, int rowLength, int colLength);
void transpose(int *matrix, int rowLength, int colLength);

int main()
{
    int iMatrix[ROW_LENGTH][COL_LENGTH];

    readArray(iMatrix, ROW_LENGTH, COL_LENGTH);
    displayArray(iMatrix, ROW_LENGTH, COL_LENGTH);
    transpose(iMatrix, ROW_LENGTH, COL_LENGTH);
    displayArray(iMatrix, ROW_LENGTH, COL_LENGTH);

    return 0;
}

void readArray(int *array, int rowLength, int colLength){
    int i, j;
    for(i = 0; i < rowLength; i++){
        for(j = 0; j < colLength; j++){
            printf("Enter value for element [%d, %d]: ", i, j);
            scanf("%d", (array + (i * colLength) + j));
        }
    }
}

void displayArray(int *array, int rowLength, int colLength){
    int i, j;
    for(i = 0; i < rowLength; i++){
        for(j = 0; j < colLength; j++){
            printf("%5d\t", *(array + (i * colLength) + j));
        }
        printf("\n");
    }
}

void transpose(int *matrix, int rowLength, int colLength){
    int i, j, temp;
    for(i = 0; i < rowLength; i++){
            for(j = i+1; j < colLength; j++){
                temp =  *(matrix + (i * colLength) + j);
                 *(matrix + (i * colLength) + j) = *(matrix + (j * colLength) + i);
                *(matrix + (j * colLength) + i) = temp;
            }
    }
}

A bubble sort is a simple sort in which we arrange the elements of the set by forming pairs of adjacent elements, where the pair is of the ith and (i+1)th element. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element.

void swap(int *x, int *y);
void bSort(int *list, int bounds);

int main()
{

    const int bounds = 10;

    int iArray[] = {1701, 73, 6174, 2048, 52, 203, 42, 3389, 1138, 1999};
    printArray(iArray, bounds);
    bSort(iArray, bounds);
     printArray(iArray, bounds);
    return 0;
}

void printArray(int *list, int bounds){
    int i = 0;
    for(; i < bounds; i++){
        printf("%d\t", *(list+i));
    }
    printf("\n");
}


void bSort(int *list, int bounds){
    int inner, outer;
    //go backwards through the array;
    for(inner = bounds - 1; inner > 0; inner--){
            for(outer = 0; outer < inner; outer++){                 
            if(*(list + outer) > *(list + outer + 1)){
                    swap((list + outer), (list + outer + 1));
                }
            }
    }

}


void swap(int *x, int *y){
    printf("swaping %d and %d\n", *x, *y);
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

 

Multidimensional Numeric Arrays

A two dimensional array is a matrix; it can be visualized as a spreadsheet table, with the first index giving the row, and the second index giving the column.

#include <stdio.h>

int main(void){

    int array[2][3] = {
            /* row one */{42, 47, 73},
            /* row two */{7, 11, 3}
            };

    int row, column;

    for(row = 0; row < 2; row++){
        for(column = 0; column < 2; column++){
            printf("array[%d][%d] = %d \t", row, column, array[row][column]);
        }
        printf("\n");
    }
    

    return 0;
    
}

The indexes [2][3] define the array as a two-dimensional array with two rows consisting of three columns each. Note that for each dimension of the array we must include a set of brackets. We use nested for loops to iterate through multidimensional arrays. Remember here that each index starts at 0, not 1.

Our next program will sum each row in an array.

#include <stdio.h>

int main(void){


    int array[3][3] = {
        /* row 1 */ {128, 256, 512},
        /* row 2 */ {161, 389, 443},
        /* row 3 */ {80, 25, 118}
    }; //note the semicolon
    
    //traditional to use i, j
    //rather than row, column
    int i, j, total;
    for(i = 0; i < 3; i++){
        for(j = 0, total = 0; j < 3; j++){
            total += array[i][j];
            printf("%d ", array[i][j]);
        }
        printf(" \t total = %d\n", total);
    }

    return 0;

}

For our next program, we will pass the array to a function. Because an array of more than one dimension will be used, we must specify the dimensions of the array in the formal parameter list, in order for the compiler to properly set the array pointer for each of the rows.

#include <stdio.h>

int addColumn(int array[][3], int column, int numRows);

int main(void){


    int array[4][3] = {
        {25, 118, 123},
        {143, 161, 389},
        {80, 443, 22},
        {53, 88, 546}
    };

    int i, j;

    //go down each column
    //rather than across each row
    for(i = 0; i < 3; i++){
        printf("Column %d: \t", i+1);
        for(j = 0; j < 4; j++){
            printf("%d ", array[j][i]);
        }
        printf(" total = %d\n", addColumn(array, i, 4));
    }

    return 0;

}


int addColumn(int array[][3], int column, int numRows){
    int r = 0;
    for(int i = 0; i < numRows; i++){
        r += array[i][column];
    }
    return r;
}

Matrix multiplication is another useful thing we can do with two dimensional arrays. Matrix multiplication works by multiplying the columns of one matrix by the number of rows in the other. The general rule is that the number of columns in the first matrix must be equal to the number of rows in the second matrix; but, in order to simplify things, we will only be multiplying square matrices, where the number of columns and rows are equal.

#include <stdio.h>

void printMatrix(int array[3][3], int bounds);
void multiplyMatrix(int arrayX[3][3], int arrayY [3][3], int result[3][3], int bounds);

int main(void){
    
    int array1[3][3] = {
        {1, 2, 3},
        {2, 3, 4},
        {4, 5, 6}
    };

    int array2[3][3] = {
        {1, 3, 6},
        {3, 1, 6},
        {6, 3, 1},
    };

    int result[3][3];

    printf("Matrix one: \n");
    printMatrix(array1, 3);
    
    printf("\n\nMatrix two: \n");
    printMatrix(array2, 3);

    multiplyMatrix(array1, array2, result, 3);

    printf("\n results:\n");
    printMatrix(result, 3);

    return 0;


}


void printMatrix(int array[3][3], int bounds){
    int i, j;
    for(i = 0; i < bounds; i++){
        for(j = 0; j < bounds; j++){
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
}


void multiplyMatrix(int arrayX[3][3], int arrayY [3][3], int result[3][3], int bounds){
    int row, column, row2, column2;

    for(row = 0; row < bounds; row++){
        for(column = 0; column < bounds; column++){
            result[row][column] = 0;
            printf("Multiplying row %d of arrayX by column %d of arrayY\n", row, column);
            for(row2 = 0, column2 = 0; column2 < bounds; column2++, row2++){
                result[row][column] += arrayX[row][column2] * arrayY[row2][column];
            }
        }
    }

    
}

Take a look at my author’s page at: http://www.amazon.com/Big-Als-PHP-Al-Jensen-ebook/dp/B0084AKY18/