Read numbers and print them in sorted order

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Numbers
In summary, the program reads an integer x and stores it in register n+1, increments n by 1, and reads x again. If x is less than 0, it writes 0.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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
  • #3
mathmari said:
Hey! :eek:

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)
 
  • #4
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.
 
  • #5
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)
 
  • #6
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)
 
  • #7
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)
 
  • #8
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)
 
  • #9
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)
 

FAQ: Read numbers and print them in sorted order

What is the purpose of reading and printing numbers in sorted order?

The purpose of reading and printing numbers in sorted order is to organize and display a list of numbers in ascending or descending order, making it easier for the user to interpret and analyze the data. This can be useful in various scientific and mathematical applications.

How can I read and print numbers in sorted order in a computer program?

To read and print numbers in sorted order in a computer program, you can use a sorting algorithm such as bubble sort, selection sort, or merge sort. These algorithms compare the numbers and rearrange them in the desired order. Alternatively, many programming languages have built-in functions or methods for sorting data.

Is it possible to print numbers in sorted order without using a computer program?

Yes, it is possible to print numbers in sorted order without a computer program. You can sort the numbers manually by arranging them in the desired order using pen and paper. However, this can be time-consuming and prone to human error, especially for large sets of numbers.

What is the most efficient way to read and print a large set of numbers in sorted order?

The most efficient way to read and print a large set of numbers in sorted order is to use a computer program with a fast and optimized sorting algorithm. This can significantly reduce the time and effort required to sort the numbers compared to manual sorting.

Can I customize the sorting order when printing numbers?

Yes, you can customize the sorting order when printing numbers by specifying the sorting criteria in your computer program. For example, you can sort the numbers in descending order instead of ascending order, or you can sort them based on a specific attribute such as their absolute values.

Similar threads

MHB Program that accepts inputs of the form 1^n 2^{n^2} 0
Replies
15
Views
3K
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
3K
Finding the "Runner Up" (Second Highest Value)
Replies
29
Views
2K
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
Python Python: printing every other input using a for loop
Replies
2
Views
2K
Engineering Issue with shift registers — PIPO, PISO, SIPO and SISO
Replies
10
Views
2K
MHB Representation of signed integers of base B
Replies
17
Views
1K

Hot Threads

Recent Insights

Back
Top