### Making an EM model for bubblesort

This presentation concerns a simple way of sorting data, viz. bubblesort.

By clicking on the interactive display on the left, can demonstrate bubblesort in action ...

In describing bubblesort informally, we refer to many things that have to be observed in order to understand the method.

The principle behind our approach is to make these observables explicit by embodying them in a form of computer model.

Terminology is difficult, not least because the 'model' is wide open to interaction and interpretation through which it is made and subsequently evolves.

What term is appropriate depends on the nature of the interaction. Possible terms are:

- artefact - a concrete source of experience whose interpretation may be obscure
- construal - an artefact that serves an explanatory purpose
- model - an artefact that corresponds closely to a specific referent

EM model can mean any of these things, and can apply to one and the same model when explored and interpreted in different ways.

Demonstrating bubblesort is just one way to exercise the EM bubblesort model.

### Observables ...

Our model is first and foremost to be experienced visually - plain as it is!

It reflects those aspects of the state that are significant in (bubble)sorting.

The 7 data items to be sorted are shown in an array - they have a L-to-R order.

This order exists independent of the data - it is built into a geometric structure.

The data itself consists of some numbers that have

- a value that is not explicitly visualised
- an associated representation - in this case by decimal digits

There are more sophisticated observables

- how one data item compares in the ordering with its neighbours
- which data item is the largest and the smallest

Another observable is whether or not the array is sorted.

In the process of bubblesorting, there are other observables, such as what pass is being executed in the sorting. At each pass, some items will have already been placed in order.

The 7 data items to be sorted are shown in an array - they have a L-to-R order. This order exists independent of the data - it is built into a geometric structure.

    %donald
    point S1, N1
    line V1
    V1 = [S1, N1]

execute | copy to input box

The data itself consists of some numbers that have ...

- a value that is not explicitly visualised

These are encoded in an array called `val`;

    %eden
    val = [7,56,19,90,21,3,46];

execute | copy to input box

- an associated representation - here by decimal digits

      _v1 is label(str(val1), _elt1);
      val1 is val[1];

  execute | copy to input box

There are more sophisticated observables

- how one data item compares in the ordering with its neighbours

    %donald
    k12 = label(sign12!, {0,-17}+(S1+N1) div 2)

    %eden
    sign12 is calc_sign(val1,val2);

    GREEN="blue"; WHITE="white";
    ordvis = 1;
    A_k12 is "color="
            // ((ordvis) ? GREEN : WHITE);

execute | copy to input box

- which data items are under consideration ...

  The first is data item 1, and the last is data item 7.

- ... and of these, which is the largest and the smallest.

  The largest is 90. The smallest is 3.

Why are these more sophisticated observables?

- how one data item compares in the ordering with its neighbours

... relies on your being able to make comparisons between values

- which data items are under consideration ...
- ... and of these, which is the largest and the smallest.

  ... also depends upon how you're executing the EM bubblesort model.

The most primitive observables have explicitly defined values. The values and visual counterparts of more complex observables are expressed by defining them in terms of more primitive observables. Definitions express dependencies (cf. spreadsheets).

A relevant criterion might be: what is given to you in your direct experience?

With basic numeracy, it's obvious how one data item compares with the next, and which are the largest and smallest elements.

The first and last data items under consideration can be read from the line ranging over the array. To interpret them, you need some notion about bubblesorting.

The idea that sophisticated observables may be 'given in experience' echoes William James's Radical Empiricism.

### Different modes of observation

There are many different varieties of observation depending on the knowledge and perception of the observer etc. For instance, we shall consider the manual versus automated perspectives.

All the observables discussed so far are relevant if I am manually sorting by whatever method. The model as demonstrated just includes some "automatic agents" to carry out the steps by way of observation and action that I can carry out manually. That's how the model was constructed.

There is an observable `autoset` to express the fact that the automatic agents are present ... its current value is 1.

When automated bubblesorting is in process, the way in which the observables first and last are redefined is strictly controlled - their values depend on which pass is currently being carried out. To change them directly would be to subvert the bubblesorting process.

The screen display can be adapted so that the background colour is determined by whether or not the automatic agents are present.

    %scout
    string autosignal;
    window arrwin = {
        type: DONALD
        box: [{0, 0}, {300, 100}]
        pict: "heaparr"
        xmax: 500
        ymax: 100
        border: 0
        bgcolor: autosignal
        sensitive:ON
    };
    %eden
    autosignal is (autoset) ? "beige" : "white" ;

execute | copy to input box

Another observable is whether or not the array is sorted.

    _fig1 is label(UnsS // "orted array of elements", cart(250, 15));
    UnsS is (sorted)?"S":"Uns";
    sorted is (val1<=val2) && (val2<=val3)
        && (val3<=val4) && (val4 <= val5)
           && (val5 <= val6) && (val6<=val7);

execute | copy to input box

or more precisely:

    sorted is (val1<=val2) && (val2<=val3)
        && (val3<=val4) && (val4 <= val5)
             && (val5 <= val6)&& (val6<=val7)
                  && (!autoset || (last==1));

execute | copy to input box

In the process of bubblesorting, there are other observables, such as what pass is being executed in the sorting. At each pass, some items will have already been placed in order.

    phase_status is (autoset) ?
    "The current phase in the bubblesort is " // str(bs_pass) :
         "There is no automated bubblesort in process";

execute | copy to input box

The current phase in the bubblesort is 1.

### Constructing a sorting method ...

The EM "bubblesort" model can be just as useful for other kinds of sorting ...

Here's an alternative way of sorting:

- put the model to manual mode (click+shift+cntrl)
- manually filter the smallest element to the "first" location
- manually filter the largest element to the "last" location
- increment first and decrement last.

      first++; last--;

  execute | copy to input box