输入数量可变的冒泡排序 [英] Bubble sort with variable number of inputs
问题描述
我正在为Little Man Computer开发一个冒泡排序程序，我希望它具有可变数量的输入(例如500)，此后该程序将停止接收输入并将值从最小到最大排序.
I am working on a bubble sort program for the Little Man Computer and I want it to have a variable number of inputs (like 500), after which the program will stop taking inputs and will sort the values from least to greatest.
请注意，冒泡排序中的数字应为零.因此，如果输入为3、5、6、0，则应将其排序为0、3、5、6.
Note that zero should be accepted as a number in the bubble sort. So if the inputs are 3, 5, 6, 0 then it should sort them to 0, 3, 5, 6.
推荐答案
该想法是为其余输入的 length 保留第一个输入.这样，您就可以知道何时获取所有值.因此，在您的示例中:
The idea is to reserve the very first input for the length of the rest of the input. This way you can know when all the values have been taken. So in your example:
3 5 6 0
实际输入值必须为
4 3 5 6 0
...其中4告诉我们紧随其后的是4个数据值.
...where 4 tells us that 4 data values are following.
因此，这意味着程序将以类似以下内容的开头:
So this means that the program would start with something like:
INP
BRZ quit ; nothing to do
STA size
; .... other code ....
quit HLT
size DAT
然后，代码将需要使用此 size 来初始化计数器，并获取其余输入
Then the code would need to use this size to initialise a counter, and take the remaining inputs
LDA size
SUB one
loop STA counter
INP ; take the next input
; .... process this value ....
LDA counter ; decrement the counter
SUB one
BRP loop ; while no underflow: repeat
; ... other processing on the collected input ...
quit HLT
counter DAT
当您有多个(可能是嵌套的)循环时(如冒泡排序那样)，您将不得不管理多个计数器.
When you have several -- possibly nested -- loops, like is the case with bubble sort, you'll have to manage multiple counters.
在此答案中，您将找到冒泡排序的实现，其中输入必须以0终止.在这里，我为您提供了该解决方案的一种变体，其中0不再用作输入终止符，但第一个输入表示输入中跟随的值数组的长度.
In this answer you'll find an implementation of Bubble Sort where the input needs to be terminated by a 0. Here I provide you a variation of that solution where 0 no longer serves as an input terminator, but where the first input denotes the length of the array of values that follows in the input.
请注意，这会使代码更长一些，因此，用于存储输入数组的剩余空间会变小:此处仅25个邮箱可用于该数组.在标准的LMC上，将永远无法存储500个输入，因为总共只有100个邮箱，并且其中的一些代码占用了这些邮箱.
Note that this makes the code somewhat longer, and as a consequence the space that remains for storing the input array becomes smaller: here only 25 mailboxes remain available for the array. On a standard LMC it would never be possible to store 500 inputs, as there are only 100 mailboxes in total, and code occupies some of these mailboxes.
在算法中(加载输入后)，外循环需要迭代 size -1次，并且内循环每次迭代都需要少迭代一次.(这是气泡排序的标准原理).
In the algorithm (after having loaded the input), the outer loop needs to iterate size-1 times, and the inner loop needs to iterate one time less each time the outer loop makes an iteration (this is the standard principle of Bubble Sort).
#input: 10 4 3 2 1 0 9 8 5 6 7
LDA setfirst
STA setcurr1
INP
BRZ zero ; nothing to do
SUB one
STA size ; actually one less
input STA counter1
INP
setcurr1 STA array
LDA setcurr1
ADD one
STA setcurr1
LDA counter1
SUB one
BRP input
LDA size
BRA dec
sort STA counter1
LDA getfirst
STA getcurr1
STA getcurr2
LDA setfirst
STA setcurr2
LDA cmpfirst
STA cmpcurr
LDA counter1
loop STA counter2
LDA getcurr1
ADD one
STA getnext1
STA getnext2
LDA setcurr2
ADD one
STA setnext
getnext1 LDA array
cmpcurr SUB array
BRP inc
getcurr1 LDA array
STA temp
getnext2 LDA array
setcurr2 STA array
LDA temp
setnext STA array
inc LDA getnext1
STA getcurr1
LDA setnext
STA setcurr2
LDA cmpcurr
ADD one
STA cmpcurr
LDA counter2
SUB one
BRP loop
LDA counter1
dec SUB one
BRP sort
LDA size
output STA counter1
getcurr2 LDA array
OUT
LDA getcurr2
ADD one
STA getcurr2
LDA counter1
SUB one
BRP output
zero HLT
one DAT 1
getfirst LDA array
setfirst STA array
cmpfirst SUB array
size DAT
counter1 DAT
counter2 DAT
temp DAT
array DAT
<script src="https://cdn.jsdelivr.net/gh/trincot/lmc@v0.77/lmc.js"></script>这篇关于输入数量可变的冒泡排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
