Arrays

An array is a data structure that consists of a set of values of the same data type.

Format for declaring an array: data_type array_name[number of values to hold];

A declaration for an array that holds 15 real numbers might resemble:

float  RealAr[15];

The number inside the square brackets [] is called a subscript. It’s used to reference a certain element of the array.

Subscripts start from 0 and run to N-1 (where N is the value within the square brackets). So RealAr has subscripts from 0 to 14.

Subscripts are ALWAYS an integer – so elements can be referenced using:

Literal/hardcoded value -- 4
Variable -- n
Integer expression -- n – 2
Scalar expression -- ‘A’
Any function that returns an integer value -- min(4, x)

To refer to a specific element in the array: array_name[subscript number]

So to get the first element in RealAr you would code: RealAr[0]

NOTES on arrays:

Can be initialized when they are declared

char vowels[5] = {‘a’, ‘e’, ‘i’, ‘o’, ‘u’};

For numerical arrays – if all of the spaces are not initialized, the remaining ones are set to 0

int IntAr[10] = {2, 4, 6, 8};

The number of elements in the array is not always used when declaring an array

int  IntAr[] = {3, 5, 7};

Special way to initialize char arrays

char LastName[10] = "Byrnes";

Passing arrays to functions

Functions CAN alter the values in an array that is declared in main.

Prototype format: Return_data_type  function_name(array_data_type []);

Function header format: Return_data_type  function_name(array_data_type  array_name[]);

Calling statement format: function_name(array_name)

Sorting Arrays

It’s usually helpful when we have an array to be able to put it in some sort of order (be it numerical or alphabetical).

There are many algorithms to sort a list. Some are simple and some are complex. Some are fast while others are slow. We’ll look at a few of the most common ones.

Selection sort

Imagine you have a list of number (characters, strings, etc…)

8   4   2   5   3   7

Look through the list and find the smallest. Exchange the smallest with the first item in the list.

2   |   4   8   5   3   7

Now look through everything to the right of the | for the smallest. Exchange the smallest with the first item in the list to the right of the |

2   3   |   8   5   4   7

Repeating the steps results in:

2   3   4   |   5   8   7

2   3   4   5   |   8   7

2   3   4   5   7   |   8

2   3   4   5   7   8   |

PSEUDOCODE:

TOP => subscript of the first element
LAST => subscript of the last element
SSF => subscript of the smallest element
PTR => subscript to go through the array

DO WHILE (TOP < LAST)
   PTR = TOP
   SSF = TOP
   DO WHILE (PTR < LAST)
      IF (AR[PTR] < AR[SSF])
         SSF = PTR
      ENDIF
      PTR = PTR + 1
   ENDDO
   SWAP AR[TOP] and AR[SSF]
   TOP = TOP + 1
ENDDO

Bubble Sort

The smallest element "bubbles" to the top of the array

Accomplished by comparing adjacent elements. If elements are in increasing order or equal, nothing is done. If elements are in decreasing order, the elements swap positions.

1 pass => largest element at bottom of array

8    4    2    5    3    7

PSEUDOCODE:

I, J => subscripts to go through the array
END => subscript of the last element
FLAG => indicates that a swap has occurred (1 = yes, 0 = no)

FLAG = 1
DO WHILE (FLAG = 1  AND  END > 0)
   I = 0
   J = 1
   FLAG = 0
   DO WHILE (J <= END)
      IF (AR[I] > AR[J])
         FLAG = 1
         SWAP AR[I] and AR[J]
      ENDIF
      I = I + 1
      J = J + 1
   ENDDO
   END = END - 1
ENDDO

Insertion Sort

This sort starts with the first two elements of the list and puts them in order. The third element is then added. The new list of three elements is put in order. This process continues until the entire list is in order.

In other words, as an element is added to the list, it is inserted into the correct position

8    6    2    3    5    1

PSEUDOCODE:

LOW => subscript of the first element
HIGH => subscript of the last element
J, K => subscripts

J = LOW + 1
DO WHILE (J <= HIGH)
   K = J
   DO WHILE (K > LOW  AND  AR[K] < AR[K-1])
      SWAP AR[K] and AR[K-1]
      K = K - 1
   ENDDO
   J = J + 1
ENDDO

Multi-Dimensional Arrays

The elements of an array may be of any type. They could even be an array. This type of array is known as a multi-dimensional array.

For a 2-dimensional array:

data_type array_name[number of ROWS][number of COLUMNS];

int twoDar[4][7]

To refer to a specific element in the array, must specify two subscripts.

twoDar[1][4]

this refers to the element in the second row (subscript 1) in the fifth column (subscript 4).

It's also possible to refer to a specific row:

twoDar[2]

this refers to the third row of the array.

Initializing a multi-dimensional array

An array can be initialized when it is created in a few different ways:

int twoDar[3][4] = { 2, 4, 6, 8, 1, 3, 5, 7, 10, 11, 12, 13 };

The first row (twoDar[0]) will have the values 2, 4, 6, and 8

int twoDar[3][4] = { {2, 4, 6, 8}, {1, 3, 5, 7}, {10, 11, 12, 13} };

this will produce the same results as the first declaration

As with single dimensional arrays, if enough values are not specified, the remaining positions will be assigned the value 0.

int twoDar[3][4] = { 2, 4, 1, 3, 5, 10, 11, 12, 13 };

int twoDar[3][4] = { {2, 4}, {1, 3, 5}, {10, 11, 12, 13} };

These will produce very different results.

Passing multi-dimensional arrays to functions

Multi-dimensional arrays are passed to functions in the same manor as single dimensional arrays. The difference lies in the function prototype and header.

The prototype and header both need the number of columns to be supplied.

Prototype: return_type  func_name(data_type [][# columns]);

Header:    return_type  func_name(data_type array_name[][# columns])