Example: Bubble Sort

The following SAL program sorts an array of integers using a bubble sort. In Pascal, the bubble sort algorithm for N integers in an array A is:

{ read numbers to be sorted into the array }
        repeat
            Flag := true;
            for I := 1 to N - 1 do
                if (A[I] > A[I+1]) then
                    begin
                    Temp := A[I]; 
                    A[I] := A[I+1]; 
                    A[I+1] := Temp;
                    Flag := false;
                    end;
        until (Flag)

#
#	SAL code for bubble sort of integer array
#
	.data
n:	.word	0	# input number
a:	.space 200	# 50 element array
i:	.word		# array index
J:	.word		# array index
base:	.word	a	# base address of array
end:	.word		# address of last array element
flag:	.word   0	# completion flag
prompt:	.asciiz	"Enter integers to be sorted, one per line.  End with 0\n"
result:	.asciiz "Sorted list:\n"
nl:	.byte	'\n'

	.text
__start: puts	prompt 			# prompt for input
	la base, a			# initialize base, end
	move	end, base
getin:	get	n			# input numbers > 0
	blez	n, sort
	move	M[end], n		# store input in array
	add	end, end, 4		# increment ending address
	b 	getin

sort:	la	i, a			# bubble sort outer loop
	add	J, i, 4
	move	flag, 0			# clear swap flag
loop:	ble	M[i], M[J], noswap	# if elements i & J out of order, swap 
	move	n, M[i]
	move	M[i], M[J]
	move	M[J], n
	move	flag, 1			# set swap flag
noswap:	add	i, i, 4			# increment i
	add	J, J, 4			# increment J
	blt	J, end, loop		# test for end of array
	bgtz	flag, sort		# if a swap occurred, continue sort

	put	'\n'
	puts	result
	la 	i, a
print:	put	M[i]			# print sorted array
	put	'\n'
	add	i, i, 4
	blt	i, end, print
	done


dec1 18% spim
SPIM Version 4.4.2, Release:  April 22, 1993
Copyright 1990-92 by James R. Larus (larus@cs.wisc.edu)
Modified to read SAL code by Scott Kempf (scottk@cs.wisc.edu)
See the file COPYING for license information
(spim) load "bubble.s"
(spim) run
Enter integers to be sorted, one per line.  End with 0
1
9
2
8
3
7
4
6
5
0

Sorted list:
1
2
3
4
5
6
7
8
9

(spim) exit
dec1 19%