The C Programming Language

Part F - Refinements

Algorithms

Design procedures using selection and iteration constructs to solve a programming task
Design data collections using arrays to manage information efficiently

"Algorithms are essential to the way computers process data"
(Wikipedia, 2016)

Searching | Masking | Sorting | Mixing | Exercises

The central aspect of solving a programming task is the design of an appropriate algorithm. An algorithm is the set of rules that define the sequence of operations required to complete the task. Examples of tasks that require algorithms include finding the elements in a list satisfying a specified condition, sorting the elements of a list in a specified order and mixing the elements of a list. The design of an algorithm typically involves selections and iterations; in some cases, nested selections and nested iterations. Often, there is more than one algorithm that solves the programming task. Different algorithms exhibit different efficiencies.

This chapter introduces the implementations of a few more common algorithms. We implement them in function form for use as black boxes in other applications.

Searching

Search algorithms finds the index of one or more array elements that satisfy a specified condition or set of conditions. These algorithms work with key-value pairs. Each key is unique while the values are not necessarily unique.

Two Algorithms

Unsorted Key Array

Given an unsorted key array, we start our search at the first element and progress through the array element by element until we find a match. This algorithm involves an iteration and a selection.

 // Find Unit Price
 // find.c

 #include <stdio.h>

 // find returns the index of the first element in a[n]
 // that contains the value 'item'; -1 if not found
 //
 int find(int a[], int n, int item)
 {
         int i, rc = -1;
         for (i = 0; i < n; i++)
                 if (item == a[i]) {
                         rc = i; // save the index
                         i  = n; // stop the iteration 
                 }

         return rc;
 }

 int main(void)
 {
         int i, item;
         int sku[]      = { 2156, 4633, 3122, 5611};
         double price[] = {12.34, 7.89, 6.56, 9.32};
         const int n    = 4;

         printf("SKU   : ");
         scanf("%d", &item);
         i = find(sku, n, item);
         if (i >= 0 && i < n)
                 printf("Price : $%0.2lf\n", price[i]); 
         else
                 printf("%d not in system\n", item);

         return 0;
 }





























 SKU   : 4633


 Price : $7.89

Note that we check the value returned by find() to ensure that it is within the bounds of the key array (that is, we check that it is not -1).

Sorted Key Array

Given a sorted key array, we start our search in the middle of the array and at each step discard the half that doesn't contain the search key. Although this algorithm is slightly more complicated than the unsorted one, it is significantly faster, which is important with a large number of elements.

 // Find Unit Price - Sorted Keys Ascending Order
 // find_ascend.c

 #include <stdio.h>

 // find_ascend returns the index of the first element
 // in ascending order a[n] that contains the value 'item' 
 // returns -1 if not found
 //
 int find_ascend(int a[], int n, int item)
 {
         int i, low = 0, high = n - 1, rc = -1;
         do {
                 i = (low + high) / 2;
                 if (a[i] < item)
                         low = i + 1;
                 else if (a[i] > item)
                         high = i - 1;
                 else
                         rc = i;
         } while (low <= high && rc == -1);

         return rc;
 }

 int main(void)
 {
         int i, item;
         int sku[]      = { 2156, 3122, 4633, 5611};
         double price[] = {12.34, 6.56, 7.89, 9.32};
         const int n    = 4;

         printf("SKU   : ");
         scanf("%d", &item);
         i = find_ascend(sku, n, item);
         if (i >= 0 && i < n)
                 printf("Price : $%0.2lf\n", price[i]); 
         else
                 printf("%d not in system\n", item);

         return 0;
 }


































 SKU   : 4633


 Price : $7.89

Masking

Masking algorithms distinguish certain array elements from all other elements. The masking array is a parallel array with respect to the other arrays in the set. The elements of the masking array are flags that identify inclusion or exclusion.

Consider the following program, which calculates the total purchase price for a set of products. The user enters the sku for each product purchased and the quantity. Some products attract HST (Harmonized Sales Tax), while others do not. We store the skus, unit prices and tax status in three parallel arrays. The tax status array is the masking array. The user enters 0 to terminate input.

 // Total Purchase Price
 // masking.c

 #include <stdio.h>
 #define HST 0.13

 int find(int a[], int n, int item)
 {
         int i, rc = -1;
         for (i = 0; i < n; i++)
                 if (item == a[i]) {
                         rc = i;
                         i  = n;
                 }

         return rc;
 }

 int main(void)
 {
         int i, item, n;
         int sku[]      = { 2156, 3122, 4633, 5611};
         double price[] = {12.34, 6.56, 7.89, 9.32};
         int tax[]      = {    1,    0,    0,    1};
         const int nitems = 4;
         double sum = 0.0;

         do {
                 printf("SKU : ");
                 scanf("%d", &item);
                 if (item != 0) {
                         i = find(sku, nitems, item);
                         if (i >= 0 && i < nitems) {
                                 printf("NO  : ");
                                 scanf("%d", &n);
                                 if (tax[i] == 1)
                                         sum += n *
                                          price[i]
                                          * (1.0 + HST); 
                                 else
                                         sum += n *
                                          price[i];
                         } else {
                                 printf("%d not in"
                                  " system\n",
                                  item);
                         }
                 }
         } while (item != 0);

         printf("Total is $%0.2lf\n", sum);
         return 0;
 }






























 SKU : 2156
 NO  : 3
 SKU : 3121
 SKU not in system 
 SKU : 3122
 NO  : 2
 SKU : 5611
 NO  : 1
 SKU : 0












 Total is $65.48

Sorting

Sorting algorithms rearrange the elements of an array according to a pre-defined rule. Typically, this rule is ascending or descending order. The sorting criterion may be numeric or based upon a collating sequence such as ASCII or EBCDIC.

The two simplest algorithms are

selection sort
bubble sort

Selection Sort

A selection sort selects a reference element and steps through the rest of the elements looking for any one with a value that does not meet the test condition. If found, the algorithm swaps that element with the reference element.

The following program sorts the array in ascending order. Starting with the first element in the array, it picks the first unsorted element as the reference element, swaps it with the smallest element in the unsorted part of the array, and iterates until it reaches the last element in the array.

 // Selection Sort
 // selectionSort.c

 #include <stdio.h>

 // selectSort sorts the elements of a[n] in ascending order
 //
 void selectSort(int a[], int n)
 {
     int i, j, m;
     int temp;

     for (i = 0; i < n; i++) {
         m = i;
         for (j = i + 1; j < n; j++)
             if (a[j] < a[m]) {
                 m = j;
             }
         if (m != i) {
             temp = a[i];
             a[i] = a[m];
             a[m] = temp;
         }
     }
 }

 int main(void)
 {
         int i;
         int sku[]   = {2156, 4633, 3122, 5611};
         const int n = 4;

         selectSort(sku, n);
         for (i = 0; i < n; i++ )
                 printf("%6d\n", sku[i]);

         return 0;
 }

Bubble Sort

A bubble sort moves through the array element by element swapping elements if the next one does not satisfy the sort condition. The algorithm repeats this process for each unsorted subset of the array starting with the first element. The algorithm moves elements to their terminal positions just like bubbles rising through a liquid - hence the name bubble sort.

 // Bubble Sort
 // bubbleSort.c

 #include <stdio.h>

 // bubbleSort sorts the elements of a[n] in ascending order 
 //
 void bubbleSort(int a[], int n)
 {
         int i, j;
         int temp;

         for (i = n - 1; i > 0; i--) {
                 for (j = 0; j < i; j++) {
                         if (a[j] > a[j+1]) {
                                 temp = a[j];
                                 a[j] = a[j+1];
                                 a[j+1] = temp;
                         }
                 }
         }
 }

  int main(void)
 {
         int i;
         int sku[]   = { 2156, 4633, 3122, 5611};
         const int n = 4;

         bubbleSort(sku, n);
         for (i = 0; i < n; i++ )
                 printf("%6d\n", sku[i]);

         return 0;
 }

Sorting Strings

The following program accepts a list of names, sorts them in alphabetic order and displays the sorted list:

 // Sort a List of Names
 // sortNames.c

 #include <stdio.h>
 #include <string.h>
 #define MN 10   // maximum number of names in the list
 #define MC 30   // maximum number of characters in a name
 #define FM "30" // used in the format string of scanf()

 void bubble(char a[][MC+1], int size);

 int main(void)
 {
         char name[MN][MC+1];
         int i, n, keepgoing;

         // Input the list of names
         printf("Enter names (^ to stop)\n");
         i = 0;
         do {
                 printf("? ");
                 scanf(" %"FM"[^\n]", name[i]);
                 keepgoing = strcmp(name[i], "^") != 0;
                 i++;
         } while (keepgoing == 1 && i < MN);
         if (keepgoing == 1)
                 n = MN;
         else
                 n = i - 1;

         // sort the names
         bubble(name, n);

         // display thesorted list
         for (i = 0; i < n; i++)
             printf("%s\n", name[i]);

         return 0;
 }

 // bubbleSort sorts the elements of a[size] in ascending order 
 //
 void bubble(char a[][MC+1], int size)
 {
         int i, j;
         char temp[MC+1];

         for (i = size - 1; i > 0; i--) {
                 for (j = 0; j < i; j++) {
                         if (strcmp(a[j],a[j+1]) > 0) {
                                 strcpy(temp, a[j]);
                                 strcpy(a[j], a[j+1]);
                                 strcpy(a[j+1], temp);
                         }
                 }
         }
 }

Note the concatenation of string literals in the format string of the call to scanf(). This lets us set the maximum number of input characters alongside the maximum number of characters in the array of strings at the head of the program code. The C compiler converts a concatenation of string literals into a single literal removing the intermediate pairs of double quotes; that is, to the compiler "a""b""c" is the same as "abc".

Mixing

Mixing algorithms have applications in games of chance. Examples include shuffling the cards in a deck or tumbling numbered balls into a lottery chute. The algorithm depends on the extent to which we seek to generate a truly fair result.

Consider the following program, which tumbles 10 balls into a lottery chute. To simulate mixing, the algorithm picks the index of a reference element, randomly picks the index of another element further along in the array and swap the values stored in the two elements. This algorithm is attributed to Donald Knuth, a pioneer of computer science.

 // Mix Lottery Balls
 // mix.c

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

 // mix mixes the elements in a[n] randomly 
 //
 void shuffle(int a[], int n)
 {
         int i, left, j, temp;

         left = n;
         for (i = 0; i < n; i++) {
                 j = i + rand() % left;
                 temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
                 left--;
         }
 }

 int main(void)
 {
     int i, n = 10;
     int ball[n];

     for (i = 0; i < n; i++)
             ball[i] = i + 1;
     srand(time(NULL));
     shuffle(ball, n);
     for (i = 0; i < n; i++)
             printf("%5d\n", ball[i]);

     return 0;
 }

Exercises

Upgrade bubbleSort.c to sort unit prices alongside the key array
Upgrade masking.c to keep track of the number of items in stock
Complete the following practice problems
- Find Subjects

print this page

Top

Previous: Two-Dimensional Arrays

Next: Portability

Notes

Copying From This Site