Solved

bubble sort program

Posted on 2003-11-23
8
26,659 Views
Last Modified: 2011-08-18
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
0
Comment
Question by:alqaoud
8 Comments
 
LVL 3

Expert Comment

by:terageek
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
     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
0
 

Author Comment

by:alqaoud
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

by:
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
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 

Expert Comment

by:tkcan30
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

by:terageek
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

by:SOBKing
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

by:terageek
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

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Assembly Language - 8086 Processor 3 1,073
cmpl in assembly 5 1,342
MIPS Assembly Language 3 789
DOS function for Text Windows size 8 302
Google Drive is extremely cheap offsite storage, and it's even possible to get extra storage for free for two years.  You can use the free account 15GB, and if you have an Android device..when you install Google Drive for the first time it will give…
Having trouble getting your hands on Dynamics 365 Field Service or Project Service trial? Worry No More!!!
Email security requires an ever evolving service that stays up to date with counter-evolving threats. The Email Laundry perform Research and Development to ensure their email security service evolves faster than cyber criminals. We apply our Threat…
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …

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

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

Join & Ask a Question