Sorting algorithms (sort array)

Ellis Dee said, "To correct it is simple: you need to change "While Jump" to "While Jump > 1", and I need to change "Loop Until lngJump = 0" to "Loop Until lngJump = 1"."
-----------------------
Terrific! You would not believe how much that improved the speed of the Jump Sort! Now after 20,000 elements or more, Jump Sort is faster than the VB sorted list box. Your simple yet ingenious improvement eliminated N comparisons.:thumb:

You asked if While...Wend is faster than Do...Loop Until. I believe it makes no difference in execution speed. I checked it by modifying my code for both the inner and outer loops. In either case, I can sort 60,000 random 9-character stings in less than 9 seconds. I used "Loop Until Jump < 2" rather than "Loop Until Jump = 1" on the outer loop and "Loop Until Not Swapped" on the inner loop. Years ago I read that inequality tests run faster than equality tests, but that may be nonsense these days.

You may now have to raise the grade you bestowed on the Jump Sort in the Code Bank from B- to B+.;)

The difference between While ... Wend and Do ... Loop is that Do allows for both While and Until conditions, and it allows you to control when the condition is checked: at the beginning of execution of the loop or at the end of it.

Code:

---

Do While False
    MsgBox "One"
Loop

Do
    MsgBox "Two"
Loop While False

---

Speed difference is what one could call "non-existant".

Merri, could you help me fix the Shaker Sort you posted? The initial loops don't actually do anything except waste an inordinate amount of time.

I noticed this yesterday and today, which is when I finally got around to implementing graphical sorts like that java page. (It's amazing how helpful graphical displays are for pinpointing faulty algorithms.)

Here's the original code you posted. I've highlighted the faulty comparisons:

Code:

---

Public Function ShakerSort(ByRef LongArray() As Long) As Long()
    Dim lngLB As Long, lngUB As Long, lngOut() As Long, NoSwap As Boolean
    Dim lngA As Long, lngB As Long, lngC As Long, lngTemp As Long
    If ArrayInit(Not LongArray) Then
        lngLB = LBound(LongArray)
        lngUB = UBound(LongArray)
        If lngLB < lngUB Then
            lngOut = LongArray
            lngA = lngUB \ 2
            Do While lngA > 0
                lngB = lngA
                Do While lngB > 0
                    For lngC = 0 To lngUB - lngB
                        If lngOut(lngA) > lngOut(lngA + 1) Then
                            lngTemp = lngOut(lngA)
                            lngOut(lngA) = lngOut(lngA + 1)
                            lngOut(lngA + 1) = lngTemp
                        End If
                    Next lngC
                    lngB = lngB \ 2
                Loop
                lngA = lngA \ 2
            Loop
            lngUB = lngUB - 1
            Do Until NoSwap
                NoSwap = True
                For lngA = lngLB To lngUB
                    If lngOut(lngA) > lngOut(lngA + 1) Then
                        lngTemp = lngOut(lngA)
                        lngOut(lngA) = lngOut(lngA + 1)
                        lngOut(lngA + 1) = lngTemp
                        NoSwap = False
                    End If
                Next lngA
                If Not NoSwap Then
                    NoSwap = True
                    lngUB = lngUB - 1
                    For lngA = lngUB To lngLB Step -1
                        If lngOut(lngA) > lngOut(lngA + 1) Then
                            lngTemp = lngOut(lngA)
                            lngOut(lngA) = lngOut(lngA + 1)
                            lngOut(lngA + 1) = lngTemp
                            NoSwap = False
                        End If
                    Next lngA
                    lngLB = lngLB + 1
                End If
            Loop
            ShakerSort = lngOut
        Else
            ShakerSort = LongArray
        End If
    End If
End Function

---

I think the other two comparisons are fine.

Replace lngA with lngC.

Yep, that seemed to improve it quite a bit, though it's still doing more comparisons than bubblesort. That in and of itself doesn't concern me, though.

If you look at the java page you linked upthread, they show a ShakerSort and a ShakerSortTwo. Both show the initial loops as comparing elements more than one position apart. The Shaker sort logic that you posted looks like it's intended to do something similar, though it always compares an element with one right next to it.

Is that what you intended?

Attached is a standalone form that demonstates exactly what the Shakersort is doing.

This is obviously a work in progress; ignore the comparison and exchange totals. (And mergesort is still not implemented properly.) But it will clarify what the algorithm is doing, at least.

Quote:

---

Originally Posted by Ellis Dee

Yep, that seemed to improve it quite a bit, though it's still doing more comparisons than bubblesort. That in and of itself doesn't concern me, though.

If you look at the java page you linked upthread, they show a ShakerSort and a ShakerSortTwo. Both show the initial loops as comparing elements more than one position apart. The Shaker sort logic that you posted looks like it's intended to do something similar, though it always compares an element with one right next to it.

Is that what you intended?

---

Humm, reread the code now, I did the sort code quickly when I did it so I copied the + 1 idea from the wrong lines :)

Code:

---

Public Function ShakerSort(ByRef LongArray() As Long) As Long()
    Dim lngLB As Long, lngUB As Long, lngOut() As Long, NoSwap As Boolean
    Dim lngA As Long, lngB As Long, lngC As Long, lngTemp As Long
    If ArrayInit(Not LongArray) Then
        lngLB = LBound(LongArray)
        lngUB = UBound(LongArray)
        If lngLB < lngUB Then
            lngOut = LongArray
            lngA = lngUB \ 2
            Do While lngA > 0
                lngB = lngA
                Do While lngB > 0
                    For lngC = 0 To lngA - lngB
                        If lngOut(lngC) > lngOut(lngC + lngB) Then
                            lngTemp = lngOut(lngC)
                            lngOut(lngC) = lngOut(lngC + lngB)
                            lngOut(lngC + lngB) = lngTemp
                        End If
                    Next lngC
                    lngB = lngB \ 2
                Loop
                lngA = lngA \ 2
            Loop
            lngUB = lngUB - 1
            Do Until NoSwap
                NoSwap = True
                For lngA = lngLB To lngUB
                    If lngOut(lngA) > lngOut(lngA + 1) Then
                        lngTemp = lngOut(lngA)
                        lngOut(lngA) = lngOut(lngA + 1)
                        lngOut(lngA + 1) = lngTemp
                        NoSwap = False
                    End If
                Next lngA
                If Not NoSwap Then
                    NoSwap = True
                    lngUB = lngUB - 1
                    For lngA = lngUB To lngLB Step -1
                        If lngOut(lngA) > lngOut(lngA + 1) Then
                            lngTemp = lngOut(lngA)
                            lngOut(lngA) = lngOut(lngA + 1)
                            lngOut(lngA + 1) = lngTemp
                            NoSwap = False
                        End If
                    Next lngA
                    lngLB = lngLB + 1
                End If
            Loop
            ShakerSort = lngOut
        Else
            ShakerSort = LongArray
        End If
    End If
End Function

---

Now it should replicate ShakerSortTwo more or less accurately.

Yep, perfect. Thanks for the help.