Bubble sort in assembly

[ResidentBiscuit]

Ok so I'm needing to implement a bubble sort in the marie assembler language, which some of you seem to be familiar with somehow. I can't seem to even get started with this, but it's got me frustrated. I finally got the array up and working, and now I can't seem to think about how to sort it.

Here's what I got for the populating an array of n size. Works just fine.

Org 100
Loc, Load Arr
Load Loc
Subt H1000
Store ArrL   //Start of Arr
Store XAddr
Load Size    //Array Size
Loop, Store N
Input
Output
StoreI ArrL
Load ArrL
Add c1
Store ArrL
Load N
Subt c1
Skipcond 400
Jump Loop
Load XAddr
Store ArrL
Halt
Size, Dec 3
c1, Dec 1
H1000, Hex 1000
ArrL, Dec 0
XAddr, Dec 0
N, Dec 0
Arr, Dec 0
     Dec 0
     Dec 0

Here's what I'm looking at implementing:

int i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<i;j++)
        {
            if(array[i]>array[j])
            {
                int temp=array[i]; //swap 
                array[i]=array[j];
                array[j]=temp;
            }

        }

    }

But, I have no clue how to get started on this

[4z0M4iN6]

That's an unusually implemented list sort, but not a bubble sort.
Consider this as a bubble sort:

int i;
int j;

int mintemp;
int swapped;

for( j = 0; j < (ArraySize - 1); ++j)
{
	
	swapped = false;

	for( i = j; i < (ArraySize - 1); ++i)
	{
		mintemp = array[i];

		if(array[i+1] < mintemp)
		{
			array[i] = array[i+1];
			array[i+1] = mintemp;
			swapped = true;
		}
	}

	if(!swapped) break; // that's the advantage
}

But the bubble sort normally has one optimation more. See http://en.wikipedia.org/wiki/Bubble_sort

[naraku9333]

@dadabe
Looks like a bubble sort to me, Im not familiar with a list sort.

@ResidentBiscuit
The inner for doesn't look right, maybe should be
for(j=i; j<10;++j)? I cant add anything concerning the swap in the pseudo assembly, Ill take a look later if I get the time.

[4z0M4iN6]

naraku9333 wrote:

I will explain, what a list sort is.

List sort: you search an array and look for the lowest (or highest) value and set this vaue at the begin (or end) of your current part of the array.

This would be a list sort:

#include <define.h>

int i;
int j;
int lowest;
int minimum;

for( j = 0; j < (ArraySize - 1); ++j)
{
	minimum = INT_MAX;

	for( i = j; i < ArraySize; ++i)
	{
               if(array[i] < minimum)
               {                              
                    minimum = array[i];
                    position = i;
               }
        }
        array[position] = array[j];
        array[j] = minimum;
} 

ResidentBiscuit used (in this case - I always use i for the inner loop) array[j] (he array[i]) as minimum and swapped the content with array[i] (he array[j]) each time, when the condion was fullfilled. The line "array[j] = minimum" was in this case not neccessary.

[ResidentBiscuit]

I have never heard of a list sort, either. And neither has the internet in general after doing a quick search. I actually just got rid of that whole inner loop and used a flag to see check if it was all sorted. Still haven't worked out how to translate it into assembly. I have no issue with the C++ code

[4z0M4iN6]

Sorry about my code for a bubble sort. I didn't think it over. I only wrote, what I remembered. But I remembered wrong.

What's wrong?


If I increase j, I must make shure, that the smallest element bubbles down. So I have to decrease i.

Correct is:

int i;
int j;

int temp;
int swapped;

for( j = 0; j < (ArraySize - 1); ++j)
{
	
	swapped = false;

	for( i = ArraySize; i > j ; --i)
	{
		temp = array[i];

		if(array[i-1] > temp)
		{
			array[i] = array[i-1];
			array[i-1] = temp;
			swapped = true;
		}
	}

	if(!swapped) break; // that's the advantage
}

Seems to look well now

[naraku9333]

@ResidentBiscuit
What version of MARIE do you have, I dont seem to have StoreI available. I have version 1.3.01

[ResidentBiscuit]

Ah yea StoreI is useful. Lemme see if I can get a link for you, if not I'll send you the jar if you mind sending your email in a PM

[ResidentBiscuit]

Did you download from here?

http://computerscience.jbpub.com/ecoa/3e/simulators.aspx

[4z0M4iN6]

ResidentBiscuit wrote:

I have never heard of a list sort, either. And neither has the internet in general after doing a quick search. I actually just got rid of that whole inner loop and used a flag to see check if it was all sorted. Still haven't worked out how to translate it into assembly. I have no issue with the C++ code

What I wrote, wasn't about C++ code. Sorry, that I formulated it in C code, but I didn't have time to draw some nice pictures. And I think you understand C.

And what you wrote about a quick search in internet is also not very relevant. What you need, is, to have an idea, how a list sort or a bubble sort works. What is needed, is, you have to think about it.

And if you have thought about it and have understood the principle, then you can code it.

Why did I write, it's important to think? Yes you could have looked up such wellknown examples somewhere. But don't forget, later you have to implement many things, you can't read somewhere and the solution is, to think about it, and this you should understand. And if you have thought yourself about many things, than it's your own knowledge, which you will never forget. And if you have trained your thinking, you can solve many problems, which others can not, who have knowledge mostly only from books.

And about thinking. Don't think too much. It's better you don't have much in your mind, when you begin. Best, your mind should be empty, and you should concentrate only on a small part of the problem, but this part make as best and as simple as you can.

You could begin:

How to implement the outer loop.

[1vRz3TCk]

dadabe wrote:

That's an unusually implemented list sort, but not a bubble sort.
Consider this as a bubble sort: ...

The code that ResidentBiscuit originally posted looks like a basic bubble sort to me. The code that you posted looks like modified bubble sort (AKA bubble sort).

dadabe wrote:

List sort: you search an array and look for the lowest (or highest) value and set this vaue at the begin (or end) of your current part of the array.

Sounds like Selection sort to me.

[4z0M4iN6]

CodeMonkey wrote:

The code that ResidentBiscuit originally posted looks like a basic bubble sort to me.

Yes it looks, but think it over, what it does. And then you will know.

I see, the smallest is placed at the first place, but the second smallest is placed at increasing positions. This means: nothing bubbles.

The first place is used simply as my variable "minimum", and the performance is more bad, because of always exchanging elements.

But: if you decrease the inner j, as I did, this could be a more better bubble sort than mine - I don't know yet, you should think it over - yes it would, it needs less swaps - this means less write accesses to memory and so a better performance - and the performance would be still more better, if you don't place the smalles element into the first place, but hold it in a register, and store it to the first place after the inner loop. And don't forget swapped.

If you could implement the outer loop, and could follow my thoughts, you can implement the inner loop and then it's finished.

Oh I thought it over again, your bubble sort wouldn't be a bubble sort. You begin with exchanging the element at the highest position - if its smaller - with the element at the lowest position. This means, the smaller bubble down, but the bigger don't bubble up. Instead you replace the highest position with the lowest position - or similar - now I got it - you only would do a bubble sort for elements smaller than the first one you took - nothing happens to bigger ones - exept that one at the lowest position - oh that's the same as I already had said before. You should take my bubble sort.

Do you understand now about implementation? It has not much to do with C or assembly - it's imagination. C or assembly is just the notation, how you write it.

And do you know, how I learned this? By coding in assembly. Your RAM is your empty pieces of paper. And you can draw all on it, what you can imagine and in assembly without any syntactical restrictions of higher programming languages.

Sounds like Selection sort to me.

Sorry, it was a long time ago, I had known the difference between a list and a selection sort. But I forgot. Maybe this is called selection sort.

[1vRz3TCk]

dadabe wrote:

Yes it looks, but think it over, what it does. And then you will see.

Sorry, I only looked at the general structure not the details...

for(i=0;i<10;i++)
    {
        for(j=0;j<i;j++)
        {
            if(array[i]>array[j])
            {
                int temp=array[i]; //swap 
                array[i]=array[j];
                array[j]=temp;
            }

        }

    }

ResidentBiscuit originally code

    for(int x=0; x<n; x++)
    {
        for(int y=0; y<n-1; y++)
        {
            if(array[y]>array[y+1])
            {
                int temp = array[y+1];
                array[y+1] = array[y];
                array[y] = temp;
            }
        }
    }

basic bubble sort

    for(int x=0; x<n; x++)
    {
        int index_of_min = x;

        for(int y=x; y<n; y++)
        {
            if(array[index_of_min]>array[y])
            {
                index_of_min = y;
            }
        }
        int temp = array[x];
        array[x] = array[index_of_min];
        array[index_of_min] = temp;
    }

simple selection sort

I was more curious about the 'List sort' than the details of ResidentBiscuits code as I had not heard of it called that.

[ResidentBiscuit]

Good god. This is not an algorithm discussion thread. I understand sorts, I understand how they work. And dadabe, you can have ascending AND descending bubble sorts. Anyways, all I was asking for was a little bit of help implementing this in the assembly language I am given. It had a 4 bit instruction set, so I am kind of limited in what I can do. That's all, not here to argue algorithms and efficiency.

[4z0M4iN6]

Ok ResidentBiscuit, I didn't know, what's the problem. It's an interesting problem, but sorry I don't have time to learn about your assembler and help you.

Or maybe at weekend, if it's not too late for you.

[doug4]

You do realize this is a C++ forum, right?

[ResidentBiscuit]

EDIT:

Removed this cause it sounded awful rude. Frustration got the best of me, apologies

[4z0M4iN6]

CodeMonkey wrote:

I was more curious about the 'List sort' than the details of ResidentBiscuits code as I had not heard of it called that.

Yes I didn't remember this word, I only had the word list sort somewhere in my head. And now I also remember what this is. Has to do something with STL, isn't it.

Your examples are simpler and are easier to remember. But you know the example of ResidentBiscuit contained increasing beginnings. So I showed, if doing this, people should not forget to make the innerloop working backwards for a bubble sort.

And your list sort seem shorter than mine and people could think, then it would also work faster. But it only looks so in source code. In object code mine ist shorter and faster and especially easier to implement in assembler. Beginning always from 0, ResidentBiscuit should take from your code. But implementing an indexed access to RAM takes time and brain and maybe isn't neccessary - holding the minimum value in a register would be easier and faster - or maybe the indexed access could be neccessary, if we think of a 4 bit instruction set?. Could the register and data size also be only 4 bits and maybe ResidentBiscuit needs 16 bit. He didnt tell us about it. But an address register of only 4 bits doesn't make any sense. Could only address 16 nibbles of RAM - this would be very limited and I fear not sufficient for his program - especially if the instruction pointer would be limited to only four bit.

What do you think?

[ResidentBiscuit]

It's a 16 bit system, 4 bits for the opcode and 12 bits for the address. Zero and one address operations, all data goes through an accumulator. I do have some Indirect addressing opcodes, so pointers are possible, just limited.

[4z0M4iN6]

I downloaded it and could open it. Looks nice. And 12 bits for the address means 4 KB, if you can address bytes or 8 KB if it would be all 16 bit. This isn't any problem.

I suggest we take the bubble sort, which I showed (swapped) but with decreasing end, as CodeMonkey showed, if you agree.

When do you need the code?

Before we begin, we should make the C code more assembler like.
Best I should also have a look on the instruction and register set of the virtual machine.

In MarieGuide.pdf I saw 7 registers and the ALU.

Registers:

IR
OUT
IN
AC
MBR
PC
MAR

Now we have to find the register description

Oh, it's a terrible guide, I can't find anything - maybe I can find some other guide?

Oh it's only a guide to the simulator environment, not to the machine itself.

I found another very important document on the web:

MARIE: An Introduction to a Simple Computer

http://samples.jbpub.com/9781449600068/00068_CH04_Null3e.pdf

Didn't you get this? Without this document you couldn't do anything!

This would explain your problem!