alqaoud
asked on
bubble sort program
I wrote a program in (a86 )to sort the whole array into ascending order and it’s run ok but how can I make it more effcient(reducing unnecessary work) this is my code;
Code segment
Jmp main
Add1 dw 9,3,2,7,1,4,2,5,8,1
Main: mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
ret
order: call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
orderab: mov ax,add1[si]
cmp ax,add1[si+2]
jli finish
mov bx,add1[si+2]
mov add1[si],bx
mov add1[si+2],ax
finish: inc si
inc si
ret
Code segment
Jmp main
Add1 dw 9,3,2,7,1,4,2,5,8,1
Main: mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
mov si,0
call order
ret
order: call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
call orderab
orderab: mov ax,add1[si]
cmp ax,add1[si+2]
jli finish
mov bx,add1[si+2]
mov add1[si],bx
mov add1[si+2],ax
finish: inc si
inc si
ret
ASKER
terageek, thank you very much but you first program give this result 2,3,1,7,2,4,8,5,9,1 and the second program didn't excute correctly and the the result i need should be 1,1,2,2,3,4,5,7,8,9 like the result from my program i wrote in beginning.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
The best way to make the sort more efficient is to use a different algorithm such as quicksort, heapsort, or mergesort. Those types of sorts require n* log n comparisons on average, while a sort such as bubble sort requires n*n comparisons. These algorithms are a lot faster, especially for arrays larger than 300 or so. For some examples of other algorithms and source code, try http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html.
Actually, an optimized bubble-sort will require only n comparisons on an array which is already sorted. Quicksort, heapsort, mergesort and insertionsort all take n*log n. If your data set is already mostly sorted, bubble-sort will give you the best average runtime.
if the list is sorted and all you are trying to do is insert an element you dont need anywhere near n comparisons, you will only need log n
each comparison you are chopping the list in 1/2
each comparison you are chopping the list in 1/2
Sorting a list and inserting an element into a sorted list are two different problems.
There are a few algorithms for inserting a new element into a sorted list. There is a binary search insertion which requires log (n) compares, and there is a linear search insertion which can take from 1 to n compares. If your data is in a linked list or you can start off taking a guess as to about where a piece of data should go, the linear search can be faster on average.
Dispite the big-O analysis, sometimes a generally "slower" algorithm can be faster when you take into account your specific data-set.
There are a few algorithms for inserting a new element into a sorted list. There is a binary search insertion which requires log (n) compares, and there is a linear search insertion which can take from 1 to n compares. If your data is in a linked list or you can start off taking a guess as to about where a piece of data should go, the linear search can be faster on average.
Dispite the big-O analysis, sometimes a generally "slower" algorithm can be faster when you take into account your specific data-set.
Code segment
Jmp main
Add1 dw 9,3,2,7,1,4,2,5,8,1
Main: mov cx, 9
call order
mov cx, 8
call order
mov cx, 7
call order
mov cx, 6
call order
mov cx, 5
call order
mov cx, 4
call order
mov cx, 3
call order
mov cx, 2
call order
mov cx, 1
call order
ret
order: xor si, si
orderab: mov ax,add1[si]
cmp ax,add1[si+4]
jle finish
mov bx,add1[si+4]
mov add1[si],bx
mov add1[si+4],ax
finish: add si, 4
loop orderab
ret
This will reduce the work almost in half, but add some overhad from the loop. If you are concerned about average run-time, you could do the following. It will run very quickly if the list is already in order (just 9 compares!), but slower than the above code if it is in reverse order (same number of compares, with more overhead).
Main: mov cx, 9
order: xor si, si
mov di, cx
xor dx, dx
orderab:
mov ax,add1[si]
cmp ax,add1[si+4]
jle finish
mov dx, di
sub dx, ci
mov bx,add1[si+4]
mov add1[si],bx
mov add1[si+4],ax
finish: add si, 4
loop orderab
inc dx
mov cx, dx
loop order
ret