We want to output the characters of a string to be entered by the user in sorted order. (At first this formulation may seem artificial; however, we will come up against it again in Section 2.3.5 as a basic constituent of a certain method for clustering strings). We use a simple sorting algorithm for that purpose.

In the first step we search for the “smallest” character, that is, the character that comes first in the lexicographical order of all characters^[7], and swap it with the first character (which stands at position 0). In the second step we search for the smallest character in the residual array, which starts at position 1, and swap it (this being the second smallest character in the overall array) with the character at position 1. In the third step we search etc. Generally, in the i-th step we search in the residual array starting at position i-1 for the smallest character and swap it with the character at position i-1. Having n characters altogether, the characters are in the correct order after n steps (iterations).^[8] (Actually, n-1 iterations are enough because the last residual array, which consists of only one single character, is already in correct order. This sorting method is called sorting by minimum search.

As we see, it is important for a sorting algorithm to be able to access the individual characters by their position (called index) and to swap them. The data structure of choice for this is the array. So we read in a string and store its individual characters as elements of an array, then sort the array according to the method just outlined and finally write the characters back again in sorted order into the string. We use the LEDA class array for this purpose.

#include <LEDA/array.h>
#include <LEDA/string.h>
#include <LEDA/misc.h>
#include <iostream>

using leda::array;
using leda::string;
using std::cout;

int main() 
{
  string s;

  s = leda::read_string("Please enter a string: ");

  int n = s.length();

  array<char> A(n);

  // copy chars into array
  for(int i = 0; i < n; i++)
    A[i] =  s[i];

  // sort array
  for(int i = 0; i < n-1 ; i++) {
    char min = A[i]; // minimal element seen so far
    int min_pos = i; // memorize its position
    // search for min starting from position i+1
    for(int j = i + 1; j < n; j++) 
      if(A[j] < min) {
        min = A[j];
        min_pos = j;
      }
    // swap elements at positions i and min_pos
    A[min_pos] = A[i];
    A[i] = min;
  }

  // copy chars back into string, overwriting old ordering
  for(int i = 0; i < n; i++)
    s[i] =  A[i];

  cout << s << "\n";
}

A sample run of the program is the following:

Please enter a string: Jumping Jack Flash
  FJJaacghiklmnpsu

The LEDA class array is our first example of a container type. This is a data structure in which a collection of (uniform) objects can be held. In this context, the objects are also called elements. The type of the elements of an array is a type parameter, which must be specified at the declaration of the array. In our example we store single characters in the array A; so the array is of type array<char>. Figure 2.1 shows an array with the characters of the example run.

Figure 2.1. An array of characters

This array consists of n=18 characters. The index of the first character is 0, the index of the last one is 17.

The number of elements that an array shall store can be specified in the definition. However, unlike with ordinary C++ arrays, this number does not have to be known at compilation time; it may very well be variable, as the above definition

array<char> A(n);

with a variable n points out. As we will see soon, it can be even completely left out since LEDA arrays can be enlarged to any arbitrary size at runtime.

Like in C++ and other programming languages the individual elements of the array can be accessed by the subscript operator. A[0] denotes the first element of the array; to be more precise, the operator [] returns a reference to this element. Thereby the value of an element can be read or set anew:

A[0] = 'P'; 

turns the Jumping Jack Flash into the Pumping Jack Flash.

To read the string we have used the function read_string() here, which is declared like other useful small functions in the header file misc.h. It outputs a prompt, lets the user enter a string, and returns this string.

Now we could say: Actually, we would not have needed the slightest array for this sorting anyway, in fact, we can also access the individual characters of the string by the operator []! Consequently, we could sort right inside the string itself without the detour via an array. This is correct and an experienced LEDA programmer would never write a sorting method himself because all conceivable efficient sorting algorithms are already built into LEDA, of course. We would also have been able to make our sorting life easier by using the array method

A.sort(); 

To use this method here, we must copy the characters of the string into an array, sort the array and then write the characters back again into the string:

#include <LEDA/array.h>
#include <LEDA/string.h>
#include <iostream>

using leda::array;
using leda::string;
using std::cout;

int main() 
{
  string s;

  cout << "Please enter a string: ";

  s.read_line();

  int n = s.length();

  array<char> A(n);

  for(int i = 0; i < n; i++)
    A[i] =  s[i];

  A.sort();

  for(int i = 0; i < n; i++)
    s[i] =  A[i];

  cout << s << "\n";
}

Here we read the string by the string method read_line(). The array method sort() sorts the elements of an array according to their linear order. We will learn more about linear orders and how a type can be made a linearly ordered type in Section 2.8.3. The type char already has a linear order pre-defined by LEDA.

Unlike C++ arrays, LEDA arrays may have any arbitrary integral interval as index set. Therefore the indices do not have to start at 0, and in particular, negative indices may also occur. Figure 2.2 clarifies this.

Figure 2.2. A LEDA array with negative indices

The elements are not initialized at the definition. low() and high() return the smallest and the largest index of the array, respectively.

The smallest and the largest index have to be specified in the definition, like in

array<char> A(-5, 5);

Alternatively an array may be created by

array<char> A;

and its size may be defined by resize() not until a later point in time.

The class array has further useful methods, which we want to introduce here briefly.

The method

A.init(x);

sets all elements of an array to the value x.

	Important
	The elements are not set to a defined initial value, for example 0, in the moment of the definition of an array. This would perhaps be quite practical, but then arrays could not be created in constant time any more. (We will learn what “constant time” means in Section 2.2.3.)

The method

A.print();

outputs the complete array on standard output and thereby offers a comfortable way to create debugging output.

A call of

A.permute();

randomly permutes the elements of the array A.

Particularly interesting is the method

A.resize(new_low, new_high);

It redefines the size of an array; the new smallest and largest index have to be specified. “Old” elements are copied automatically into the new array and newly added elements are set to 0 or to the default value of the element type, respectively.

The methods

A.low();
A.high();

return the smallest and largest index of an array, respectively, and

A.size();

returns the number of elements of A. These methods are very useful primarily when the size and the outermost indices are not known any more as a result of a resize().

For high speed searches for elements the method

A.binary_search(x);

can be used. With the array containing n elements, it finds an element with value x in time O(log n). It is a precondition of the binary search that the array be sorted, see also Exercise 3. If the array is not in sorted order, it can be sorted before by means of sort(). The method binary_search() returns the index of the element to be searched for.

If there are several elements in the (sorted) array with a value of x, then they collocate in a partial sequence side by side. binary_search() then returns any index of this sequence. On the other hand, the method

A.binary_locate(x);

also executes a high-speed binary search; however, it returns the maximum index of a partial sequence of equal values.

	Warning
	In version 4.4 of LEDA (and in earlier versions) binary_locate() is faulty and should not be used.

Elements occurring multiply in A can be deleted by

A.unique();

Here it is also a precondition that the array be sorted. This method copies every value occurring in the array to the front once and returns the index of the last of these (now unique) values. Thus the original array will be destroyed because elements at the front are overwritten but not copied to rear. (Elements are lost!)

A small program tells more than a thousand words to an experienced programmer. Therefore we want to outline the use of these methods by a little example, completely senseless as a stand-alone program:

#include <LEDA/array.h>
#include <iostream>

using leda::array;
using std::cout;
using std::endl;

int main() 
{
  array<int> A(-5,5);

  A.init(0);
  A.print(); cout << endl;

  for(int i = A.low(); i <= A.high(); i++)
    A[i] = i;
  A.print(); cout << endl;

  A.permute();
  A.print(); cout << endl;
  
  A.sort();
  A.print(); cout << endl;

  A.resize(0,15);
  A.print(); cout << endl;

  cout << "A contains " << A.size() << " elements.\n";

  for(int i = A.low(); i <= A.high(); i++)
    A[i] /= 2;
  A.print(); cout << endl;
 
  A.sort();
  A.print(); cout << endl;

  int pos1 = A.binary_search(0);
  int pos2 = A.binary_locate(0);
  cout << "pos1 = " << pos1 << "   " << "pos2 = " << pos2 <<endl;

  int h = A.unique();
  cout << "The unique elements of A are: ";
  for(int i = A.low(); i <= h; i++) 
    cout << A[i] << " ";
  cout << endl;

  cout << "The rest of A is now: ";
  for(int i = h+1; i <= A.high(); i++) 
    cout << A[i] << " ";
  cout << endl;
}

The sensational output of the program is

  0 0 0 0 0 0 0 0 0 0 0
 -5 -4 -3 -2 -1 0 1 2 3 4 5
 4 5 2 -2 -5 1 -4 3 -1 0 -3
 -5 -4 -3 -2 -1 0 1 2 3 4 5
 0 1 2 3 4 5 0 0 0 0 0 0 0 0 0 0
A contains 16 elements.
 0 0 1 1 2 2 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2
pos1 = 7   pos2 = 7
The unique elements of A are: 0 1 2
The rest of A is now: 0 0 0 0 0 0 0 0 0 1 1 2 2

	Note
	print() always outputs a blank first. This is an error that is eliminated as of version 5.0 of LEDA.

One of the main advantages of LEDA arrays over ordinary C++ arrays is the possibility to adjust their size dynamically by resize(). Figure 2.3 clarifies what happens in the above program in the call of the method resize(): The index domain of the array changes from the interval [-5..5] to the interval [0..15]. The elements contained in the intersection of both index sets (that is the elements with indices 0 to 5) are adopted, the elements added newly are initialized to 0.

Figure 2.3. The method resize() of arrays

A beautiful application of resize() is found in the efficient computation of the binomial coefficients (n,k). This denotes the number of subsets with k elements each of a set with n elements. For example, there are (49,6) possibilities in the German national lottery to pull 6 balls out of a barrel with 49 balls altogether. These are a total of 13,983,816 possibilities. The probability to obtain six winning numbers in the German national lottery (if one fills out only one tip per bill) is therefore 1/13,983,816. In other words, one must play the national lottery for 13.938,816 / 52 = 268,054.15 years on the average to become rich. So it is better to learn LEDA properly and then make dough as a LEDA expert!

As it is well known, the binomial coefficients occur as the numbers in Pascal's triangle, see Figure 2.4: In this triangle, the k-th number in row n is exactly (n,k). An interesting observation is that in every row of the triangle the two outermost numbers are 1 and that the inner numbers are the sum of the two numbers standing above in the preceding line. Expressed in formulae:

Figure 2.4. Pascal's triangle

This observation leads us to the following program to calculate 10 lines of Pascal's triangle. We use a temporary array to calculate each new line from the previous one. In every iteration, the array becomes larger by 1 element by a call of resize(). A.low() and B.low() always stick to 0 here, of course; only the value of high() increases in every iteration.

#include <LEDA/array.h>
#include <iostream>

using leda::array;
using std::cout;

int main()
{
  array<int> A(0,1);
  A[0] = A[1] = 1;

  A.print();
  cout << "\n";

  array<int> B;

  for(int n = 0; n <= 10 ; n++) {

    B.resize(A.low(), A.high() + 1);

    B[0] = B[B.high()] = 1;
    for(int k = 1; k < B.high(); k++)
      B[k] = A[k-1] + A[k];

    B.print();
    cout << "\n";

    A = B;
  }
}

The output of the program is

 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 1 5 10 10 5 1
 1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
 1 8 28 56 70 56 28 8 1
 1 9 36 84 126 126 84 36 9 1
 1 10 45 120 210 252 210 120 45 10 1
 1 11 55 165 330 462 462 330 165 55 11 1
 1 12 66 220 495 792 924 792 495 220 66 12 1

The array B becomes larger by 1 element in every iteration here. It serves as a temporary array to calculate the respectively next line from the preceding line.

What exactly happens at the above assignment A = B? What could happen? Since we are experienced programmers, two possibilities immediately come to our mind: The elements could be copied from B to A componentwise (that is elementwise), or B and A could now point to the same object, that is the same memory location. How does LEDA proceed here? And what will happen when the arrays store more complex types than int? (We will see in Section 2.3.5 how to specify types of our own as parameters of containers.) Are these arrays copied bitwise or are merely references passed on? So what happens exactly? To settle these important questions, we must have a close look at the type and copy concept of LEDA.

Arrays of LEDA are part of the non-primitive types, also called structured types, see also Figure A.1. This means that they store collections of values; these collections have an inner structure. In contrast to this, primitive types like strings only store single values from a certain domain.^[9] In the case of arrays this inner structure is simply the linear sequence of the individual array elements. To be more precise, arrays are part of the non-item-based, structured types, also called simple-structured types. (We will learn what item-based structured types are in Section 2.3.2 where we will consider the type list as an example.)

We hope that the confusion is not too big here. Of course we will get to know examples of every sub-point of this categorization one after another. For the time being, however, we still have to learn a LEDA rule that tells us what really happens at an assignment A = B.

The rule of interest here is the rule “Copy of a value”. This rule consists of three partial rules that describe, depending on the category of the type of which a copy is made, how this copy is created. Here at first part b of the rule, which applies to simple-structured types, is important. (As just mentioned, arrays are a simple structured type.) This part b of the rule says that a copy of such a value, which represents a set or a sequence, is a componentwise copy of all individual values of this set or sequence, respectively.

The individual values of the array B are of type int, which as a built-in type is counted among the primitive types. Part a of the rule now says that a copy of such a primitive value is a bitwise copy of this value itself (written into a different memory location), like it is also provided by the language C++.

Applying both part a and part b of the rule to the assignment A = B, we see that the individual values are copied componentwise and bitwise here. So A and B do not point to the same physical memory location after the assignment.

Moreover, an array may also store pointer types like int* or other types like string. Such types are also counted among the primitive types according to the rule. Therefore a copy is made in this case, too.

Still the question remains what happens if a non-primitive type is stored in the array B. What happens during copying? The only non-primitive type that we already know is the type array. So if we copy an array of arrays, for example an array<array<int> >^[10], how does LEDA proceed then? In this case the rule has to be applied recursively: The complete structure is copied bitwise, nowhere references are passed on. If, however, we have an array in which values of an item-based, structured type, such as list, for example an array<list<int> >, are stored, we must in addition apply part c of the rule; we will come to this not until in Section 2.3.3.

The class array is implemented by C++ arrays.

Accessing an element takes constant time. The method sort() uses the Quicksort algorithm for sorting and takes time O(n·log(n)) with n elements to be sorted.

If n objects of type T are stored in an array, the space requirement is O(n·sizeof(T)).

More about arrays can be found on the corresponding manual page. We will learn more about the useful functions from LEDA/misc.h in Section 2.11.5.