quicksort

[peter84]

Hi, I'm doing quicksort in assembly (masm), but I have no idea how to start. Maybe I'll get help from the course later, but I want to start anyway. So... what would you do in this case? Splitting the programming-task into small pieces, so, what pieces do you think that should be? Not looking for code, just some help thinking the right way  :thumbu

[sluggy]

The best thing for you to do is to learn the simple theory behind the quicksort algorithm, then design a bit of code, then ask the questions.

This link, and particularly this one should help you.

[PBrennick]

peter84,

Hutch is working on the exect same thing and will be posting his code sometime today in this thread, http://www.masmforum.com/simple/index.php?topic=2579.msg20396#msg20396

It will give you some ideas.
Paul

[peter84]

Thanks for the replies guys! Guess I forgot to mention that I've already done quicksort in java about a year ago.

I guess what is bothering me is how to represent an array in assembly, how to make the algorithm manipulate it, i.e. choose a pivot and compare all other to that. We have the cmpl-operand (using GNU/linux), and the bigger and smaller elements are to be seperated. Where do I store the 2 smaller parts, and then the 4 smaller parts, etc?

Appreciete your replies!  :wink

[Eóin]

Here is some example code of an inner QuickSort loop. First the Java code for reference, then the Assembly. I'm not posting the full code to avoid overwhelming you.

Code Select Expand

j = r-1;
i = l;
v = a[j];
for(;;)
{
    while(a[++i]<v);
    while(a[--j]>v);
    if (j<i) break;
    swap (a,i,j);
}

Code Select Expand


mov edi,[rgh]
mov esi,[lft]
sub edi,4

mov edx,[ebx+edi]
.lpFor:
.wle1: add esi,4
cmp [ebx+esi],edx
jl .wle1

.wle2: sub edi,4
cmp [ebx+edi],edx
jg .wle2

cmp esi,edi
jg .exFor

mov eax,[ebx+esi]
mov ecx,[ebx+edi]
mov [ebx+edi],eax
mov [ebx+esi],ecx
jmp .lpFor
.exFor:

In the java code a is the array. l & r are offsets representing the left and right hand side of the partition to divide. v is chosen as the pivot and i & j become the offsets to the array elements which get compared against the pivot.

The Assembly code has many one-to-one correspondences with the java code. The array in assembly in a continuous block of memory, perhaps allocated by a routine like HeapAlloc on Windows. The array (in this example) stores integers as DWORDs, hence when incrementing or decrementing an offset into the array, 4 is added or subtracted, 4 being the size of a DWORD.

A pointer to the start of this array is kept in ebx. The pivot value is moved into edx, and edi & esi become the offset into the array that scan from the left and right sides of the partition. You can see how after the appropriate elements in the array are determined for swapping a check is performed to see if we need to exit the loop early much like the if (j<i) break; code in the java version.

I will quite happily post the full code if you wish but it’s written in FASM (similar but not identical to MASM) and it uses an Insertion Sort after the partitions get below a critical size, which is a feature you may not want. And of course you say you don't just want to be handed code.

[peter84]

Thanks Eóin! I think I see the solution in front of me now (no, not at the computerscreen  :P). I'll keep working, and drop a post if I'm stuck.

Oh, and thanks for the good explanation. Are you a teacher? :)

[Eóin]

No, but I hope to teach Math eventually when I finish my studies.

[PBrennick]

Eóin,
Personally, I think you will be great at that!  Keep up the studies and the good work!
Paul

[peter84]

So... I can reserve space for the numbers with the .equ-operand, but how do I define how large it should be? And does anyone know how to translate this to GNU/linux asm: cmp [ebx+esi],edx # the stuff inside the [ ]

Thanks!  :8)

[Eóin]

It's not so much a question of GNU/linux asm, rather its a question of which Assembler are you using. Unforunatly if you're using GAS not many people here will probably know of it seeing as this forum is mostly MASM users.

[roticv]

gas has a screwed up convention of

opcode src, dest

while most assembler has the convention of

opcode dest, src

So in gas cmp [ebx+esi],edx
is the same as cmp edx, [ebx+esi] in masm

[notoka]

I would submit that it is Intel's format: Destination, Source that is counterintuitive.  Do you know of any airline that asks from a prospective passenger the destination, PRIOR to inquiring about the intended port of embarkation? http://portal.lufthansa.com/online/portal?ctest=1
::)

[Eóin]

I would submit that equating English language grammar (or metaphors ::) ) to assembly is ridiculous.

[roticv]

HAHA

What about equating it to another programming language?

Like for example in C, we do

var = 1;

isn't that the same as

dest, src

:lol

[rea]

That remember me time a go... tought dont remember exactly what was my problem with that  :green2.