Read numbers and print them in sorted order

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Numbers
Click For Summary

Discussion Overview

The discussion revolves around creating a RAM program to read a series of positive integers followed by an endmarker (0) and then print those integers in sorted order. Participants explore various sorting algorithms and the implementation details of the program, including how to handle input and manage registers.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant questions whether storing each positive number in a different register is correct and seeks clarification on the termination condition of the loop.
  • Another participant suggests that a bubble sort could be a suitable sorting method if efficiency is not a concern.
  • There is a discussion about the redundancy of certain LOAD and STORE operations in the program, with some participants agreeing on the need to simplify the code.
  • Several participants express confusion about how to compare the integers after reading them and propose various sorting approaches, including bubble sort and a simpler counting method using an array-like structure.
  • Concerns are raised about the proper implementation of conditions in the RAM program, particularly regarding the use of JZERO instructions and the potential for register conflicts.

Areas of Agreement / Disagreement

Participants express uncertainty about the best approach to sorting the integers and how to implement the program correctly. Multiple competing views on sorting methods and program structure remain unresolved.

Contextual Notes

Participants highlight limitations in their understanding of how to manage registers and implement arrays in RAM, as well as the implications of using certain instructions in their code. There are also unresolved questions about the termination condition of loops and the handling of input.

Who May Find This Useful

This discussion may be useful for individuals interested in programming concepts related to RAM architecture, sorting algorithms, and register management in low-level programming.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Give a RAM program to read $n$ positive integers followed by an endmarker ($0$) and then print the $n$ numbers in sorted order.

I have done the following:

Code: 
Read 1
LOAD 1
STORE 1

LOAD =2
STORE 2

while: JZERO endwhile
       READ *2
       LOAD *2
       STORE *2

       LOAD 2
       ADD =1
       STORE 2

endwhile: ...

So far I tried to store each positive number that is read in a different register. Is this correct?? (Wondering)

Then I have to order the numbers.

Do I have to store the integer of register 1 in the register n+1 and compare it with the integers of registers 2 till n?? If any of these numbers is greater that the number of register n+1, we store this number in register n+1.

Is my idea correct?? (Wondering)
 
Technology news on Phys.org
mathmari said:
Hey! :o

Give a RAM program to read $n$ positive integers followed by an endmarker ($0$) and then print the $n$ numbers in sorted order.

I have done the following:

Code: 
Read 1
LOAD 1
STORE 1

LOAD =2
STORE 2

while: JZERO endwhile
       READ *2
       LOAD *2
       STORE *2

       LOAD 2
       ADD =1
       STORE 2

endwhile: ...

So far I tried to store each positive number that is read in a different register. Is this correct?? (Wondering)

When will the loop terminate exactly? (Wondering)

Btw, aren't the LOAD 1 and STORE 1 after READ 1 redundant?
Then I have to order the numbers.

Do I have to store the integer of register 1 in the register n+1 and compare it with the integers of registers 2 till n?? If any of these numbers is greater that the number of register n+1, we store this number in register n+1.

Is my idea correct?? (Wondering)

I don't understand.
Can you explain more? (Wondering)
 
I like Serena said:
When will the loop terminate exactly? (Wondering)

When the input is $0$, or not?? But how could we write it in the program?? (Wondering)
I like Serena said:
Btw, aren't the LOAD 1 and STORE 1 after READ 1 redundant?

Yes, you're right! It should be:
Code: 
Read 1
LOAD 1

without [m]STORE 1[/m].
I like Serena said:
I don't understand.
Can you explain more? (Wondering)

Now, we have $n$ integers stored in $n$ registers.

To compare them, do we have to pick the integer of register $1$ and store it in register $n+1$, and then compare it with the integers of registers $2,\dots , n$ ?? Then if the integer of register $i$ is smaller/greater that the integer of register $n+1$, we store this integer in register $n+1$. Having compared this integer with the integers of all the registers, we conclude that the integer of register $n+1$ is the smallest/greatest integer and we print it. After that, we do the same for the second smallest/greatest, and so on.
 
mathmari said:
When the input is $0$, or not?? But how could we write it in the program?? (Wondering)

At the end of the while-loop, you have LOAD 2, ADD =1.
It's not likely that this will be 0 any time soon. (Worried)
Yes, you're right! It should be:
Code: 
Read 1
LOAD 1

without [m]STORE 1[/m].

What is the point of LOAD 1 if you do LOAD =2 immediately after? (Smirk)
Now, we have $n$ integers stored in $n$ registers.

To compare them, do we have to pick the integer of register $1$ and store it in register $n+1$, and then compare it with the integers of registers $2,\dots , n$ ?? Then if the integer of register $i$ is smaller/greater that the integer of register $n+1$, we store this integer in register $n+1$. Having compared this integer with the integers of all the registers, we conclude that the integer of register $n+1$ is the smallest/greatest integer and we print it. After that, we do the same for the second smallest/greatest, and so on.

Okay...
Suppose we have $2,3,1$, meaning $n=3$.
Then we have:
\begin{array}{|c|c|c|c|c|}
\hline
c(1) & c(2) & c(3) & c(n+1) \\
\hline
2 & 3 & 1 \\
& & & 2 \\
& & & 3 \\
& & & \text{WRITE 3} \\
\hline
\end{array}

And now? (Wondering)
 
I got stuck right now... (Wondering)

Code: 
n=0;
Read x;
while x > 0
     n=n+1;
     Read x;
if x < 0
   Write 0

Now the program has read n positive integers, followed by an endmarker (0), right??

I am confused how to compare these integers... (Wondering)
 
mathmari said:
I got stuck right now... (Wondering)

Code: 
n=0;
Read x;
while x > 0
     n=n+1;
     Read x;
if x < 0
   Write 0

Now the program has read n positive integers, followed by an endmarker (0), right??

I am confused how to compare these integers... (Wondering)

Well, the straight forward approach is to implement a sort algorithm, like bubble sort, or insertion sort.
You can pick this up from for instance wiki, and convert it to RAM code yourself. (Thinking)

Alternatively, you can try to implement something simpler.
For instance:
Code: 
max = 0
read x
while x > 0
  a[x] = a[x] + 1
  if x > max
    max = x
  read x
for x = 1 to max
  for n = 0 to a[x]
    write a[x]
(Wasntme)
 
I like Serena said:
Well, the straight forward approach is to implement a sort algorithm, like bubble sort, or insertion sort.
You can pick this up from for instance wiki, and convert it to RAM code yourself. (Thinking)

Alternatively, you can try to implement something simpler.
For instance:
Code: 
max = 0
read x
while x > 0
  a[x] = a[x] + 1
  if x > max
    max = x
  read x
for x = 1 to max
  for n = 0 to a[x]
    write a[x]
(Wasntme)

How do we use arrays in RAM?? (Wondering)

Is the equivalent program in RAM of the code above the following:

Code: 
LOAD =0
STORE 1

READ 2

while: LOAD 2
       JZERO endwhile

LOAD *2
ADD =1
STORE *2

if: LOAD 2
  SUB 1
  JZERO endif

LOAD 2
STORE 1

endif: READ 2

LOAD =1
STORE 2
while1: LOAD 2
        SUB 1
        JZERO endwhile1

LOAD =0
STORE 3
while2: LOAD 3
         SUB *2
         JZERO endwhile2

WRITE *2

JUMP while2

endwhile2: JUMP while1

JUMP while

endwhile: HALT

(Wondering)
 
mathmari said:
How do we use arrays in RAM?? (Wondering)

Is the equivalent program in RAM of the code above the following:

Code: 
LOAD =0
STORE 1

READ 2

while: LOAD 2
       JZERO endwhile

LOAD *2
ADD =1
STORE *2

if: LOAD 2
  SUB 1
  JZERO endif

LOAD 2
STORE 1

endif: READ 2

LOAD =1
STORE 2
while1: LOAD 2
        SUB 1
        JZERO endwhile1

LOAD =0
STORE 3
while2: LOAD 3
         SUB *2
         JZERO endwhile2

WRITE *2

JUMP while2

endwhile2: JUMP while1

JUMP while

endwhile: HALT

(Wondering)

Close.
I see you found a way to implement an array. (Smile)

Anyway, I'm afraid that the JZERO instructions are not proper implementations of the corresponding conditions.
This is particularly a problem with the if-statement that will now behave wrong. (Worried)

I see you have found a way to implement an array.
However, you are using the registers 1, 2, and 3 for other purposes, but they are now effectively also used in the array.
That will cause problems! (Doh)
 

Similar threads

MHB Program that accepts inputs of the form 1^n 2^{n^2} 0
  • · Replies 15 ·
Replies
15
Views
4K
MHB Converting Recursion into Loops for Computing n^n
  • · Replies 15 ·
Replies
15
Views
3K
Sequential Analog Computers?
  • · Replies 10 ·
Replies
10
Views
2K
Where is an ISR stored? Estimated time taken to address an interrupt
  • · Replies 6 ·
Replies
6
Views
4K
Finding the "Runner Up" (Second Highest Value)
  • · Replies 29 ·
Replies
29
Views
3K
Understanding of this pseudo-code
  • · Replies 8 ·
Replies
8
Views
2K
MHB Dynamic programming: which recurrence relation do we use?
  • · Replies 2 ·
Replies
2
Views
2K
MHB Computer system : Clarification needed
  • · Replies 32 ·
2
Replies
32
Views
2K
Python Python: printing every other input using a for loop
  • · Replies 2 ·
Replies
2
Views
3K
MHB Representation of signed integers of base B
  • · Replies 17 ·
Replies
17
Views
2K