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;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s