Sorting Strings in C

There are many techniques for encoding and encrypting text. Encoding text means modifying the text’s format so that it can be interpreted by another system; encrypting text means modifying the text so that it can only be interpreted by designated parties.

A transposition cypher is a simple means for encrypting text. In this technique, the text is written as a matrix of characters, then the matrix is transposed and the characters read out.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <malloc.h>

int main(void){

    char input[100];
    char matrix[10][10];

    int i, spaces, row, column, lineLength, stringLength;

    printf("Please enter a text string to encrypt: \n");
    
    fgets(input, sizeof(input), stdin);

    spaces = 0;
    stringLength = strlen(input);

    for(i = 0; i < stringLength; i++){
        if(input[i]==' '){
            spaces++;
        }
    }

    lineLength = 1 + sqrt(stringLength - spaces);

    //fill matrix with empty spaces
    for(row = 0; row < 10; row++){
        for(column = 0; column < 10; column++){
            matrix[row][column] = ' ';
        }
    }

    row = 0;
    column = 0;
    i = 0;

    while(input[i]!='')
    {
        //leave blank spaces be
        if(input[i]!=' ' && input[i]!='\n'){
            matrix[row][column] = input[i];
            row++;
            //have we reached the end of the line?
            if(row==lineLength){
                row = 0;
                column++;
            }
        }
        i++;
    } //end while

    //print out matrix
    for(row = 0; row < 10; row++){
        for(column = 0; column < 10; column++){
            printf("%c", matrix[row][column]);
        }
        putchar('\n');
    }


    //print out encrypted string
    char *s = (char*)malloc(sizeof(char) * stringLength - spaces);
    
    row = 0;
    column = 0;
    i = 0;
    printf("Encrypted string: %s\n", s);    
    for(row = 0; row < 10; row++){
        for(column = 0; column < 10; column++){
            if(matrix[row][column]!=' ' && matrix[row][column]!='\n'){
                *(s + i) = matrix[row][column];    
                i++;    
            }
        }
    }

    printf("Encrypted string: %s\n", s);
    return 0;

}

Our next program is a simple text formatter. To do this, we must determine how many lines will fit on a single line of text, and then we must figure out how many blank spaces we must include to make sure that the line fills the margins.

#include <stdio.h>
#include <string.h>

#define EXPAND_LINE 1
#define NO_EXPAND 0
#define WIDTH 50

void initializeBuffer(char *buff);
void loadWord(char *buffer, char *word, int *spaceremaining);
int getWord(char *text, int index, char *word);
void printLine(char *buffer);

int main(void){

    char *text = "A lot hinges on the fact that, in most circumstances, people are not allowed to hit you with a mallet. They put up all kinds of visible and invisible signs that say 'Do not do this' in the hope that it'll work, but if it doesn't, then they shrug, because there is, really, no mallet at all.";


    char buffer[100];
    char word[100];

    int spaceleft, nextIndex, currIndex;

    spaceleft = WIDTH;

    nextIndex = 0;

    initializeBuffer(buffer);

    while(1){
        //get() function returns int value
        //indicating where to resume search in text
        //side effect is loading next word into word
        //buffer
        nextIndex = getWord(text, currIndex, word);
        if(spaceleft >= strlen(word)){
            //loadword side effects
            //decrements spaceleft
            //loads word into buffer
            loadWord(buffer, word, &spaceleft);
            currIndex = nextIndex;
        } else {
            //print out line
            printLine(buffer);
            //reset buffer
            initializeBuffer(buffer);
            //reset spaceleft
            spaceleft = WIDTH;
        }
        //break out of loop if
        //no more words
        if(strlen(word)==0){
            if(buffer[0]!=''){
                printLine(buffer);
            }
            break;
        }
        
    } // end while loop

    return 0;

}

void initializeBuffer(char *buffer){
    for(int i = 0; i < WIDTH; i++){
        *(buffer+i) = '';
    }
}

int getWord(char *text, int index, char *word){
    int i = 0;
    
    while((text[index]==' ') && (text[index] != '')){
        index++;
    }

    //copy characters into word
    while((text[index]!=' ') && (text[index] != ''))
    {
        *(word+i) = text[index];
        i++;
        index++;
    }
    *(word+i) = '';

    return index;
}

void loadWord(char *buffer, char *word, int *spaceremaining){
    strcat(buffer, word);
    *spaceremaining -= strlen(word);
    if(WIDTH > strlen(buffer)){
        strcat(buffer, " ");
        (*spaceremaining)--;
    }
}


void printLine(char *buffer){

    int index = 0;
    int wordEndIndex  = 0;
    int copyIndex;
    //no need to expand the line
    if(strlen(buffer)==WIDTH){
        printf("%s\n", buffer);
    } else {
        int blanks = WIDTH - strlen(buffer);
    
        while(blanks-- > 0){
            //find end of word
            while(buffer[wordEndIndex]!=' ' & buffer[wordEndIndex]!='\n'){
                wordEndIndex++;
            }    
            for(copyIndex = WIDTH - 1; copyIndex > wordEndIndex; copyIndex--){
                buffer[copyIndex] = buffer[copyIndex - 1];
            }
            buffer[wordEndIndex] = ' ';
            wordEndIndex++;
        }        
        //attach end of line character    
        buffer[WIDTH] = '';
        
        printf("%s\n", buffer);        
    } // end else
}

If you have any interest in learning more about C, take a look at my book at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/

Sorting and Processing Strings in C

An array of strings is stored in memory as a two dimensional array of characters. For our first program, we will create a two dimensional array of five words with each word containing up to ten characters.

#include <stdio.h>
#include <string.h>

int main(void){

    int i, j;

    char swapstring[10];

    char strings[5][10] = {
            {'T','e','l','e','b','i','t'},
            {'A','t','a','r','i'},
            {'M','e','m','o','t','e','c','h'},
            {'V','i','s','i','c','o','r','p'},
            {'B','o','m','i','s'},
        }; // end strings[][]   


    printf("The original list is: \n");
    for(i = 0; i < 5; i++){
        printf("%s\n", strings[i]);
    }
    printf("\n");

    //use bubble sort
    for(j = 0; j < 4; j++){
        for(i = j + 1; i < 5; i++){
            //strcmp() returns a number greater than zero
            //if the second string is less than the first
            if(strcmp(strings[j], strings[i]) > 0){
                strcpy(swapstring, strings[j]);
                strcpy(strings[j], strings[i]);
                strcpy(strings[i], swapstring);
            }
        }
    }

    printf("The sorted list is: \n");
    for(i = 0; i < 5; i++){
        printf("%s\n", strings[i]);
    }

    return 0;


}

In our first program we used bubble sort to sort the list of strings. A bubble sort is a nested loop that performs n-1 passes over a list of n number of items, swapping an item with the next item in the list if it is greater than the next item. Bubble sort is very simple, and also very inefficient.

In our next program, we will use selection sort to sort the strings. Selection sort’s main value over bubble sort is that it should in general perform less swaps; although, it is still not a very efficient sorting routine. Selection sort, like bubble sort, has an inner and outer loop. The outer loop moves from the start of the array to the penultimate element. At each increment of the outer loop, the inner loop sets the potential minimum value to whatever the current index is in the outer loop. The inner loop then compares this theoretical minimum value with every element after it; if the loop finds a value that is less than the theoretical minimum, it resets the the theoretical minimum to the index of that element. Finally, when the inner loop has been completed, it then and only then swaps out the current element in the outer loop with the element that the inner loop found to be the smallest.

 

#include <stdio.h>
#include <string.h>


int main(void){

    char swapstring[10];

    int j,k, minimum;

    char strings[5][10]= {
        "Malthus",
        "Smith",
        "Volaire",
        "Hobbes",
        "Hume"
    };

    printf("The original list is: \n");
    for(j = 0; j < 5; j++){
        printf("%s\n", strings[j]);
    }


    for(j = 0; j < 4; j++){
        //set index of smallest element
        minimum = j;
        for(k = j + 1;  k < 5; k++){
            //if result is negative
            //strings[k] is less than strings[minimum]
            if(strcmp(strings[k], strings[minimum]) < 0){
                //elemet at index k is new minimum
                minimum = k;
            }

        } //end innner for loop
       
        //swap
        strcpy(swapstring, strings[j]);
        strcpy(strings[j], strings[minimum]);
        strcpy(strings[minimum], swapstring);

    } // end outer for loop

    printf("The sorted list is: \n");
    for(j = 0; j < 5; j++){
        printf("%s\n", strings[j]);
    }

    return 0;
}

Our next program counts the number of vowels in a string using a simple switch statement.

#include <stdio.h>

#define LENGTH 50


int GetVowelCount(char *s);

int main(void)
{

    char string1[LENGTH] = "WelcoMe to ThE jUnGLe, we'VE got fuN aNd GAmes.";
    char string2[LENGTH] = "hE's THE One thEy call dR. FeELgoOd.";

    int i = 0;
   

    printf("Vowel count for %s: ", string1);
    printf("%d\n", GetVowelCount(string1));

    printf("Vowel count for %s: ", string2);
    printf("%d\n", GetVowelCount(string2));

    return 0;
}

int GetVowelCount(char *s){
    int i = 0, j = 0;

    while(*(s+i)!=''){
        switch(*(s+i)){
            case 'A':
            case 'a':
                j++;
                break;
            case 'E':
            case 'e':
                j++;
                break;
            case 'I':
            case 'i':
                j++;
                break;
            case 'O':
            case 'o':
                j++;
                break;
            case 'U':
            case 'u':
                j++;
                break;   
        }
        i++;
    }

    return j;
}

Our final program is a simple one as well; it is the classic palindrome checker. A palindrome is a word that reads the same forwards and backwards.

#include <stdio.h>
#include <string.h>

int CheckForPalindrome(char *s);

int main(void){

    char *s[5] =
    {
        “radar”,
        “robot”,
        “kayak”,
        “jazz”,
        “civic”,
    };

    for(int i = 0; i < 5; i++){
        printf(“%s\t”, *(s+i));
        if(CheckForPalindrome(*(s+i))>0){
            printf(“is a palindrome.\n”);
        } else {
            printf(“is not a palindrome.\n”);
        }
    }

    return 0;
}

//returns -1 if it finds two characters that do not match
//returns 1 otherwise
int CheckForPalindrome(char *s)
{
    int L = 0;
    //remember, index starts at 0
    //hence, minus 1
    int R = strlen(s) – 1;

    while(L < R){
        if(*(s+L)!=*(s+R)){
            return -1;
        }
        L++;
        R–;
    }

    return 1;
}

If you would like to learn more about C, take a look at my book at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/