How to utilize the bubble sort on machine code/assembly language?

Writing a bubble sort algorithm directly in machine language can be quite complex and varies significantly based on the specific architecture (e.g., x86, ARM) you’re targeting. Machine language is the lowest level of code, consisting of binary or hexadecimal instructions executed directly by a computer’s CPU.

Instead, it’s more common to write algorithms in a high-level programming language (such as Python, C, or Java) or even in assembly language, which is one step closer to machine language but still more readable than raw binary or hexadecimal codes. Assembly language is then translated into machine language via an assembler.

If you’re interested in implementing bubble sort in assembly language for educational purposes, I  provide an example in a more common assembly language, like x86 assembly, which you could then study or modify for your specific needs. Assembly language allows you to understand the mechanics of bubble sort at a low level without dealing with the direct binary encoding of machine language.

Bubble Sort in Assembly for x86 and ARM CPUs – How to utilize the bubble sort on machine code/assembly language?

x86 Assembly Example (Intel Architecture)

section .data
    array db 9, 2, 8, 3, 7, 4, 6, 1, 5 ; Example array
    len equ $ - array                 ; Length of the array

section .text
global _start

_start:
    mov ecx, len
    dec ecx
    outer_loop:
        push ecx
        mov ecx, len
        dec ecx
        inner_loop:
            mov al, [array + ecx]
            cmp al, [array + ecx - 1]
            jge skip
            xchg al, [array + ecx - 1]
            mov [array + ecx], al
            skip:
            loop inner_loop
        pop ecx
        loop outer_loop

    ; Exit (to Linux)
    mov eax, 1          ; syscall: exit
    xor ebx, ebx        ; status 0
    int 0x80

Let’s break down the x86 assembly code example I provided earlier, line by line. This explanation will give you insights into how assembly code operates on a low level, directly interfacing with the computer’s hardware. This code was designed to sort an array using the Bubble Sort algorithm.

x86 Assembly Code Explanation

• Defines the data section, where initialized data is stored. This section is used for declaring constants or variables that do not change at runtime.

• Declares an array of bytes (db stands for ‘define byte’). This is our unsorted array which the Bubble Sort algorithm will sort.

• Calculates the length of the array by subtracting the start address of the array from the current location ($ symbol) in the data section.

• Defines the text section, where the executable code is placed. This is the section for assembly instructions.

• Makes the _start label globally visible, which is necessary for the linker to identify the entry point of the program. This is where execution begins.

• Label marking the start of the program’s execution.

• Moves the length of the array into the ECX register, which will be used as a counter for the outer loop.

• Decrements ECX by 1 because the Bubble Sort algorithm needs to iterate one less than the number of elements in the array for each pass.

• Label for the beginning of the outer loop of the Bubble Sort algorithm.

• Pushes ECX onto the stack to save its current value for later use in the inner loop.

• Re-initializes ECX with the length of the array for the inner loop.

• Prepares ECX for the inner loop by decrementing it, ensuring the inner loop does not compare beyond the array’s bounds.

• Label for the beginning of the inner loop where the actual comparison and possible swap of elements occur.

• Moves the byte at [array + ECX] into AL, the lower byte of the AX register. This instruction gets the current element for comparison.

• Compares the current element (AL) with the previous element in the array. The CMP instruction sets flags based on the comparison.

• Jumps if greater or equal based on the comparison. If the current element is greater than or equal to the previous one, it skips the swap operation.

• Exchanges the current element with the previous one if the current element is less than the previous one. This is the swap operation.

• Moves the value in AL back into the array at the current position, completing the swap if it occurred.

• Label for skipping the swap operation if the current element is in the correct order relative to the previous element.

• Decrements ECX and loops back to the inner_loop label if ECX is not zero. This continues the inner loop until all elements for this pass are compared.

• Pops the saved value of ECX off the stack to restore it for the next pass of the outer loop.

• Decrements ECX and loops back to the outer_loop label if ECX is not zero. This continues the outer loop until the array is sorted.

• Exits the program. This sequence of instructions performs a system call to exit the program. mov eax, 1 sets up the system call number for exit. xor ebx, ebx sets the exit status to 0, indicating success. int 0x80 triggers the system call.

This code provides a basic illustration of sorting an array using the Bubble Sort algorithm in x86 assembly language, showcasing direct manipulation of memory and registers to perform sorting operations.

ARM Assembly Example – How to utilize the bubble sort on machine code/assembly language?

    .section .data
array:  .byte 9, 2, 8, 3, 7, 4, 6, 1, 5
len = . - array

    .section .text
    .globl _start

_start:
    ldr r4, =len
    subs r4, r4, #1
outer_loop:
    push 
    ldr r4, =len
    subs r4, r4, #1
inner_loop:
    ldrb r2, [r0, r4]
    subs r3, r4, #1
    ldrb r1, [r0, r3]
    cmp r2, r1
    strhs r1, [r0, r4]
    strhs r2, [r0, r3]
    subs r4, r4, #1
    bne inner_loop
    pop 
    subs r4, r4, #1
    bne outer_loop

    /* Exit (to Linux) */
    mov r0, #0
    ldr r7, =1
    swi 0

Let’s break down the ARM assembly code example provided earlier, line by line. This explanation will help you understand how this assembly code operates, specifically targeting the ARM architecture and using the Bubble Sort algorithm to sort an array.

ARM Assembly Code Explanation

• Defines the data section where initialized data, such as constants and arrays, are stored. This is used for declaring data that the program will use.

• Declares an array with the .byte directive, initializing it with a series of numbers. This is the array that will be sorted.

• Calculates the length of the array by subtracting the starting address of the array from the current location (denoted by .). This provides the size of the array for loop control.

• Defines the text section, where the executable code resides. This section contains the assembly instructions that make up the program.

• Specifies the global label _start, indicating the entry point of the program. This is where execution begins when the program is run.

• Marks the beginning of the executable code. This label is essential as it is where execution starts.

• Loads the length of the array into register r4. The ldr instruction is used here to load the address or value into a register. In this case, it’s loading the size of the array for loop control.

• Subtracts 1 from the value in r4. The subs instruction subtracts the second and third operands (here, r4 and 1), stores the result in the first operand (r4), and updates the condition flags based on the result.

• Label for the beginning of the outer loop of the Bubble Sort algorithm.

• Pushes the value of r4 onto the stack. This saves the current counter value so it can be restored later, allowing for nested looping.

• Re-initializes r4 for the inner loop, similar to the previous initialization but repeated to ensure the inner loop has the correct starting value.

• Label for the beginning of the inner loop, where the comparison and potential swapping of array elements happen.

• Loads a byte from the array into r2. The ldrb instruction loads a single byte from the address calculated by adding r0 (which should hold the base address of the array) and r4 into register r2.

• Calculates the address of the previous element by subtracting 1 from r4 and storing the result in r3.

• Loads the previous byte (element) into r1 for comparison with the current element (r2).

• Compares the values in r2 and r1. The cmp instruction compares two registers and sets the condition flags accordingly without storing the result.

• Conditionally swaps the elements if r2 (current element) is higher than r1 (previous element). strhs (store halfword if higher or same) instructions conditionally execute based on the result of the last comparison, swapping the elements if necessary.

• Decrements the loop counter (r4) to move through the array.

• Branches to inner_loop if not equal to zero. The bne instruction causes the program to loop back to the inner_loop label if the zero flag is not set, indicating that there are more elements to process.

• Pops the saved value of r4 off the stack. This restores the outer loop counter from the stack, preparing for the next iteration of the outer loop.

• Continues the outer loop if not completed. The loop counter is decremented, and if it’s not zero, the program branches back to outer_loop.

• Exits the program. This sets up for a system call to exit the program. mov r0, #0 sets the exit status to 0 (success), ldr r7, =1 loads the system call number for exit into r7, and swi 0 invokes the system call interrupt.

This breakdown explains the ARM assembly code’s operation for sorting an array using the Bubble Sort algorithm, demonstrating the direct hardware manipulation characteristic of assembly language programming.

Compiling and running assembly code involves several steps, largely dependent on the specific CPU architecture (e.g., x86 or ARM) and the operating system you’re using. Here’s a general overview of how this process works:

1. Writing the Code

First, you write your assembly code in a text editor and save it with an appropriate extension (e.g., .asm for NASM).

2. Compiling the Code

Assembly code is typically assembled (rather than compiled in the traditional sense) into machine code using an assembler like NASM (Netwide Assembler) for x86 architecture or GAS (GNU Assembler) for ARM. The assembler translates your assembly language instructions into machine code.

• For x86 using NASM:
  nasm -f elf64 yourcode.asm -o yourcode.o


  This command generates an object file (yourcode.o). The -f elf64 option tells NASM to output in the ELF 64-bit format, suitable for x86-64 Linux systems.

• For ARM: The process is similar, but you’d use an assembler that supports ARM instructions, possibly using a cross-assembler if you’re compiling on a non-ARM machine.

3. Linking

After assembling, you need to link the object file(s) to create an executable. This step involves resolving addresses for any external references and libraries your code might use (though, in many assembly programs, external references are minimal).

• Using ld (the GNU linker):
  ld yourcode.o -o yourcode


  This creates an executable file from your object file.

4. Running the Executable

Once you have your executable, you can run it directly from the terminal in Linux:

How Does It Work Internally?

• Loading: When you execute the program, the operating system loads it into memory.
• Execution: The CPU reads the machine code instructions from the entry point specified in the executable file. For assembly programs, this often directly corresponds to the start of your _start label or equivalent.
• Instruction Processing: The CPU executes each instruction sequentially unless instructed otherwise by control flow instructions (e.g., jumps, calls). The instructions perform operations such as moving data between registers, performing arithmetic operations, or interacting with memory.
• System Calls: For operations like input/output or exiting the program, your assembly code makes system calls to the operating system kernel.
• Termination: Once the program reaches its termination point (often a system call to exit), control is returned to the operating system, and the program’s memory is freed.

The direct nature of assembly language programming allows for precise control over the hardware but requires a detailed understanding of the CPU architecture and the operating system’s conventions for things like system calls.

Bubble sorting in assembly language asm algorithm | bubble sort assembly code | ascending order

Bubble Sort in Data Structure | Bubble sort algorithm | Bubble Sort- Algorithm & Procedure

Related Videos:

Related Posts:

How do I make my Java program sort data or an array? Bubble Sort.(Opens in a new browser tab)

How Do You Implement Bubble Sort in JavaScript?(Opens in a new browser tab)

Computer Programming Sorting Algorithms(Opens in a new browser tab)

How Does the Bubble Sort Algorithm Work in VB.NET?(Opens in a new browser tab)

Surface Pro 10: The Dawn of a New Era for 2-in-1 Devices(Opens in a new browser tab)