ARRAYS

-----

Suppose we want to find the maximum value of 5 integer values

stored in variables called value0, value1, value2, value3, value4.
The following portion of code will achieve the desired result:

int maximum = value0;

if value1 > maximum
maximum = value1;
if value2 > maximum
maximum = value2;
if value3 > maximum
maximum = value3;
if value4 > maximum
maximum = value4;

Note how 4 separate if statements were required and a total of

5 separate integer variables were needed to hold the values being
compared.

One can easily see how such an approach would not be practical
to find the maximum of 1000 integer values.

C++ allows for the array data type to simplify such situations in
which
one is working with a set of similar data items. An array is simply
a collection of similar items referred to by a single common name in
which
every individual item or element in the collection can be
individually referenced.

The following program defines and initializes an array of 10

integers:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// an array

#include <iostream>
#include <string>

using namespace std;

int main()
{

// declare and initialize an array of 10 integers

int my_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

// use a for loop to sequentially access the individual

// elements of the array

for(int i = 0 ; i <=9; i++)

cout << "my_array[" << i << "] = " << my_array[i] << endl;

return 0;
}

The program produces the following output:

ted@flash Programs 8:16pm >array

my_array[0] = 12
my_array[1] = 234
my_array[2] = 23
my_array[3] = 1
my_array[4] = -7
my_array[5] = 55
my_array[6] = 18
my_array[7] = 67
my_array[8] = 99
my_array[9] = 100
ted@flash Programs 8:16pm >

In general arrays are declared in the following manner:

base_type_of_elements name_of_the_array[ size_expression ]

where

base_type_of_elements: is the type of each array element such as

char, int, float, double, etc...
(it is even possible to have an array of
structs)

name_of_the_array : is an indentifier which specifies the name of

the array

size_expression: is an constant or a constant expression which

identifies
the SIZE of the array.
The expression must be capable of being evaluated
to integer
value at COMPILE time.

Some examples of legal array declarations are:

float some_real_numbers[25] ; // an array of 25 floats

char two_letters[2] ; // an array which can hold two chars
const int m = 5;
const int = 4;

Some illegal array definitions are:

float some_real_numbers[25.5] ; // an array of 25 floats

const float m=4 ;
const float n=5 ;
int an_array[m*n];

The above are illegal since non-integer types are used to specify
the array sizes:

illegal_array_definitions.C:18: size of array `some_real_numbers'

has non-integer type
illegal_array_definitions.C:21: size of array `an_array' has non-
integer type

int an_array[m*n];
Let us explore this issue of the array size specifier being a
CONSTANT integer
expression:

Here is a C program which attempts to use an integer variable y to

specify
the size of an integer array called x:

#include <stdio.h>

int main()
{
int y;
int x[y];
return 0;

This program does NOT compile with the Sun C Compiler :

ted@townshend JUNK 1:06pm >/opt/SUNWspro/bin/cc array3.c

"array3.c", line 6: integral constant expression expected
cc: acomp failed for array3.c

The Sun compiler is very strict, it is complaining (vehemently) that

it is illegal to use an non integral constant expression to specify
the
size of an array.

Let us now compile the program using g++:

ted@townshend JUNK 1:07pm >g++ array3.c

ted@townshend JUNK 1:08pm >

Oddly enough, the g++ compiler compiles the source code with no
warnings and
no errors and it produces an executable program called a.out :
ted@townshend JUNK 1:08pm >ls -al a.out
-rwx------ 1 ted staff 6064 Oct 18 13:06 a.out

Let's add a little more functionality to our program and try to

compile it
with g++ and run it:

#include <iostream>

int main()
{
int y;
cout << "Enter the array size " << endl;

cin >> y;

int x[y];
for(int i = 0 ; i < y ; i++)
{
cout << "Enter the value " ;
cin >> x[i];
}

for(int i = 0 ; i < y ; i++)

cout << x[i] << endl;

ted@townshend JUNK 1:09pm >g++ -o array array.C

ted@townshend JUNK 1:10pm >

It compiles fine... it even runs fine:

ted@townshend JUNK 1:10pm >array

Enter the array size
4
Enter the value 1
Enter the value 2
Enter the value 3
Enter the value 4
1
2
3
4

Let's change the program slightly, so that we input the value of y

AFTER,
we declare the array x:

#include <iostream>

int main()
{
int y;
cout << "Enter the array size " << endl;

#include <iostream>

int main()
{
int y;

int x[y];

cout << "Enter the array size " << endl;

cin >> y;

for(int i = 0 ; i < y ; i++)

{
cout << "Enter the value " ;
cin >> x[i];
}

for(int i = 0 ; i < y ; i++)

cout << x[i] << endl;
}

This program compiles fine with the g++ compiler:

ted@townshend JUNK 1:11pm >g++ -o array2 array2.C

HOWEVER, during run time, a SEGMENTATION FAULT occurs:

ted@townshend JUNK 1:11pm >array2

Segmentation fault

It appears that the issue of the array size specifier being an

integer constant
is compiler-dependent. The Sun C compiler is the most strict, there
may be
some command-line options with g++ which may tell the compiler to be
more strict
about these issues....

Here they are:

ted@brownsugar Programs 5:19pm >g++ -Wall -pedantic -o

dynamic_size_array dynamic_size_array.C
dynamic_size_array.C: In function `int main()':
dynamic_size_array.C:30: error: ISO C++ forbids variable-size array
`array'

These small examples help to prove that one does not know what will
occur with
a program until you actually compile and run it (using DIFFERENT )
compilers.

It would be interesting to see how the Microsoft Visual C++ compiler

would
handle these examples. Unfortunately, I do not have access to
Microsoft
Visual C++.

Paul Lambert, a student, has reported that Visual C++ reports:

1>.\Test.cpp(18) : error C2466: cannot allocate an array of constant

size 0

1>.\Test.cpp(18) : error C2133: 'x' : unknown size

In C++, array element number ALWAYS BEGINS with 0 for the first
array element, 1 for the second array element, 2 for the third
array element, etc. The programmer has no choice in this numbering
sequence (unlike the Pascal and BASIC programming languages).

The elements of an array ARE STORED IN CONTIGUOUS MEMORY LOCATIONS.

This following program prints out the 10 array elements as well
as the address in main memory where each element is stored:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// an array

#include <iostream>
#include <string>
#include <iomanip>

using namespace std;

int main()
{
// declare and initialize an array of 10 integers

int my_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

// use a for loop to sequentially access the individual

// elements of the array

for(int i = 0 ; i <=9; i++)

cout << "my_array[" << i << "] = " << my_array[i] <<
" stored at address " <<( (unsigned long) &my_array[i])
<< endl;

return 0;
}

Note the use of the & operator in front of the &my_array[i]. This
operator is used to return the main memory address which is used
to store the variable. Nore how we cast this value into an unsigned
long integer to avoid having addresses given in their default
hexadecimal
value.

The output is:

ted@flash Programs 8:52pm >array_address

my_array[0] = 12 stored at address 4290704856
my_array[1] = 234 stored at address 4290704860
my_array[2] = 23 stored at address 4290704864
my_array[3] = 1 stored at address 4290704868
my_array[4] = -7 stored at address 4290704872
my_array[5] = 55 stored at address 4290704876
my_array[6] = 18 stored at address 4290704880
my_array[7] = 67 stored at address 4290704884
my_array[8] = 99 stored at address 4290704888
my_array[9] = 100 stored at address 4290704892

Note how an integer occupies 4 successive bytes in main memory.

If we had not cast the address as an unsigned long integer, the

addresses wold be given in hexadecimal as:

my_array[0] = 12 stored at address 0xffbef5d8

my_array[1] = 234 stored at address 0xffbef5dc
my_array[2] = 23 stored at address 0xffbef5e0
my_array[3] = 1 stored at address 0xffbef5e4
my_array[4] = -7 stored at address 0xffbef5e8
my_array[5] = 55 stored at address 0xffbef5ec
my_array[6] = 18 stored at address 0xffbef5f0
my_array[7] = 67 stored at address 0xffbef5f4
my_array[8] = 99 stored at address 0xffbef5f8
my_array[9] = 100 stored at address 0xffbef5fc

ARRAY BOUNDS
------------

C++ does not prevent the programmer from exceeding the boundaries
of an array. This may cause strange program behavior leading to
incorrect results. For example:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating
// exceeding an arrays bounds

#include <iostream>
#include <string>

using namespace std;

int main()
{

// define and initializr an array of 14 characters

char my_array[14] = {'K','E','I', 'T', 'H', ' ',

'R','I','C','H','A','R','D','S' };
// use a for loop to sequentially access the individual
// elements of the array and intentionally go beyond
// the end of the arrat

for(int i = 0 ; i <=19; i++)

cout << "my_array[" << i << "] = " << my_array[i] << endl;

return 0;
}

The output is:

ted@flash Programs 9:04pm >bounds

my_array[0] = K
my_array[1] = E
my_array[2] = I
my_array[3] = T
my_array[4] = H
my_array[5] =
my_array[6] = R
my_array[7] = I
my_array[8] = C
my_array[9] = H
my_array[10] = A
my_array[11] = R
my_array[12] = D
my_array[13] = S
my_array[14] = �
my_array[15] =
my_array[16] =
my_array[17] =
my_array[18] =
my_array[19] =

Note how the values for my_array[14] through to my_array[19] are

simply attempt to interpret the bit patterns found in these main
memory locations as characters.

C++ even lets a programmer inadvertently supply a negative

value as an array index (and go to a memory location which
PRECEDES the first array element) :

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// an array

#include <iostream>
#include <string>
#include <iomanip>

using namespace std;

int main()
{

// declare and initialize an array of 10 integers

int my_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

// use a for loop to sequentially access the individual

// elements of the array

for(int i = -2 ; i <=9; i++)

cout << "my_array[" << i << "] = " << my_array[i] <<
" stored at address " <<( &my_array[i]) << endl;

return 0;
}

The output is:

ted@flash Programs 7:10pm >array_address2

my_array[-2] = 0 stored at address 0xffbef5d0
my_array[-1] = -1 stored at address 0xffbef5d4
my_array[0] = 12 stored at address 0xffbef5d8
my_array[1] = 234 stored at address 0xffbef5dc
my_array[2] = 23 stored at address 0xffbef5e0
my_array[3] = 1 stored at address 0xffbef5e4
my_array[4] = -7 stored at address 0xffbef5e8
my_array[5] = 55 stored at address 0xffbef5ec
my_array[6] = 18 stored at address 0xffbef5f0
my_array[7] = 67 stored at address 0xffbef5f4
my_array[8] = 99 stored at address 0xffbef5f8
my_array[9] = 100 stored at address 0xffbef5fc

The program attempts to interpret the random bit

patterns found in the 8 preceding bytes from
address 0xffbef5d8 as integer values and prints
them out.

We can now rewrite our program which finds the maximum of

a list of items making use of array notation:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// an array to store 10 numbers and
// find the maximum value

#include <iostream>
#include <string>

using namespace std;

int main()
{

// declare and initialize an array of 10 integers

int my_array[10] ;

for(int i = 0 ; i <=9; i++)

{
cout << "Enter an integer " ;
cin >> my_array[i];
}

int max = my_array[0];

for(int i = 1; i <= 9; i++)

if ( my_array[i] > max)
max = my_array[i];

cout << "Max is " << max << endl;

return 0;
}

The output is:

ted@flash Programs 9:19pm >max_array

Enter an integer 1
Enter an integer 2
Enter an integer 3
Enter an integer 4
Enter an integer 5
Enter an integer 6
Enter an integer 7
Enter an integer 8
Enter an integer 9
Enter an integer 10
Max is 10

ARRAY INITIALIZATION
--------------------

C++ supports various methods of specifying the initial values

of array elements.

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating
// different methods of array initialization

#include <iostream>
#include <string>

using namespace std;

int main()
{

// declare and initialize an array of 10 integers

// by giving the values of all 10 elements in a
// comma spearated list enclosed in curly parentheses

int my_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

// declare and initialize an array of 5 integers by

// explicitly initializing the first element to 5,
// the remaining unspecified elements will be set to 0
// also by the compiler

int array2[5] = {5};

// use a for loop to sequentially access the individual

// elements of the array

for(int i = 0 ; i <=9; i++)

cout << "my_array[" << i << "] = " << my_array[i] << endl;

for(int i = 0 ; i <=4; i++)

cout << "array2[" << i << "] = " << array2[i] << endl;

return 0;
}
The output is:

my_array[0] = 12
my_array[1] = 234
my_array[2] = 23
my_array[3] = 1
my_array[4] = -7
my_array[5] = 55
my_array[6] = 18
my_array[7] = 67
my_array[8] = 99
my_array[9] = 100
array2[0] = 5
array2[1] = 0
array2[2] = 0
array2[3] = 0
array2[4] = 0

ARRAY INITIALIZATION WITHOUT SPECIFYING AN EXPLICIT ARRAY SIZE

--------------------------------------------------------------

It is possible to initialize an array without specifying it size.

The compiler will determine the array size by counting the number
of expressions encountered in the intialization list.
A few examples illustrare this:

int numbers[] = {0,1,2,3,4,5,6,7,8,9} ;

char lower_case_vowels[] = {'a','e','i','o','u'}

The size of the numbers array will be set to 10 and the size
of the lower_case_vowels array will be set to 5.

CHARACTER ARRAY STRING INITIALIZATION

-------------------------------------

C++ allows for an alternate initialization of character

arrays which uses a character string (enclosed in
double quotes) to specify the individual initial values
of the array elements:

For example:

char my_name[] = "Ted";

will create and intialize an array of FOUR elements:

my_name[0] = 'T'
my_name[1] = 'e'
my_name[2] = 'd'
my_name[3] = `\0`

The last element of the my_name array is initialized to the NULL

CHARACTER
(`\0`). The null character is used in C++ to indicate the end of a
string.

Character arrays which have been intialized in such a fashion may

either be printed out element by element or by simply sending
the array directly to the cout stream with the << manipulator:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// character array strings

#include <iostream>
#include <string>

using namespace std;

int main()
{

char my_name[] = "Ted";

// print out the array element by element

for(int i = 0; i <= 3; i++)

cout << my_name[i] ; // null character will cause nothing to be
printed.

cout << endl;

// alternate method of printing out character array strings

cout << my_name << endl; // will print out all the characters in the
array
// up to but not including the null
character

return 0;
}

The output is the same in both cases:

Ted
Ted

Here are some more examples of different ways of initializing

array to the same initial value and different ways of
printing out the identical results:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// character array strings

#include <iostream>
#include <string>

using namespace std;

int main()
{

// four ways to intialize an array to the same values

char my_name1[] = "Ted";

char my_name2[4] = {'T','e','d','\0'};
char my_name3[] = {'T','e','d','\0'};
char my_name4[4] = "Ted";

// print out the array element by element

for(int i = 0; i <= 3; i++)

cout << my_name1[i] ; // null character will cause nothing to be
printed.

cout << endl;

for(int i = 0; i <= 3; i++)

cout << my_name2[i] ; // null character will cause nothing to be
printed.

cout << endl;

for(int i = 0; i <= 3; i++)

cout << my_name3[i] ; // null character will cause nothing to be
printed.

cout << endl;

for(int i = 0; i <= 3; i++)

cout << my_name4[i] ; // null character will cause nothing to be
printed.

cout << endl;

cout << endl;

cout << my_name1 << endl << my_name2 << endl << my_name3 << endl <<
my_name4 << endl;

// can even print out a character string array by passing the

ADDRESS of the first
// element in the array to cout !!!

cout << &my_name1[0] << endl << &my_name2[0] << endl << &my_name3[0]
<< endl << &my_name4[0] << endl;

// this will print out the letter 'T'

cout << my_name1[0] << endl;

return 0;
}

The output is:

ted@flash Programs 10:14pm >string_array2

Ted
Ted
Ted
Ted

Ted
Ted
Ted
Ted
Ted
Ted
Ted
Ted
T

Reading in character arrays from the keyboard

---------------------------------------------
Character arrays may be read in directly from the keyboard using a
simple

cin >> name_of_array ;

statement . Any other type of array ( array of ints, array of

floats, array of doubles)
cannot be read in entirely in a similar fashion, they have to be
entered element by element
within a loop as in :

int number_array[5];

for(int i = 0 ; i < 5 : i++)

cin >> number_array[i];

When a character array is readin directly from the keyboard, the

end-of-string
character ('\0' is added after the last character is entered by
pressing the
enter key of the keyboard).

Here is a simple program which illustrates these concepts. It

declares a character
array of up to 80 chars which is used to store a name which the user
enters from the
keyboard. Pressing the Enter key terminates the input (and stores
the '\0' character
into the array ). The program then prints out the array in reverse
element by first
locating the array index which corresponds to where the '\0' is
stored, then using
a for loop from this index value backwards to value 0 to print out
each individual array
element:

// Author: Ted Obuchowicz

// file: read_in_word.C
#include <iostream>
#include <string>

using namespace std;

int main()
{

char word[80]; // reserve up to 80 characters

cin >> word; // read in the entire string from the keyboard
directly

cout << word << endl; // print it out .. this will print only up
to the '\0'

// use a for loop to print out the ENTIRE 80 characters...

int index = 0;
for ( ; index < 80; index++)
{
cout << "word[" << index <<"] = " << word[index] << endl;
}

// find where the '\0' is stored which indicated the end of the
entered word

index = 0;

for( ; index < 80; index++)

{
if (word[index] == '\0' )
break;
}

// print the string backwards

for (int i = index - 1 ; i >= 0 ; i--)

cout << word[i] ;
cout << endl;

return 0;
}

The output produced by the program is:

ted@brownsugar Programs 9:56pm >read_in_word

abc ( the user types in this word )
abc ( produced by cout << word statment )
word[0] = a (produced by the for loop which loops thru all 80
elements of the array)
word[1] = b
word[2] = c
word[3] = ( this is what the '\0' produced when fed in to cin
<< )
word[4] = � ( these are non-ASCII characters which happened to be
stored in some locations)
word[5] = #
word[6] = �
word[7] =
word[8] = �
word[9] = $
word[10] =
word[11] = �
word[12] =
word[13] =
word[14] =
word[15] =
word[16] =
word[17] =
word[18] =
word[19] =
word[20] =
word[21] =
word[22] =
word[23] =
word[24] =
word[25] =
word[26] =
word[27] =
word[28] = �
word[29] = ?
word[30] =
word[31] = �
word[32] =
word[33] =
word[34] =
word[35] =
word[36] =
word[37] =
word[38] =
word[39] =
word[40] =
word[41] =
word[42] =
word[43] =
word[44] =
word[45] =
word[46] =
word[47] =
word[48] =
word[49] =
word[50] =
word[51] =
word[52] =
word[53] =
word[54] =
word[55] =
word[56] = �
word[57] = �
word[58] = �
word[59] = �
word[60] =
word[61] =
word[62] =
word[63] = �
word[64] = �
word[65] = =
word[66] =
word[67] = �
word[68] =
word[69] =
word[70] =
word[71] =
word[72] =
word[73] =
word[74] =
word[75] =
word[76] =
word[77] =
word[78] =
word[79] =
cba ( this is produced by printing out the backwards word
starting from one position
( before the '\0' character )

PASSING ARRAYS TO FUNCTIONS

----------------------------

Consider the following program which passes an array of 5 elements

to
to a function. The function simple sets the value of all the array
elements to 0 and returns back to the calling program:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating
// how arrays are passed to functions

#include <iostream>
#include <string>

using namespace std;

void how_are_arrays_passed(int param[], int size_of_array)
{
for (int i = 0 ; i < size_of_array; i++)
param[i] = 0; // set all the elements to 0
}

int main()
{

// declare and initialize an array of 5 integers

int array[5] = {100, 100, 100, 100, 100};

// use a for loop to sequentially access the individual

// elements of the array

cout << "Before function : " << endl;

for(int i = 0 ; i <=4; i++)

cout << "array[" << i << "] = " << array[i] << endl;

how_are_arrays_passed(array,5);

cout << "After function : " << endl;

for(int i = 0 ; i <=4; i++)

cout << "array[" << i << "] = " << array[i] << endl;

return 0;
}

The program output may be surprising to a few readers:

Before function :
array[0] = 100
array[1] = 100
array[2] = 100
array[3] = 100
array[4] = 100
After function :
array[0] = 0
array[1] = 0
array[2] = 0
array[3] = 0
array[4] = 0

AHHHH!!!! the values of the array elements in the main program were
actually changed by the function!!!

It would be inefficient to pass an array using thr call-bu value

mechanism (imagine copying a 1 000 000 element array into a
function's stack frame every time to function is invoked, this
would have dramatic effects on a program's run time and memory
requirements).

In C++ (and in good old C) ARRAYS ARE ALWAYS PASSED AS REFERENCE

PARAMETERS. NO & IS NEITHER NEEDED NOR EXPECTED IN THE ARRAY
PARAMETER DEFINITION.

A few astute readers may have noticed that in the definition of

the array parameter to the function no array size was specified.
C++ allows the size to be left out so that the function may work
with array
arguments of different size. Of course, a second integer parameter
is passed
to the function idnicating the actual size of the array which the
function
will be working with during the course of its execution.

SEARCHING A NON-SORTED ARRAY (LINEAR SEARCH)

-----------------------------------------

Suppose we wish to search an array (which contains elements in

non-sorted order) to see if it contains a particular element (the
key).
If the element is in the array, we want to (first) index of
where it occurs, otherwise a message saying the element is not
contained in the array is to be displayed. We can perform
a LINEAR SEARCH on the array starting from the first array
element and comparing it with the key, we keep on comparing
successive array elements with the key until we either find
a match or reach the end of the array. This is known as a
LINEAR SEARCH of an array. It requires a number of
comparisons which is proportional to the size, n, of the array.
In computer science terminology, we say that the "order of
complexity of a linear search of an array of n elements is
O(n)" .

Here is an implementation of the linear search in C++:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// linear search on an array to find a key

#include <iostream>
#include <string>

using namespace std;

int main()
{

// declare and initialize an array of 10 integers

int my_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

int key;
cout << "enter the key value to be searched for";
cin >> key;

int array_index; // define this outside the for loop

// since we want to know its value upon
// loop termination

bool found = false;

for( array_index = 0 ; array_index <=9; array_index++)
{
if (my_array[array_index] == key)
{
found = true;
break;
}
}

if (found)
cout << "Key found in position " << array_index << " " <<
my_array[array_index] << endl;
else
cout << "Key is not in the array." << endl;

return 0;
}

We can employ recursion to perform a linear search of an unordered

array.
We simply start from the beginning of the array, if the first
element
of the array matches the key, a message is displayed, if there is no
match
we make a recursive call with the remaining elements of the array.
Eventually,
all the elements will be compared one-by-one with the key resulting
in either
a match or the key not being found :

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// linear search on an array to find a key
#include <iostream>
#include <string>

using namespace std;

void linear_search(int array[], int start , int size, int key)

{
if (key == array[start])
cout << "key found in array[" << start << "]" << endl;
else
if ( start == (size-1) )
cout << "key not found." << endl;
else
linear_search(array, start+1, size, key);
}

int main()
{

// declare and initialize an array of 10 integers

int my_array[10] = {-56, 0, 5, -234, 1, 12, -3, 678, 34, 100 };

int key;
cout << "enter the key value to be searched for " ;
cin >> key;

linear_search(my_array, 0, 10, key);

return 0;
}

SORTING AN ARRAY LINEARLY

--------------------------

Sorting a set of data into some numeric order (increasing order or

decreasing order) is a commonly required task in data processing.
Here is a C++ program which performs a LINEAR SORT on an array
of 10 elements:

// Author: Ted Obuchowicz

// Feb. 13, 2002
// example program illustrating use of
// linear sort on an array to sort it into
// ascending order (smallest to largest value)

#include <iostream>
#include <string>

using namespace std;

void print_array(int some_array[], int size)

{
for(int i = 0 ; i < size ; i++)
cout << some_array[i] << endl;
}

int main()
{

// declare and initialize an array of 10 integers

int unsorted_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

cout << "The unsorted array is: " << endl;

print_array(unsorted_array, 10);

int sorted_array[10];

// now sort the array in place

for(int i = 0 ; i < 10 ; i++)

{
int smallest = unsorted_array[i];
for(int j = i+1 ; j <10; j++)
 {
if (unsorted_array[j] < smallest)
{
smallest = unsorted_array[j]; // found a new smallest value
in array
int temp = unsorted_array[i]; // now swap the two array
elements
unsorted_array[j] = temp;
unsorted_array[i] = smallest;
}
}
}

cout << "The sorted array is: " << endl;

print_array(unsorted_array, 10);

return 0;
}

The program output is:

The unsorted array is:

12
234
23
1
-7
55
18
67
99
100
The sorted array is:
-7
1
12
18
23
55
67
99
100
234

New and Improved sorting program

----------------------------------

Here is a simpler version of the previous array sorting example

program.
It does not make use of the "int smallest" variable which was
introduced
during preliminary program debugging. It simply "swaps" the two
array
elements if necessary within the for loop.

// linear sort on an array to sort it into

// ascending order (smallest to largest value)

#include <iostream>
#include <string>

using namespace std;

// a function to print out the elements of an array

void print_array(int some_array[], int size)

{
for(int i = 0 ; i < size ; i++)
cout << some_array[i] << endl;
}

int main()
{
// declare and initialize an array of 10 integers

int unsorted_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};

cout << "The unsorted array is: " << endl;

print_array(unsorted_array, 10);

// now sort the array in place

for(int i = 0 ; i < 10 ; i++)

{
for(int j = i+1 ; j <10; j++)
{
if (unsorted_array[j] < unsorted_array[i])
{
int temp = unsorted_array[i]; // now swap the two array
elements
unsorted_array[i] = unsorted_array[j];
unsorted_array[j] = temp;
}
}
}

cout << "The sorted array is: " << endl;

print_array(unsorted_array, 10);

return 0;
}

This program can be further refined by making use of a "swap"

function which
swaps the two array elements when we find (unsorted_array[j] <
unsorted_array[i] )
to be true within the nested loop as in:

#include <iostream>
#include <string>

using namespace std;

// a function to print out the elements of a 1-dimensional array

void print_array(int some_array[], int size)

{
for(int i = 0 ; i < size ; i++)
cout << some_array[i] << endl;
}

// a function which swaps two elements of the array

// note since arrays are always passed by REFERENCE
// the swap occurs on the actual array which is passed to the
function

void swap_elements(int some_array[], int first, int second)

{
int temp;
temp = some_array[second];
some_array[second] = some_array[first];
some_array[first] = temp;
}

int main()
{

// declare and initialize an array of 10 integers

int unsorted_array[10] = {12, 234, 23, 1, -7, 55, 18, 67, 99, 100};
cout << "The unsorted array is: " << endl;
print_array(unsorted_array, 10);

// now sort the array in place

for(int i = 0 ; i < 10 ; i++)

{
for(int j = i+1 ; j <10; j++)
{
if (unsorted_array[j] < unsorted_array[i])
{
swap_elements(unsorted_array, i,j); // can also do
swap_elements(unsorted_array, j , i)
}
}
}

cout << "The sorted array is: " << endl;

print_array(unsorted_array, 10);

return 0;
}

Either version of the program (as the original, somewhat confusing

version) produces
the correct output:

The unsorted array is:

12
234
23
1
-7
55
18
67
99
100
The sorted array is:
-7
1
12
18
23
55
67
99
100
234

Note how the use of the swap_elements(unsorted_array, i,j) function

call within the
nested loops improves program readability.