MHB Read numbers and print them in sorted order

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Numbers
AI Thread Summary
The discussion revolves around creating a RAM program to read a series of positive integers followed by an end marker (0) and then sorting those integers. Participants are trying to clarify the logic of their code, particularly regarding how to store and sort the integers. Initial attempts involve reading integers into separate registers, but there are concerns about redundancy and the termination condition of the input loop. The conversation highlights the need for a sorting algorithm, with suggestions for using bubble sort or insertion sort. Participants also discuss how to implement comparisons between the integers stored in registers and how to handle the end marker. There are questions about using arrays in RAM and concerns about the proper implementation of conditions using JZERO instructions. Overall, the thread emphasizes understanding the flow of data input, storage, and sorting in RAM, while addressing potential pitfalls in the program's logic and structure.
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
Views
4K
MHB Converting Recursion into Loops for Computing n^n
Replies
15
Views
3K
Where is an ISR stored? Estimated time taken to address an interrupt
Replies
6
Views
4K
Finding the "Runner Up" (Second Highest Value)
Replies
29
Views
3K
Understanding of this pseudo-code
Replies
8
Views
2K
MHB Dynamic programming: which recurrence relation do we use?
Replies
2
Views
1K
MHB Computer system : Clarification needed
Replies
32
Views
2K
MHB How to Sort Elements of a Matrix in O(n) Time Complexity?
Replies
1
Views
2K
MHB Representation of signed integers of base B
Replies
17
Views
1K
Engineering Issue with shift registers — PIPO, PISO, SIPO and SISO
Replies
10
Views
3K

Hot Threads

Recent Insights

Back
Top