Solved

Difference / order nlog(n) VS. n^2 algorithm.

Posted on 1998-09-19
5
456 Views
Last Modified: 2006-11-17
What is the difference between an order nlog(n) and n^2 algorithm.  Please give a detailed explanation and examples of each in VB5.  I believe this relates to asymtotic boundaries and sorting heaps and such, but need a definitive answer that an MIS dude can understand.  Email to me if you have the time:

jhowell@cyberhighway.net

Thanks!!!
0
Comment
Question by:jwhowell
[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
  • 2
  • 2
5 Comments
 
LVL 3

Expert Comment

by:a111a111a111
ID: 1435718
Private Sub Form_Load()
MsgBox 10 ^ 2   '>> it is like 10 times 10
MsgBox 10 * Log(10) ' >> it is like 10 times log(base 10)of 10
End
End Sub

0
 

Author Comment

by:jwhowell
ID: 1435719
a111a111a111,

Thank you for the math lesson on natural logrithms, but I was hoping for a a bit more.  This relates to sorting algorithms and I need examples of each equation where I can generate a large random array or something and time the sorting of each algorithm based on the volume of the sort.  Do you have any code for timing sorting like I describe?

jwhowell
0
 
LVL 1

Accepted Solution

by:
steve06 earned 110 total points
ID: 1435720
The "speed" of a sort algorythm is measured based on the number of operations to be done, compared to the number of elements to sort.

For example, the simple "bubble sort" is of order n^2, because the number of times you go through the loop and the test increases by the square of the number of values to sort:

For i = 1 to NbElement - 1
    For j = i to NbElement
        if strArray(i) > strArray(j) then
            strTemp = strArray(i)
            strArray(i) = strArray(j)
            strArray(j) = strTemp
        end if
    Next j
Next i

If NbElement is 100, you need about 5,000 iterations.
If NbElements is 1,000, you need about 500,000 iterations, 100 times more while the number of elements is only 10 times greater.

There is one sort algorithm which is of order n*ln(n): it is called QuickSort. Here is the routine:

Sub QuickSort_VB(iLow As Long, iHigh As Long)
                            ' QuickSort works by picking a random "pivot" element in lInput, then
                            ' moving every element that is bigger to one side of the pivot, and every
                            ' element that is smaller to the other side.  QuickSort is then called
                            ' recursively with the two subdivisions created by the pivot.  Once the
                            ' number of elements in a subdivision reaches two, the recursive calls end
                            ' and the array is sorted.
   
   Dim i As Long
   Dim j As Long
   Dim iRand As Long
   Dim lPartition As Long
   Dim lTemp As Long
   
   If iLow < iHigh Then

                            ' Only two elements in this subdivision; swap them if they are out of
                            ' order, then end recursive calls:
      If iHigh - iLow = 1 Then
         If bt(iLow) > bt(iHigh) Then
            lTemp = bt(iLow)
            bt(iLow) = bt(iHigh)
            bt(iHigh) = lTemp
         End If
      Else

                            ' Pick a pivot element at random, then move it to the end:
         iRand = iLow + Int(Rnd * (iHigh - iLow + 1))
         lTemp = bt(iHigh)
         bt(iHigh) = bt(iRand)
         bt(iRand) = lTemp
         lPartition = bt(iHigh)
         Do

                            ' Move in from both sides towards the pivot element:
            i = iLow
            j = iHigh
            Do While (i < j) And (bt(i) <= lPartition)
               i = i + 1
            Loop
            Do While (j > i) And (bt(j) >= lPartition)
               j = j - 1
            Loop

                            ' If we haven't reached the pivot element, it means that two
                            ' elements on either side are out of order, so swap them:
            If i < j Then
               lTemp = bt(i)
               bt(i) = bt(j)
               bt(j) = lTemp
            End If
         Loop While i < j

                            ' Move the pivot element back to its proper place in the array:
         lTemp = bt(i)
         bt(i) = bt(iHigh)
         bt(iHigh) = lTemp

                            ' Recursively call the QuickSort procedure (pass the smaller
                            ' subdivision first to use less stack space):
         If (i - iLow) < (iHigh - i) Then
            QuickSort_VB iLow, i - 1
            QuickSort_VB i + 1, iHigh
         Else
            QuickSort_VB i + 1, iHigh
            QuickSort_VB iLow, i - 1
         End If
      End If
   End If
End Sub


The procedure above sorts the array bt().

I think some mathematicians have demonstrated that this sort is much faster, although it is impossible to exactly predict hw much time it will take to sort an array. It depends on the "disorder' of the initial array.

Hope this help,
0
 

Author Comment

by:jwhowell
ID: 1435721
Steve06,

You are the man!  Thanks a bunch.  I may want to Email you about the small comparison app I'll build using your algorithms.  Could you send me your Email address?  I also ordered a book called 'Ready-To-Run Visual Basic Algorithms.'  Do you know this book?

Here are the points!

Jason W. Howell
0
 
LVL 1

Expert Comment

by:steve06
ID: 1435722
Jason,

I don't know the book you mention. May be it contains sort algorithms as well.

I am happy that I could answer your question. My e-mail is
steve06@infonie.be

Steve.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

The debugging module of the VB 6 IDE can be accessed by way of the Debug menu item. That menu item can normally be found in the IDE's main menu line as shown in this picture.   There is also a companion Debug Toolbar that looks like the followin…
Most everyone who has done any programming in VB6 knows that you can do something in code like Debug.Print MyVar and that when the program runs from the IDE, the value of MyVar will be displayed in the Immediate Window. Less well known is Debug.Asse…
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
This lesson covers basic error handling code in Microsoft Excel using VBA. This is the first lesson in a 3-part series that uses code to loop through an Excel spreadsheet in VBA and then fix errors, taking advantage of error handling code. This l…
Suggested Courses
Course of the Month7 days, 23 hours left to enroll

617 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