Puzzles C41 ... C50

Part C — Arrays

These puzzles involve doing harder things with arrays.


Puzzle C41 — exchange the first N/2 elements of an array with the last N/2 elements

[H-7] Write a function that swaps the first half of an array with the last half. Within each half of the array, keep the elements in their original order. If the array has an odd number of characters, the middle element remains where it is. Here is a sample run:

Original:
   0    1    2    3    4    5    6    7    8    9
  10   11   12   13   14   15   16   17   18

Swap Halves:
  10   11   12   13   14   15   16   17   18    9
   0    1    2    3    4    5    6    7    8

Note the requirement to keep the middle element in place for arrays with odd numbers of elements. That requirement makes the puzzle harder than first appears.

Here is a testing framework: Testing Framework


Puzzle C42 — find the first element of one array that is not in another

[M-7] Write a function that has four arguments: two integer arrays, and their sizes. The arrays may be of different sizes. The function returns the index of the first value in the first array that is not somewhere in the second array. If all values in the first array are also in the second array, return -1.

The values in the arrays need not be in order. Values in the arrays may be repeated. Each instance of a repeated value can match the same element in the second array. Here is are several sample runs of a testing program:

Array A:
   2    2    3    3    7    1   29   19    2   19
   5
Array B:
  29   19    5    3    7    2
Value 1 is in A but not in B:


Array A:
   2    2    3    3    7    5   29   19    2   19
   5
Array B:
  29   19    5    3    7    2
All elements in A are found in B:


Array A:
   2    2    3    3    7    5   29   19    2   19
   5
Array B:
  29   19   99    3    7    2
Value 5 is in A but not in B:

Here is a testing framework: Testing Framework


Puzzle C43 — check that two arrays contain only the same elements

[M-5] Write a function who's arguments are two arrays of possibly different sizes. Every element in the first array must also be in the second array, and every element in the second array must be in the first array. However, there may be duplicate elements in either array, and the elements can be in any order.

Return 1 if the conditions are met, 0 otherwise. Here are some sample runs of a testing program:

Array A:
   1    2    3    3    4    5    6    6    7    8

Array B:
   1    2    8    8    3    5    4    6    7    7
   8    8
Arrays have all their elements in common


Array A:
   1    6    6    7    8    2    3    3    4    5

Array B:
   1    2    5    4    6    7    7    8    8    8
   3    8
Arrays have all their elements in common


Array A:
   1    6    6    7    8   99    3    3    4    5

Array B:
   1    2    5    4    6    7    7    8    8    8
   3    8
One array has at least one element not found in the other

Here is a testing framework: Testing Framework


Puzzle C44 — fill a third array with the elements two unsorted arrays have in common

[H-20] Write a function that looks at two arrays and fills a third array with the elements that are common to the first two arrays. The third array has only one copy of each element in common with the other two arrays. The first two arrays may be of unequal sizes. Assume that the arrays are not in sorted order. Return the number of elements placed in the third array. Assume that the third array already exists and is long enough to hold all the common values. Here are some sample runs:

Array A:
  17    1    3   19    3    7    9   13   15    2

Array B:
   2    3    6    8    9    3    5   16

Elements in Common:
   3    9    2
   
   
Array A:
   3    3    5    8    8    9    7    0   -1   -2
   1    1
Array B:
   3    3    3    3    3    5    5    5

Elements in Common:
   3    5

Here is a testing framework: Testing Framework

This puzzle can be solved with a function that takes O(n2) time in the worst case. This would be OK to use only for fairly small arrays. A better solution would use an O(n·logn) sorting method first.


Puzzle C45 — fill a third array with the elements two SORTED arrays have in common

[H-15] Write a function that that looks at two sorted arrays and fills a third array with the elements that are common to the first two arrays. This is the same problem as above, except now assume that the two input arrays contain integers in ascending order.

The third array has only one copy of each element in common with the other two arrays. The first two arrays may be of unequal sizes. Return the number of elements in the third array. Here are some sample runs:

Array A:
  -9    1    2    5    5    6    7    8    8    9
  17
Array B:
  -1    1    3    4    5    5    5    9   17   17
  17   18   25

Elements in Common:
   1    5    9   17


Array A:
   2    2    2    2    7   12   12
Array B:
   1    1    1    1    1    1    1    1    1    7

Elements in Common:
   7

Here is a testing framework: Testing Framework


Puzzle C46 — randomly scramble the elements in an array

[H-7] Write function randomly mixes up the elements of an integer array. Here is a sample run:


Original Array:
     0      1      2      3      4      5      6      7      8      9
    10     11     12     13     14     15     16     17     18     19
    20     21     22     23     24     25     26     27     28     29
    30     31     32     33     34     35     36     37     38     39
    40     41     42     43     44     45     46     47     48     49

Scrambled Array:
    17     10     24     20     26     49      9     41     44     47
    34     37     21     16      7     29      1      3     32     25
    35     38      2     13     40     33      8     23     30     45
    18     12     28      0     46     31     27      6     19     14
    48     11      5     39     43     15     22     42     36      4

In the example, the array starts with its elements in order, but it could start with any ordering of its elements. After being scrambled, any element might end up in any slot with equal probability.

Here is a testing framework: Testing Framework


Puzzle C47 — check that an array has an element -N for each element N

[M-10] Write a function that checks that each element N of an array is matched by at least one other element with the value -N. There may be several elements with value -N, even if there is just one N. And (also) if there are several values N, they may be matched by just one value -N. If there is one zero in the array, it must be matched by at least one other zero.

Return the number of unmatched values. For example:

   0    1   -6    3    6   -1    8    7   -9    9
   0   -7   -8    8    2    2    6    4    5   -6


5 elements are missing a match.

Here is a testing framework: Testing Framework


Puzzle C48 — check that the elements of an array are in ascending order

[E-5] Write function that checks that the elements of an array are in ascending order. Return 0 if the array is in order; otherwise, return the number of elements that are out of order. Here are some sample runs:

   1    2    3    4    6    7    8    7   10   11
  13   20   31   41   41   45   50   53   52   52
2 elements out of order.

   1    1    1    4    6    7    8    8   10   11
  13   20   31   41   41   45   50   51   52   52
All elements are in order.

The phrase "number of elements that are out of order" is vague. Decide on a simple meaning for the phrase.

Here is a testing framework: Testing Framework


Puzzle C49 — selection sort

[H-12] Write a function that carries out selection sort on an array of integers. If you have seen selection sort before, see how much you remember and try to put together a function that does it. Otherwise, read on...

Our selection sort arranges the values of an array into ascending order (low to high). Say that the array starts out as:

8 6 7 5 9 4 2 6

First, find the smallest integer in the entire array and exchange it with the element in slot zero.

8 6 7 5 9 4 2 6

2 6 7 5 9 4 8 6

Slot 0 now correctly holds the smallest value in the array, and we do not need to bother with it again. Now find the value that will go into slot 1. This is the smallest integer in the array to the right of slot zero. Exchange that value with the element in slot one:

2 6 7 5 9 4 8 6

2 4 7 5 9 6 8 6

Now slots 0 and 1 are correct. For slot 2, find the smallest integer in the rest of the array and exchange it with the element in slot two:

2 4 7 5 9 6 8 6

2 4 5 7 9 6 8 6

The algorithm continues the idea of repeatedly finding the smallest remaining element and placing it to the right of those elements already in place:

2 4 5 7 9 6 8 6

2 4 5 6 9 7 8 6

2 4 5 6 9 7 8 6

2 4 5 6 6 7 8 9

2 4 5 6 6 7 8 9

2 4 5 6 6 7 8 9

2 4 5 6 6 7 8 9

Sometimes an element is already in place, so it is swapped with itself and does not move. Here is a testing framework: Testing Framework Here is sample output of the testing framework:

  34   70   34   23   83   41   53   20   54   62
  21   21   37   42   23   80    2   22   43   73
  82   89   29   73   41   12  100   98   72   51
  35   89   50   32   49   67   83   63   72   34
  22   67   51   51   42    8   89   69   55    1
25 elements out of order.

   1    2    8   12   20   21   21   22   22   23
  23   29   32   34   34   34   35   37   41   41
  42   42   43   49   50   51   51   51   53   54
  55   62   63   67   67   69   70   72   72   73
  73   80   82   83   83   89   89   89   98  100
All elements are in order.


Puzzle C50 — sort an array using C46 and C48

[E-7] Write function that uses the answers to C46 and C48 to sort an array. In other words, sort an integer array by randomly scrambling it until it ends up sorted. Here is a testing program:

int randInt( int min, int max );
void scrambleArray( int arr[], int size );
int inOrder( int arr[], int size );

void reallyBadSort( int arr[], int size );

int main(int argc, char *argv[])
{
  const int SIZE = 12;
  int x[SIZE] ;
  int num;
  long start, end;
  
  srand( time(0) );
  fillArrayRandom( x, SIZE, 0, 100 );
  printArray( x, SIZE );
  printf("\n\n");

  printf( "start: %ld\n", start=time(0) );
  
  reallyBadSort( x, SIZE );
  
  printf( "end  : %ld\n", end=time(0) );
  printf( "elapsed time: %ld seconds\n\n", end-start );
  printArray( x, SIZE );

  printf("\n\n");
  system("PAUSE");	
  return 0;
}

Here is a result of running the program:

  58   49   75   60    0    2   38   19   14   53
  93   68

start: 1107849418
end  : 1107849706
elapsed time: 288 seconds

   0    2   14   19   38   49   53   58   60   68
  75   93

Sorting an array of 12 integers on my 3GHz 64-bit Athlon took 288 seconds, almost 5 minutes! This is because this algorithm takes O(n!) time. Sorting an array of 13 integers will take 13 times longer than the array of 12 integers, or about 65 minutes. Sorting an array of 14 integers takes 14 times longer than that, or 910 minutes, about 15 hours. Sorting an array of 17 integers will take about ten years. This is not a practical algorithm.


— Return to the main contents page