Sorting algorithms/Bubble sort: Difference between revisions

=={{header|EDSAC order code}}==

This demo of a bubble sort on the EDSAC shows how awkward it was to deal with arrays

in the absence of an index register (one was added in 1953).

To refer to an array element at a given index, the programmer had to manufacture an

EDSAC order referring to the correct address, then plant that order in the code.

To clarify the EDSAC program, an equivalent Pascal program is added as a comment.

<lang edsac>

[Bubble sort demo for Rosetta Code website]

[EDSAC program. Initial Orders 2]

[Sorts a list of double-word integers.

List must be loaded at an even address.

First item gives number of items to follow.

Address of list is placed in location 49.

List can then be referred to with code letter L.]

T49K

P300F [<---------- address of list here]

[Subroutine R2, reads positive integers during input of orders.

Items separated by F; list ends with #TZ.]

GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z

[Tell R2 where to store integers it reads from tape.]

T #L ['T m D' in documentation, but this also works]

[Lists of integers, comment out all except one]

[10 integers from digits of pi]

10F314159F265358F979323F846264F338327F950288F419716F939937F510582F097494#TZ

[32 integers from digits of e ]

[32F

27182818F28459045F23536028F74713526F62497757F24709369F99595749F66967627F

72407663F03535475F94571382F17852516F64274274F66391932F00305992F18174135F

96629043F57290033F42952605F95630738F13232862F79434907F63233829F88075319F

52510190F11573834F18793070F21540891F49934884F16750924F47614606F68082264#TZ]

[Library subroutine P7, prints positive integer at 0D.

35 locations; load at aneven address.]

T 56 K

GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F

T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@

[The EDSAC code below implements the following Pascal program,

where the integers to be sorted are in a 1-based array x.

Since the assembler used (EdsacPC by Martin Campbell-Kelly)

doesn't allow square brackets inside comments, they are

replaced here by curly brackets.]

[

swapped := true;

j := n; // number of items

while (swapped and (j >= 2)) do begin

swapped := false;

for i := 1 to j - 1 do begin

// Using temp in the comparison makes the EDSAC code a bit simpler

temp := x{i};

if (x{i + 1} < temp) then begin

x{i} := x{i + 1};

x{i + 1} := temp;

swapped := true;

end;

end;

dec(j);

end;

]

[Main routine]

T 100 K

G K

[0] P F P F [double-word temporary store]

[2] P F [flag for swapped, >= 0 if true, < 0 if false]

[3] P F ['A' order for x{j}; implicitly defines j]

[4] P 2 F [to change list index by 1, i.e.change address by 2]

[5] A #L ['A' order for number of items]

[6] A 2#L ['A' order for x{1}]

[7] A 4#L ['A' order for x{2}]

[8] I2046 F [add to convert 'A' order to 'T' and dec address by 2]

[9] K4096 F [(1) minimum 17-bit value (2) teleprinter null]

[10] P D [constant 1, used in printing]

[11] # F [figure shift]

[12] & F [line feed]

[13] @ F [carriage return]

[Enter here with acc = 0]

[14] T 2 @ [swapped := true]

A L [get count, n in Pascal program above]

L 1 F [times 4 by shifting]

A 5 @ [make 'A' order for x{n}; initializes j := n]

[Start 'while' loop of Pascal program.

Here acc = 'A' order for x{j}]

[18] U 3 @ [update j]

S 7 @ [subtract 'A' order for x{2}]

G 56 @ [if j < 2 then done]

T F [acc := 0]

A 2 @ [test for swapped, acc >= 0 if so]

G 56 @ [if not swapped then done]

A 9 @ [change acc from >= 0 to < 0]

T 2 @ [swapped := false until swap occurs]

A 6 @ ['A' order for x{1}; initializes i := 1]

[Start 'for' loop of Pascal program.

Here acc = 'A' order for x{i}]

[27] U 36 @ [store order]

S 3 @ [subtract 'A' order for x{j}]

E 52 @ [out of 'for' loop if i >= j]

T F [clear acc]

A 36 @ [load 'A' order for x{i}]

A 4 @ [inc address by 2]

U 38 @ [plant 'A' order for x{i + 1}]

A 8 @ ['A' to 'T', and dec address by 2]

T 42 @ [plant 'T' order for x{i}]

[36] A #L [load x{i}; this order implicitly defines i]

T #@ [temp := x{i}]

[38] A #L [load x{i + 1}]

S #@ [acc := x{i + 1} - temp]

E 49 @ [don't swap if x{i + 1} >= temp]

[Here to swap x{i} and x{i + 1}]

A #@ [restore acc := x{i + 1} after test]

[42] T #L [x{i} := x{i + 1}]

A 42 @ [load 'T' order for x{i}]

A 4 @ [inc address by 2]

T 47 @ [plant 'T' order for x{i + 1}]

A #@ [load temp]

[47] T #L [to x{i + 1}]

T 2 @ [swapped := 0 (true)]

[49] T F [clear acc]

A 38 @ [load 'A' order for x{i + 1}]

G 27 @ [loop (unconditional) to inc i]

[52] T F

A 3 @ [load 'A' order for x{j}]

S 4 @ [dec address by 2]

G 18 @ [loop (unconditional) to dec j]

[Print the sorted list of integers]

[56] O 11 @ [figure shift]

T F [clear acc]

A 5 @ [load 'A' order for head of list]

T 65 @ [plant in code below]

S L [load negative number of items]

[61] T @ [use first word of temp store for count]

A 65 @ [load 'A' order for item]

A 4 @ [inc address by 2]

T 65 @ [store back]

[65] A #L [load next item in list]

T D [to 0D for printing]

[67] A 67 @ [for subroutine return]

G 56 F [print integer, clears acc]

O 13 @ [print CR]

O 12 @ [print LF]

A @ [negative count]

A 10 @ [add 1]

G 61 @ [loop back till count = 0]

[74] O 9 @ [null to flush teleprinter buffer]

Z F [stop]

E 14 Z [define entry point]

P F [acc = 0 on entry]

</lang>

{{out}}

<pre>

97494

265358

314159

338327

419716

510582

846264

939937

950288

979323

</pre>