3A. Sort 'n' numbers in ascending order using Bubble sort - [VTU 4th sem Mp lab program]

Q) Sort a given set of ‘n’ numbers in ascending order using Bubble Sort algorithm.

This program sorts the given numbers in ascending order using the bubble sorting algorithm. There is no output displaying in the console/prompt in this program. We have to see the sort being performed in the debugging screen. See ‘How to compile and debug the '.asm' code in the prompt.’

Algorithm:

Step 1: Initialize array elements in data segment.
Step 2: Initialize the number of elements in a array(N-array)
             Number of elements in array (N)
             =current address of memory pointer ($)– array of Array N(array name)
Step 3: Where List is array of ‘n’ elements 
             Bubble(int(list[],know)
             {
              int i,j;
              for(i=1;i<=n;i++)
                 for(j=1;j<=n-i;j++)
                    if(list[j]>=list[j+1])
                         swap(list[j],list[j+1])
             }
Step 4: Stop


CODE:

Explanation:

• .MODEL SMALL 
• .DATA 
• LIST DB 50H,10H,78H,15H,07H 
• LEN DW $-LIST

As usual, One data and one code segment each.
Data segment begins.
LIST is a memory location with 5 immediate values stored in it which needs to be sorted, each of byte length. This is the actual array input to the program and output should be the same array in the ascending order
LEN is a location which stores the length of the array as,
Current Pointer Position (indicated by $) - Array base address (indicated by array name)
Which will give 5-0=5.


Consider our array size. That is LEN=5. Now,

• .CODE 
• MOV AX,@DATA     
• MOV DS,AX 
• MOV BX,LEN 
• DEC BX 

Beginning of code segment. 
Data segment is initialized using the second and third line in the snippet. 
Length of the list is stored in BX register (now BX=5) and BX is decreased by value 1(now BX=4). Proceed. 

• .OUTLOOP: 
• MOV CX,BX 
• MOV SI,0 

This can represent the outer ‘for loop (i=1 to n)’ of the algorithm given at the beginning.
OUTLOOP is a label.
CX is loaded with BX. You will get know the purpose later at the end.
For now, CX=4. (4 is actually the offset address of last element because 5 elements having offsets {0,1,2,3,4}).

So for each iteration of OUTLOOP, some tasks are run inside the INLOOP and at the end,  LOOP instruction is called (line 23 of the full code in this post) which decreases CX by 1 and jumps back to INLOOP if CX was not 0). This means INLOOP is run from 4 to 0 at the beginning(5 times) , and one less each for the next iterations (since CX will change after complete iteration of INLOOP) . 

Something like this,
for(outloop=1 ; outloop <= n ; outloop++)
{
    for(inloop=1 ; inloop<= n-outloop ; inloop++)
   {
             if(list[j]>=list[j+1])
                swap(list[j],list[j+1])
   
   /*find the greatest element here comparing each pair of two elements in the array from start to end and take it to the end*/
   }
   
   //one element sorted per iteration.
}

Let’s see how, in detail:

Stack index(SI) is loaded with 0. To start comparing each element with its next element in the INLOOP.

• INLOOP: 
• MOV AL,LIST[SI]             
• INC SI 
• CMP AL,LIST[SI]             
• JB GO_ON     
• XCHG AL,LIST[SI] 
• MOV LIST[SI-1],AL

INLOOP is a label.
Now contents in the location pointed to by SI, that is the first element (since SI was loaded with 0) is copied to AL register using MOV AL,LIST[SI] instruction.(Since two direct memories can not be compared using CMP)

SI is increased by 1, to get to the next element(second element of the array).

Now CMP compares both AL (that is one element in the array) and the immediate next element (present at SI+1 index). If AL is smaller than its next element(sorted), we can continue for the next iteration of the INLOOP(that is check the next two pairs of elements for greater or smaller). That is done using '‘JB GO_ON’' (jump to label GO_ON, if AL is below its next element).

If AL is bigger than its next element(unsorted), We need to swap AL and LIST[SI]. That is done using XCHG instruction. But during swapping, The actual array elements are not being swapped. Instead, its a Register and a LIST[SI] being swapped. (because AL was just a copy of LIST[SI], if you remember).
In the actual array, LIST[SI-1] remains unchanged. So we need to copy AL contents to LIST[SI-1] in order to swap in array too. Now swapping is done.


Now if AL was smaller than LIST[SI+1], we need to continue the INLOOP without swapping anything.

• GO_ON: 
• LOOP INLOOP 
• DEC BX 
• JNZ OUTLOOP

GO_ON is the label which was accessed from (AL < LIST[SI+1] condition above)

LOOP instruction will decrease CX by 1 and if CX is not zero, will jump to the label specified. So the next iteration of the INLOOP is so decided based on CX value. (at first INLOOP will run for 4 times and for the next iterations, 3,2,1 and 0 times. Since the elements at the end will be already sorted during the next iterations).

Now if CX was 0, this means INLOOP has ended. Then decrease BX by 1 and jump to OUTLOOP label if BX not zero. (NZ OUTLOOP). And again run same procedures.

For each iteration of OUTLOOP, one element will be sorted and will be at the end position in the array.So you don't need to bother about that element next. So CX value is set with BX for each new iteration of OUTLOOP. See the code (MOV CX,BX).


After BX is 0, OUTLOOP will end and hence all the elements are sorted.

• END  Declares end of the code

Output:
Output of this code is seen in the debugging screen. 
Compile, link and type '‘afdebug program.asm’ '

See the register values as it gets sorted. 

[PS: Hope this helped. Though its difficult to Explain this code in text, i have put heavy efforts to do the same. If you still didn't get this, Drop comments and let me or any other audience solve it.]

Author : Anonymous

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!

Sharing is sexy!

Related Articles