LC3 bubble sort program in ASSEMBLY or machine code There will be 10 numbers sto
ID: 3860378 • Letter: L
Question
LC3 bubble sort program in ASSEMBLY or machine code
There will be 10 numbers stored contiguously in the computer at location x7000. Write a complete LC-3 program, starting at location x3000, that will find the location of the smallest number and swap its location with the number in location x7000. For example, Suppose the following numbers are stored at location x7000: Note the smallest element occurred at location x7007: the program swapped the contents of location x7007 with location x7000. You should make NO assumptions about the numbers located at x7000. That is, there may be negative numbers and numbers may repeat.Explanation / Answer
The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.
the first pass of a bubble sort. The shaded items are being compared to see if they are out of order. If there are n items in the list, then there are n1n1 pairs of items that need to be compared on the first pass. It is important to note that once the largest value in the list is part of a pair, it will continually be moved along until the pass is complete.
At the start of the second pass, the largest value is now in place. There are n1n1 items left to sort, meaning that there will be n2n2 pairs. Since each pass places the next largest value in place, the total number of passes necessary will be n1n1. After completing the n1n1 passes, the smallest item must be in the correct position with no further processing required. ActiveCode 1 shows the complete bubbleSortfunction. It takes the list as a parameter, and modifies it by exchanging items as necessary.
The exchange operation, sometimes called a “swap,” is slightly different in Python than in most other programming languages. Typically, swapping two elements in a list requires a temporary storage location (an additional memory location). A code fragment such as
will exchange the ith and jth items in the list. Without the temporary storage, one of the values would be overwritten.
In Python, it is possible to perform simultaneous assignment. The statement a,b=b,a will result in two assignment statements being done at the same time To analyze the bubble sort, we should note that regardless of how the items are arranged in the initial list, n1n1 passes will be made to sort a list of size n. Table 1 shows the number of comparisons for each pass. The total number of comparisons is the sum of the first n1n1 integers. Recall that the sum of the first nintegers is 12n2+12n12n2+12n. The sum of the first n1n1 integers is 12n2+12nn12n2+12nn, which is 12n212n12n212n. This is still O(n2)O(n2) comparisons. In the best case, if the list is already ordered, no exchanges will be made. However, in the worst case, every comparison will cause an exchange. On average, we exchange half of the time.
A bubble sort is often considered the most inefficient sorting method since it must exchange items before the final location is known. These “wasted” exchange operations are very costly. However, because the bubble sort makes passes through the entire unsorted portion of the list, it has the capability to do something most sorting algorithms cannot. In particular, if during a pass there are no exchanges, then we know that the list must be sorted. A bubble sort can be modified to stop early if it finds that the list has become sorted. This means that for lists that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted list and stop. ActiveCode 2 shows this modification, which is often referred to as the short bubble.
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist)-1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i]>alist[i+1]:
exchanges = True
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum = passnum-1
alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.