输入数量可变的冒泡排序
Bubble sort with variable number of inputs
我正在为 Little Man Computer 开发一个冒泡排序程序，我希望它有可变数量的输入（比如 500），之后程序将停止接受输入并将值从最小到排序最伟大的。
请注意，冒泡排序中应接受零作为数字。因此，如果输入是 3、5、6、0，那么它应该将它们排序为 0、3、5、6。
想法是为其余输入的 length 保留第一个输入。这样您就可以知道何时所有值都已被采用。所以在你的例子中：
3 5 6 0
实际输入值必须是
4 3 5 6 0
...其中 4 告诉我们后面有 4 个数据值。
所以这意味着该程序将以如下内容开始：
INP
BRZ quit ; nothing to do
STA size
; .... other code ....
quit HLT
size DAT
然后代码需要使用这个size来初始化一个计数器，并获取剩余的输入
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
当你有多个——可能是嵌套的——循环时，就像冒泡排序的情况一样，你将不得不管理多个计数器。
应用于冒泡排序
在 中，您会找到冒泡排序的实现，其中输入需要以 0 结束。在这里，我为您提供该解决方案的变体，其中 0 不再用作输入终止符，但是第一个输入表示输入中后面的值数组的长度。
请注意，这会使代码稍长一些，因此保留用于存储输入数组的 space 变得更小：这里只有 25 个邮箱可用于数组。在标准的 LMC 上，永远不可能存储 500 个输入，因为总共只有 100 个邮箱，而代码占用了其中一些邮箱。
算法中（加载完输入后），外循环需要迭代size-1次，内循环每次少迭代一次外层循环进行一次迭代（这是冒泡排序的标准原理）。
#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>
This is the final code and some basic information.
// Basic Outline
// 1) Initialize (may be empty)
// 2) Input Count
// 3) Handle Special Cases, GoTo 1 (will now be no special cases)
// 4) Input List
// 5) Sort the list (using Bubblesort)
// 6) Output List
// 7) GoTo 1
//
// Program uses an LMCe, same as an LMC except that it has an extra digit.
//The number of memory cells is thus 1000 and the range of values is from 0 to 9999.
//
// Memory Map
//
// 0 – 79 the program
// 80-87 unused (may be used to test sorting in LMCs)
// 88-99 constants and variables
// 100 – 999 the list to be sorted.
//
// INITIALIZE (This section is blank)
//
// INPUT COUNT
//
000 IN 9001 // input count
001 STO 090 3090 // store count
//
// SPECIAL CASES (This section is now blank)
//
// INPUT LIST
//
002 LDA 096 5096 // STO
003 ADD 095 1095 // Determine first location
004 STO 011 3011 // Overwrite STO instruction for list
005 ADD 090 1090
006 STO 092 3092 // Store STO + LOC + Count to determine end
//
// INPUT LIST LOOP
007 LDA 011 5013 // Load manipulated instruction (using as counter)
008 SUB 092 2092 //
009 BRZ 016 7016 // If last count, go to END INPUT LIST
010 IN 9001 //
011 DAT 0 // manipulated instruction (store input in list)
012 LDA 011 5011
013 ADD 098 1098 // increment store instruction (to next list location)
014 STO 011 3011 // Update STO instruction
015 BR 007 6007 // GOTO INPUT LIST LOOP
//
// END INPUT LIST
//
// BUBBLESORT
// Note: the ‘to’ is inclusive.
//
// for I = 0 to count – 1 do (may not be inclusive)
// for j = count – 1 downto I + 1 do (may be inclusive)
// if A[j] < A[j-1]
// then exchange A[j] and A[j-1]
// end do
// end do
//
// If count < 2, then skip bubble sort
016 LDA 098 5098
017 SUB 090 2090 // 1 – count
018 BRP 061 8061 //. GO TO END I LOOP
//
// Initialize ‘I’ Counter
019 LDA 099 5099
020 STO 092 3092 // set I to zero (0)
//
// START I LOOP
//
021 LDA 090 5090
022 SUB 098 2098 // COUNT - 1
023 SUB 092 1092 // COUNT -1 – I
024 BRZ 061 7061 // if(I == count - 1) GOTO END I LOOP
//
// Initialize J
025 LDA 090 5090
026 SUB 098 2098
027 STO 093 3093 // J = Count – 1
//
// START J LOOP
//
028 LDA 092 5092 // I
029 SUB 093 2093 // I - J
030 BRP 057 8057 // If I == j, then GO END J LOOP
//
// Compare A[j] and A[j-1]
//
// Load A[j] into variable
031 LDA 097 5097 // load LDA instruction numeric code
032 ADD 095 1095 // set to LDA 500
033 ADD 093 1093 // set to LDA [500 + j] or A[j]
034 STO 039 3039 // reset instruction
035 SUB 098 2098 // set to LDA [500 + j – 1] or A[j-1]
036 STO 037 3037 // reset instruction
//
// Load and compare A[j] and A[j-1]
037 DAT 0 // load A[j-1] (instruction is manipulated)
038 STO 088 3088
039 DAT 0 // load A[j] (instruction is manipulated)
040 STO 089 3089
041 SUB 088 2088 // A[j] – A[j-1] (swap if not positive)
042 BRP 053 8053 // GOTO DECREMENT J
//
// swap the variables
//
// set up the STO variables
043 LDA 096 5096 // load STO instruction code
044 ADD 095 1095 // set to STO 500
045 ADD 093 1093 // set to STO [500 + j]
046 STO 052 3052 // reset instruction
047 SUB 098 2098 // set to STO [500 + j – 1]
048 STO 050 3050 // reset instruction
//
// do the swap (no need for a variable since they are already stored)
049 LDA 089 5089 // load A[j]
050 DAT 0 // Store in A[j-1] (instruction is manipulated)
051 LDA 088 5088 // load A[j-1]
052 DAT 0 // Store in A[j] (instruction is manipulated)
//
// DECREMENT J
//
053 LDA 093 5093
054 SUB 098 2098
055 STO 093 3093 // J = J – 1
056 BR 028 6028 // GOTO START J LOOP
//
// END J LOOP
//
// Increment I
057 LDA 092 5092
058 ADD 098 1098
059 STO 092 3092 // I = I + 1
060 BR 021 6021 // GOTO START I LOOP
//
// END I LOOP (End Bubblesort)
//
// OUTPUT COUNT
//
061 LDA 090 5090 // Count
062 OUT 9002
//
// OUTPUT LIST (now sorted)
// Initialize
063 LDA 097 5097
064 ADD 095 1095 // LDA + LOC
065 STO 071 3071 // set up instruction
066 ADD 090 1090 // LDA + LOC + Count
067 STO 092 3092 // store unreachable instruction
//
// OUTPUT LIST LOOP
068 LDA 071 5071 // load manipulated instruction (used as counter)
069 SUB 092 2092
070 BRZ 077 7077 // GOTO END OUTPUT LOOP
071 DAT 0 // manipulated output
072 OUT 9002
073 LDA 071 5071
074 ADD 098 1098
075 STO 071 3071 // increment manipulated instruction
076 BR 068 6028 // GOTO OUTPUT LIST LOOP
//
// END OUTPUT LOOP
077 BR 0 6000 // Branch to top of loop (embedded)
//
// End of program
078 HLT 0 // (Should never hit this instruction)
//
// Variables
088 DAT 0 // A[j-1] value (also used for swapping)
089 DAT 0 // A[j] value (also used for swapping)
//
090 DAT 0 // count variable (input and output)
091 DAT 0 // unused
092 DAT 0 // ‘I’ counter
093 DAT 0 // ‘j’ counter
//
// Constants
094 DAT 0 // unused
095 DAT 500 // initial list location
096 DAT 3000 // STO instruction
097 DAT 5000 // LDA instruction
098 DAT 1 // one (constant)
099 DAT 0 // zero (constant)
我正在为 Little Man Computer 开发一个冒泡排序程序，我希望它有可变数量的输入（比如 500），之后程序将停止接受输入并将值从最小到排序最伟大的。
请注意，冒泡排序中应接受零作为数字。因此，如果输入是 3、5、6、0，那么它应该将它们排序为 0、3、5、6。
想法是为其余输入的 length 保留第一个输入。这样您就可以知道何时所有值都已被采用。所以在你的例子中：
3 5 6 0
实际输入值必须是
4 3 5 6 0
...其中 4 告诉我们后面有 4 个数据值。
所以这意味着该程序将以如下内容开始：
INP
BRZ quit ; nothing to do
STA size
; .... other code ....
quit HLT
size DAT
然后代码需要使用这个size来初始化一个计数器，并获取剩余的输入
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
当你有多个——可能是嵌套的——循环时，就像冒泡排序的情况一样，你将不得不管理多个计数器。
应用于冒泡排序
在
请注意，这会使代码稍长一些，因此保留用于存储输入数组的 space 变得更小：这里只有 25 个邮箱可用于数组。在标准的 LMC 上，永远不可能存储 500 个输入，因为总共只有 100 个邮箱，而代码占用了其中一些邮箱。
算法中（加载完输入后），外循环需要迭代size-1次，内循环每次少迭代一次外层循环进行一次迭代（这是冒泡排序的标准原理）。
#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>
This is the final code and some basic information.
// Basic Outline
// 1) Initialize (may be empty)
// 2) Input Count
// 3) Handle Special Cases, GoTo 1 (will now be no special cases)
// 4) Input List
// 5) Sort the list (using Bubblesort)
// 6) Output List
// 7) GoTo 1
//
// Program uses an LMCe, same as an LMC except that it has an extra digit.
//The number of memory cells is thus 1000 and the range of values is from 0 to 9999.
//
// Memory Map
//
// 0 – 79 the program
// 80-87 unused (may be used to test sorting in LMCs)
// 88-99 constants and variables
// 100 – 999 the list to be sorted.
//
// INITIALIZE (This section is blank)
//
// INPUT COUNT
//
000 IN 9001 // input count
001 STO 090 3090 // store count
//
// SPECIAL CASES (This section is now blank)
//
// INPUT LIST
//
002 LDA 096 5096 // STO
003 ADD 095 1095 // Determine first location
004 STO 011 3011 // Overwrite STO instruction for list
005 ADD 090 1090
006 STO 092 3092 // Store STO + LOC + Count to determine end
//
// INPUT LIST LOOP
007 LDA 011 5013 // Load manipulated instruction (using as counter)
008 SUB 092 2092 //
009 BRZ 016 7016 // If last count, go to END INPUT LIST
010 IN 9001 //
011 DAT 0 // manipulated instruction (store input in list)
012 LDA 011 5011
013 ADD 098 1098 // increment store instruction (to next list location)
014 STO 011 3011 // Update STO instruction
015 BR 007 6007 // GOTO INPUT LIST LOOP
//
// END INPUT LIST
//
// BUBBLESORT
// Note: the ‘to’ is inclusive.
//
// for I = 0 to count – 1 do (may not be inclusive)
// for j = count – 1 downto I + 1 do (may be inclusive)
// if A[j] < A[j-1]
// then exchange A[j] and A[j-1]
// end do
// end do
//
// If count < 2, then skip bubble sort
016 LDA 098 5098
017 SUB 090 2090 // 1 – count
018 BRP 061 8061 //. GO TO END I LOOP
//
// Initialize ‘I’ Counter
019 LDA 099 5099
020 STO 092 3092 // set I to zero (0)
//
// START I LOOP
//
021 LDA 090 5090
022 SUB 098 2098 // COUNT - 1
023 SUB 092 1092 // COUNT -1 – I
024 BRZ 061 7061 // if(I == count - 1) GOTO END I LOOP
//
// Initialize J
025 LDA 090 5090
026 SUB 098 2098
027 STO 093 3093 // J = Count – 1
//
// START J LOOP
//
028 LDA 092 5092 // I
029 SUB 093 2093 // I - J
030 BRP 057 8057 // If I == j, then GO END J LOOP
//
// Compare A[j] and A[j-1]
//
// Load A[j] into variable
031 LDA 097 5097 // load LDA instruction numeric code
032 ADD 095 1095 // set to LDA 500
033 ADD 093 1093 // set to LDA [500 + j] or A[j]
034 STO 039 3039 // reset instruction
035 SUB 098 2098 // set to LDA [500 + j – 1] or A[j-1]
036 STO 037 3037 // reset instruction
//
// Load and compare A[j] and A[j-1]
037 DAT 0 // load A[j-1] (instruction is manipulated)
038 STO 088 3088
039 DAT 0 // load A[j] (instruction is manipulated)
040 STO 089 3089
041 SUB 088 2088 // A[j] – A[j-1] (swap if not positive)
042 BRP 053 8053 // GOTO DECREMENT J
//
// swap the variables
//
// set up the STO variables
043 LDA 096 5096 // load STO instruction code
044 ADD 095 1095 // set to STO 500
045 ADD 093 1093 // set to STO [500 + j]
046 STO 052 3052 // reset instruction
047 SUB 098 2098 // set to STO [500 + j – 1]
048 STO 050 3050 // reset instruction
//
// do the swap (no need for a variable since they are already stored)
049 LDA 089 5089 // load A[j]
050 DAT 0 // Store in A[j-1] (instruction is manipulated)
051 LDA 088 5088 // load A[j-1]
052 DAT 0 // Store in A[j] (instruction is manipulated)
//
// DECREMENT J
//
053 LDA 093 5093
054 SUB 098 2098
055 STO 093 3093 // J = J – 1
056 BR 028 6028 // GOTO START J LOOP
//
// END J LOOP
//
// Increment I
057 LDA 092 5092
058 ADD 098 1098
059 STO 092 3092 // I = I + 1
060 BR 021 6021 // GOTO START I LOOP
//
// END I LOOP (End Bubblesort)
//
// OUTPUT COUNT
//
061 LDA 090 5090 // Count
062 OUT 9002
//
// OUTPUT LIST (now sorted)
// Initialize
063 LDA 097 5097
064 ADD 095 1095 // LDA + LOC
065 STO 071 3071 // set up instruction
066 ADD 090 1090 // LDA + LOC + Count
067 STO 092 3092 // store unreachable instruction
//
// OUTPUT LIST LOOP
068 LDA 071 5071 // load manipulated instruction (used as counter)
069 SUB 092 2092
070 BRZ 077 7077 // GOTO END OUTPUT LOOP
071 DAT 0 // manipulated output
072 OUT 9002
073 LDA 071 5071
074 ADD 098 1098
075 STO 071 3071 // increment manipulated instruction
076 BR 068 6028 // GOTO OUTPUT LIST LOOP
//
// END OUTPUT LOOP
077 BR 0 6000 // Branch to top of loop (embedded)
//
// End of program
078 HLT 0 // (Should never hit this instruction)
//
// Variables
088 DAT 0 // A[j-1] value (also used for swapping)
089 DAT 0 // A[j] value (also used for swapping)
//
090 DAT 0 // count variable (input and output)
091 DAT 0 // unused
092 DAT 0 // ‘I’ counter
093 DAT 0 // ‘j’ counter
//
// Constants
094 DAT 0 // unused
095 DAT 500 // initial list location
096 DAT 3000 // STO instruction
097 DAT 5000 // LDA instruction
098 DAT 1 // one (constant)
099 DAT 0 // zero (constant)