Solved

# bubble sort program

Posted on 2003-11-23
26,673 Views
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

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

jli finish
finish:      inc si
inc si
ret
0
Question by:alqaoud
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions

LVL 3

Expert Comment

ID: 9820549
Each time you call order, you need to call orderab 1 fewer time.  In addition, you could put orderab inline.  I left main unrolloed since it is still called a constant number of times.  Also, since you have dwords, shouldn't your indexes go by 4?

Code segment
Jmp  main

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
jle finish
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:
jle finish
mov dx, di
sub dx, ci
finish:     add si, 4
loop orderab
inc dx
mov cx, dx
loop order
ret
0

Author Comment

ID: 9821949
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.
0

LVL 3

Accepted Solution

terageek earned 50 total points
ID: 9822072
Hmmm....

If your code worked correctly, you can try changing my 4s to 2s.

I just saw a typo in the second code...

sub dx, ci
should be:
sub dx, cx
0

Expert Comment

ID: 10136562
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.
0

LVL 3

Expert Comment

ID: 10150426
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.
0

Expert Comment

ID: 10465516
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
0

LVL 3

Expert Comment

ID: 10474109
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.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

### Suggested Solutions

This article describes how to import an Outlook PST file to Office 365 using a third party product to avoid Microsoft's Azure command line tool, saving you time.
Had a business requirement to store the mobile number in an environmental variable. This is just a quick article on how this was done.
In an interesting question (https://www.experts-exchange.com/questions/29008360/) here at Experts Exchange, a member asked how to split a single image into multiple images. The primary usage for this is to place many photographs on a flatbed scanner…
Finding and deleting duplicate (picture) files can be a time consuming task. My wife and I, our three kids and their families all share one dilemma: Managing our pictures. Between desktops, laptops, phones, tablets, and cameras; over the last decade…
###### Suggested Courses
Course of the Month2 days, 10 hours left to enroll

#### 752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.