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
SUMMARY

The discussion focuses on implementing a RAM program to read and sort positive integers followed by an endmarker (0). Participants suggest using bubble sort or insertion sort algorithms for sorting the integers stored in registers. Key points include the need to compare integers stored in different registers and the importance of correctly managing the loop termination condition. The conversation highlights potential issues with redundancy in code and the proper implementation of array-like structures in RAM programming.

PREREQUISITES
  • Understanding of RAM programming concepts
  • Familiarity with sorting algorithms such as bubble sort and insertion sort
  • Knowledge of register-based data storage and manipulation
  • Ability to implement loop and conditional structures in RAM code
NEXT STEPS
  • Study the implementation of bubble sort in RAM programming
  • Learn about conditional statements and loop structures in RAM
  • Research how to effectively use registers for array-like behavior in RAM
  • Explore optimization techniques for sorting algorithms in low-level programming
USEFUL FOR

Programmers and computer science students interested in low-level programming, specifically those working with RAM architecture and sorting algorithms.

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
1K
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