8085 program for bubble sort

Prerequisite – Bubble Sort
Problem – Write an assembly language program in 8085 microprocessor to sort a given list of n numbers using Bubble Sort.

Example –

Assumption – Size of list is stored at 2040H and list of numbers from 2041H onwards.

Algorithm –

1. Load size of list in C register and set D register to be 0
2. Decrement C as for n elements n-1 comparisons occur
3. Load the starting element of the list in Accumulator
4. Compare Accumulator and next element
5. If accumulator is less than next element jump to step 8
6. Swap the two elements
7. Set D register to 1
8. Decrement C
9. If C>0 take next element in Accumulator and go to point 4
10. If D=0, this means in the iteration, no exchange takes place consequently we know that it won’t take place in further iterations so the loop in exited and program is stopped

Program –

2000H START LXI H, 2040H Load size of array
2003H MVI D, 00H Clear D register to set up a flag
2005H MOV C, M Set C register with number of elements in list
2006H DCR C Decrement C
2007H INX H Increment memory to access list
2008H CHECK MOV A, M Retrieve list element in Accumulator
2009H INX H Increment memory to access next element
200AH CMP M Compare Accumulator with next element
200EH MOV B, M Swap the two elements
200FH MOV M, A
2010H DCX H
2011H MOV M, B
2012H INX H
2013H MVI D, 01H If exchange occurs save 01 in D register
2015H NEXTBYTE DCR C Decrement C for next iteration
2019H MOV A, D Transfer contents of D to Accumulator
201AH CPI 01H Compare accumulator contents with 01H
201FH HLT HALT

Explanation-

• Retrive an element in accumulator.
• Compare it with next element, if it is greater then swap otherwise move to next index.
• If in one entire loop there has been no exchange, halt otherwise start the whole iteration again.
• The following approach has two loops, one nested inside other so-

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.