Sorting is the classic first array algorithm, and bubble sort is the easiest to trace by hand. It works by repeatedly comparing neighbouring numbers and swapping any pair that is out of order. After enough passes, the smallest values have bubbled to the front. You should already be comfortable with arrays and strings and loops before this one. Emu8086 setup is in the install guide.
The idea, in one paragraph
Each pass walks the array from left to right, comparing each pair of neighbours. Whenever the left number is larger than the right one, the two are swapped. After one full pass, the largest number has reached the end. Repeating the pass for the remaining elements eventually leaves the whole array in ascending order. The code below uses four passes for a five-element array, which is more than strictly necessary but keeps the loop structure simple and easy to trace.
The complete program
Read the inner loop first: it compares the two bytes SI points at, swaps them if they are out of order, then moves SI on. The outer loop repeats that walk. CX is saved on the stack around the inner loop because both loops need CX; the stack handling is explained in full in the subroutines and stack tutorial.
ORG 100h MOV CX, 4 outer_loop: PUSH CX LEA SI, arr MOV CX, 4 inner_loop: MOV AL, [SI] MOV BL, [SI+1] CMP AL, BL JBE no_swap MOV [SI], BL MOV [SI+1], AL no_swap: INC SI LOOP inner_loop POP CX LOOP outer_loop RET arr DB 5, 2, 8, 1, 9
Trace it by hand
Start: 5, 2, 8, 1, 9. First pass: 5 and 2 swap to 2, 5; 5 and 8 stay; 8 and 1 swap to 1, 8; 8 and 9 stay. After pass one the array is 2, 5, 1, 8, 9. Second pass gives 2, 1, 5, 8, 9. Third pass gives 1, 2, 5, 8, 9. The fourth pass changes nothing, which is how you know the array is sorted. You should see exactly those intermediate states if you set a breakpoint at the POP CX line and inspect memory after each pass.
What you should see at the end
After the program finishes, the five bytes at arr should read 1, 2, 5, 8, 9 in order. If the last element looks wrong, check the inner-loop count: with five elements there are four neighbouring pairs per pass, so the inner loop must run four times, not five. Running it five times reads one byte past the end of the array and can corrupt the byte that follows it.
Ways to break it on purpose
- Change the array to 9, 8, 7, 6, 5 and trace the worst case: every pair swaps.
- Change the array to an already-sorted list and confirm that no swaps happen but the passes still run.
- Try a duplicate value, such as 3, 3, 1, and check that equal neighbours are left alone by the
JBEtest.
Next steps
Bubble sort uses the stack to protect CX; subroutines and the stack explain that mechanism properly. To revisit the basics, see arrays and strings. The opcode reference covers CMP and the conditional jumps, and the home page is the series index.
