Array Type
The array type is a structured type: its definition refers to another type.
The term vector is used to designate a data of type array.
In Mathematics, a vector is defined by its components, and represented by a tuple: 
An array type variable is a data structure made up of a fixed number of elements of the same type, each identified by an index and accessible directly using its index.
Syntax: declaring an array type
type
identifier = array [type_of_index] of type_of_element;
type_of_index is the type of the index identifying the elements of the array, and must be a simple ordinal type: integer, char, boolean, enumerated or subrange.
type_of_element is the type of the elements of the array.
Example: array composed of five integer elements
type
quintuplet_of_int : array [1..5] of integer;
var
vector : quintuplet_of_int;
{ . . . }
vector[1] := 2;
Indices
Elements
| 1 | 2 | 3 | 4 | 5 |
| 2 | 3 | 5 | 7 | 11 |
Example: In point mechanics, the position and velocity of a point are each defined as a vector.
type
vector : array [1..3] of real;
var
position, velocity : vector;
Example: assign each letter of the alphabet a code between 1 and 26.
type
code_alphabet : array ['A'..'Z'] of 1..26;
var
code : code_alphabet;
c : char;
{ . . . }
{ initialize array elements }
for c := 'A' to 'Z' do
code[c] := 1 + ord(c) - ord('A');
{ . . . }
Example: the colors of inks used in printing are cyan, magenta, yellow and black. A color is defined as a combination of the primary colors.
type
primary_color = (cyan, magenta, yellow, black);
color = array [primary_color] of 0..100;
var
green : color;
{ . . . }
{ initialize array elements }
green[cyan] := 100;
green[magenta] := 0;
green[yellow] := 100;
green[black] := 0;
{ . . . }
Initializing an array
In the following examples, we will use the random() function to initialize the elements of an integer array with random values.
The random() function is used to generate a random integer between 0 and a given number.
Syntax
randomize; { reset the generator }
r := random(m); { generate a random integer between 0 et m }
Example: initialize an integer array with random values.
const
size = 10;
type
arr_int = array[1..size] of integer;
var
a : arr_int;
k : 1..size;
{ . . . }
randomize;
{ initialize array elements }
for k := 1 to size do
a[k] := random(100);
{ . . . }
Find the minimum in an array
In the following examples, we assume a priori the declaration of an array type as follows:
const
size = 10;
type
arr_int = array[1..size] of integer;
{ . . . }
Example
Write a function that receives an array of integers as a parameter and returns the smallest of its elements as a result.
function minimum(a : arr_int) : integer;
var
k : 1..size;
m : integer;
begin
m := a[1];
for k := 2 to size do
if a[k] < m then
m := a[k];
minimum := m;
end
Example
Write a function that receives an array of integers as a parameter and returns the index of the smallest of its elements as a result.
function index_minimum(a : arr_int) : integer;
var
k, index : 1..size;
m : integer;
begin
m := a[1];
k := 1;
index := 1;
for k := 2 to size do
if a[k] < m then
begin
m := a[k];
index := k;
end;
index_minimum := index;
end;
Example: in the following program we use the two previous functions.
program example;
const
size = 10;
type
arr_int = array[1..size] of integer;
var
a : arr_int;
i : 1..size;
function minimum(a : arr_int) : integer;
var
k : 1..size;
m : integer;
begin
m := a[1];
for k := 2 to size do
if a[k] < m then
m := a[k];
minimum := m;
end;
function index_minimum(a : arr_int) : integer;
var
k, index : 1..size;
m : integer;
begin
m := a[1];
k := 1;
index := 1;
for k := 2 to size do
if a[k] < m then
begin
m := a[k];
index := k;
end;
index_minimum := index;
end;
begin
randomize;
for i := 1 to size do
begin
a[i] := random(100);
write(a[i], ' ');
end;
writeln;
writeln('minimum: ', minimum(a));
writeln('minimum index: ', index_minimum(a));
end.
Permutation sort
We want to sort an array v[1..n].
Principle
We proceed in stages. Each stage corresponds to an index k.
Stage k
- Assume
v[1..k-1]is already sorted, and processv[k..n], - Find the minimum in
v[k..n], - Permute this minimum with
v[k], - Now
v[1..k]is sorted.:
Example: sort the integer array: v = [5, 3, 11, 2, 7]
k
1
2
3
4
5
v: sorted / not sorted.
/ 5, 3, 11, 2, 7
2,/ 3, 11, 5, 7
2, 3,/ 11, 5, 7
2, 3, 5,/ 11, 7
2, 3, 5, 7,/ 11
Index of minimum
4
2
4
5
Permute
5 and 2
none
11 and 5
11 and 7
end
Modules of Permutation Sort Program
Header and declarations
program permutation_sort;
const
size = 10;
type
index_range = 1..size;
arr_int = array[index_range] of integer;
var
arr : arr_int;
min : integer;
ind_min, index : index_range;
Procedure: initialize an integer array with random values.
procedure initialize(var a : arr_int);
var
k : index_range;
begin
randomize;
for k := 1 to size do
a[k] := random(100)
end;
Procedure: display the elements of an array.
procedure display(a : arr_int);
var
k : index_range;
begin
for k := 1 to size do
write(a[k],' ');
writeln;
end;
Function: find the minimum among the elements of an array of integers starting from a given index.
function minimum(s : index_range; a : arr_int) : integer;
var
k : index_range;
m : integer;
begin
m := a[s];
for k := s + 1 to size do
if a[k] < m then
m := a[k];
minimum := m;
end;
Function: find the index of the minimum among the elements of an array of integers starting from a given index.
function index_minimum(s : index_range; a : arr_int) : integer;
var
k, i : index_range;
m : integer;
begin
m := a[s];
k := s;
i := s;
for k := s + 1 to size do
if a[k] < m then
begin
m := a[k];
i := k;
end;
index_minimum := i;
end;
Procedure: permute two elements of an array.
Requires passing a parameter by variable to be able to modify the array.
procedure permute(k1, k2 : index_range; var a : arr_int);
var
t : integer;
begin
t := a[k1];
a[k1] := a[k2];
a[k2] := t;
end;
Main program body
begin
initialize(arr);
display(arr);
for index := 1 to size - 1 do
begin
min := minimum(index, arr);
ind_min := index_minimum(index, arr);
permute(index, ind_min, arr);
display(arr);
end;
end.
Permutation Sort Program
program permutation_sort;
const
size = 10;
type
index_range = 1..size;
arr_int = array[index_range] of integer;
var
arr : arr_int;
min : integer;
ind_min, index : index_range;
procedure initialize(var a : arr_int);
var
k : index_range;
begin
randomize;
for k := 1 to size do
a[k] := random(100)
end;
procedure display(a : arr_int);
var
k : index_range;
begin
for k := 1 to size do
write(a[k],' ');
writeln;
end;
function minimum(s : index_range; a : arr_int) : integer;
var
k : index_range;
m : integer;
begin
m := a[s];
for k := s + 1 to size do
if a[k] < m then
m := a[k];
minimum := m;
end;
function index_minimum(s : index_range; a : arr_int) : integer;
var
k, i : index_range;
m : integer;
begin
m := a[s];
k := s;
i := s;
for k := s + 1 to size do
if a[k] < m then
begin
m := a[k];
i := k;
end;
index_minimum := i;
end;
procedure permute(k1, k2 : index_range; var a : arr_int);
var
t : integer;
begin
t := a[k1];
a[k1] := a[k2];
a[k2] := t;
end;
begin
initialize(arr);
display(arr);
for index := 1 to size - 1 do
begin
min := minimum(index, arr);
ind_min := index_minimum(index, arr);
permute(index, ind_min, arr);
display(arr);
end;
end.