How to Sort 2 Dimensional Array with 5 Columns

[mhnvb]

I see a lot of sort examples that sort a 1 dimensional array , or 2 dimensional array with 2 columns.
Having trouble modifying the latter for my 5 column array.

Does anybody has a sort function for a 5 column array sort on the first column?

EG:
change this:
"def", "ken", "Dave","Bottles","Ink"
"zrr","bolt","Paper","red","grass"
"abc", "School","Tires","Wheat","Water"-
"ehg","Meat","laws","Phd","Ice"

To This:
"abc", "School","Tires","Wheat","Water"
"def", "ken", "Dave","Bottles","Ink"
"ehg","Meat","laws","Phd","Ice"
"zrr","bolt","Paper","red","grass"

Thanks for your help

[Max187Boucher]

If your only sorting the first column what's wrong with the examples you found that can sort 1 dimension array?

[Jonney]

I see a lot of sort examples that sort a 1 dimensional array , or 2 dimensional array with 2 columns.
Having trouble modifying the latter for my 5 column array.

Does anybody has a sort function for a 5 column array sort on the first column?

EG:
change this:
"def", "ken", "Dave","Bottles","Ink"
"zrr","bolt","Paper","red","grass"
"abc", "School","Tires","Wheat","Water"-
"ehg","Meat","laws","Phd","Ice"

To This:
"abc", "School","Tires","Wheat","Water"
"def", "ken", "Dave","Bottles","Ink"
"ehg","Meat","laws","Phd","Ice"
"zrr","bolt","Paper","red","grass"

Thanks for your help

Use QuickSort:
http://www.vbforums.com/showthread.p...=1#post4739885

1. replace the list(i) array to your array e.g. Cells(i,0), 0 is the first column "def" "zrr","abc","ehg"
2. List(hi) = med_value -->Cells(hi, 0) = med_value
3. List(lo) = List(hi)

For j = 0 To UBound(Cells, 1)
swapAny Cells(lo, j), Cells(hi, j)
Next j
4. swapAny can be string type or datatime or number,boolean ...
Private Sub swapAny(a, b)

Dim ltemp As Variant

ltemp = a
a = b
b = ltemp

End Sub

[Phill.W]

Sorting single elements? That's "bread and butter" programming.
Sorting pairs of elements? Now you're starting to make things fiddly; which column is which, again?
Sorting lists of elements? IMHO, that's the time to reach for Types or, better still, Classes.

I'm pretty much a Class-convert now (I started off with Types, but got fed up with their limitations).
The big advantages are that
(a) your fields are named, not indexed, and those names are fixed until you re-code the Class.
(b) an array of objects (class instances) is only one-dimensional, no matter how many fields the class has; sorting is "easy" again.

OK, you need to add a few Set keywords around the place because you're working with objects (not their "default properties") but, IMHO, the extra mileage is well worth it.

[Elroy]

Yeah, it appears you're just sorting on the first element, and just wanting to move all the elements based on that first element sort. A couple of things come to mind for me. One, during your sort, just be sure to move all the second dimension elements. And two, doing that "move" part would be easier if you created a nested UDT rather than a 2D array. I'll just do both (and I'll assume arrays dimensioned from 1 (not 0)).

Dim sData(1 to 4, 1 to 5) as string

... initialize data here.  I'll let you do that.

Dim i as long
Dim j as long
Dim k as long
Dim s as string

For i = 1 to 3
    For j = i+1 to 4
        If sData(i,0) > sData(j,0) Then
            For k = 1 to 5
                s = sData(i,k)
                sData(i,k) = sData(j,k)
                sData(j,k) = s
            Next k
        End If
    Next j
Next i

Now, just to eliminate that inner "k" loop, you could do something like:

Type MyUdt
    SortKey As String
    OtherData(2 to 5) As String
End Type

' And then in some procedure.

Dim uData(1 to 4) as MyUdt

' And then:

Dim i as long
Dim j as long
Dim k as long
Dim u as MyUdt

For i = 1 to 3
    For j = i+1 to 4
        If uData(i).SortKey > uData(j).SortKey Then
            u = sData(i)
            uData(i) = uData(j)
            uData(j) = u
        End If
    Next j
Next i

I think I got all that right. I'll let others ding me if I didn't.

EDIT: Also, just as an FYI, I'd learn to use Ubound() rather than hard coding the upper bounds, but I just hammered that out here in the forum window.

[dilettante]

Quicksort seems to have a lot of fans, but it contains the hidden time bomb that in some cases it can run for absurdly long times. That's the main reason it is never used in production software.

Heapsort is far more reliable, only slightly slower in the special cases where Quicksort does any better, and can also be written to be GUI-thread friendly: no message loop starvation causing your program to be marked unresponsive by Windows.


Don't dismiss two other options that can be very powerful: store your data as a Variant array of arrays, store your data in a fabricated ADO Recordset. The former can gain speed by pointer swapping, the latter has a sort built in.

[Elroy]

*laughs and nods*

I absolutely knew that someone would ding me for my simplistic approach to sorting. And I've totally got faster sort routines, if I don't just cheat and throw it all into a listbox and let it do it.

I do find that the above is often very intuitive and easy to understand for beginners. Every element is compared to every other element, just making sure that the lower one is below the higher one. Can't be more intuitive than that. And yes, I suspect you can develop an entire series of courses on optimal sorting and (related) index storing techniques.

But if we're just sorting, say, less than a couple hundred items, I do enjoy the intuitiveness of the above.

Elroy

[georgekar]

http://www.vbforums.com/showthread.p...=1#post4740329

As I state to the thread above, the quick sort from CVMichalel is fault. Can work but not always..I prove it, in 18 post. In post #15 I have an implementation of "the median of three technique".

[Jonney]

Quicksort seems to have a lot of fans, but it contains the hidden time bomb that in some cases it can run for absurdly long times. That's the main reason it is never used in production software.

Heapsort is far more reliable, only slightly slower in the special cases where Quicksort does any better, and can also be written to be GUI-thread friendly: no message loop starvation causing your program to be marked unresponsive by Windows.


Don't dismiss two other options that can be very powerful: store your data as a Variant array of arrays, store your data in a fabricated ADO Recordset. The former can gain speed by pointer swapping, the latter has a sort built in.

Sir, Can you please give details on the particular issues on quicksort? Any evidence or example? Why you said Heapsort is better?

[georgekar]

Time to complete a sorting is n*n max, in quick sort, and n * log(n) for heapsort. So quick sort is quick but not always. Maybe a run first to compare and swap if needed, make the list more prepeared for quick sort.

[dilettante]

There are "worst case" orders that can cause Quicksort to take a very, very long time if there is a lot to sort. Heapsort has a reliable upper limit on the time required to sort any set of data.

As they say here:

Sorting Algorithms: QuickSort

Worst-case running time O(N²)

Never use in applications which require guaranteed response time:

* Life-critical (medical monitoring, life support in aircraft and space craft)

* Mission-critical (monitoring and control in industrial and research plants handling dangerous materials, control for aircraft, defense, etc) unless you assume the worst-case response time.

This is a well known deathtrap in Quicksort. With superior alternatives available why ever use Quicksort?

Compare with Sorting Algorithms: Heapsort

Sorts in O(NlogN) time

[Schmidt]

There are "worst case" orders that can cause Quicksort to take a very, very long time if there is a lot to sort. Heapsort has a reliable upper limit on the time required to sort any set of data.

Also Quicksorts have a reliable Upperlimit: O(N²) - in the naive Versions ... (as you already noted)

The problem with the "O-Notation" is, that you cannot directly translate it to runtimes or processor-cycles.
Quicksort (when doing those N² "Steps" in the worstcase) it does them really fast - Quicksort is the
love-child of CPU-Caches.

You need really, really "Large N" (in the Giga, not the Mega-Range), to encounter real disadvantages from naive Quicksorts O(N²) worstcase.
And when you have such huge Data you have to perform sorts on, then there's usually very specific Algorithms at play
(since such huge Data-Volumes usually don't fit into memory anymore)... see:
http://en.wikipedia.org/wiki/External_sorting

As they say here:

Sorting Algorithms: QuickSort

Worst-case running time O(N²)

Never use in applications which require guaranteed response time:

* Life-critical (medical monitoring, life support in aircraft and space craft)

* Mission-critical (monitoring and control in industrial and research plants handling dangerous materials, control for aircraft, defense, etc) unless you assume the worst-case response time.

In my tests, a naive Quicksort (when performing on an array of constant values) is still faster than
performing the sort on random-data in an array of the same size.

This is a well known deathtrap in Quicksort. With superior alternatives available why ever use Quicksort?

In all practical "InMemory-Tests" (which even try to force worst-cases) Quicksort is performing better than HeapSort
(aside from the constant-Data-case, in which - as said, Quicksort has still a better timing than on random-arrays).

Just uploaded an example for the "latest word in all things QuickSort" (the DualPivot-approach) into the Codebank:
http://www.vbforums.com/showthread.p...ivot-QuickSort

Here's a Screenshot:


Whilst the above Screenshot might be dismissed because the used N=2Mio as the ArraySize might be
"not large enough to see some negative effect" - here's the same algorithms at work with N=100Mio entries in the Sort-Arrays.


If anything, then it's the HeapSort-performance which gets worse with larger N.

Olaf

[dilettante]

Cache performance can indeed make a huge difference when sorting data well within the size of the processor cache. The memory required to sort a list of integers is quite a bit smaller than more useful scenarios such as sorting lists of multi-field records. And it is true that Quicksort has variations intended to overcome some of the naive algorithm's issue.

But to put the perfomance differences into perspective you ought to add the simple Bubblesort as a "control" or baseline. The best-case performance difference between Quicksort and Heapsort don't outweigh its potential hazards.

Comparing Quick and Heap Sorts reiterates the same well known flaw in Quicksort.

As they acknowledge there, a lot of Mort-written ("commercial" as in "work for hire") software will use Quicksort and feign innocence when the house of cards comes down, but serious software uses Heapsort for reliability.

[Elroy]

*laughs, shakes my head, and shouts out to moderator*

OMG, shut this thread down before they bring in fractals and/or chaos theory to optimize their sorts.

Poor mhnvb gave us a four line situation that he wanted sorted, and we're talking about the entire history of sorting algorithms. LMAO.

In my mind, optimal sorting has LONG been relegated to the bowels of more low level programming, and need not be a concern of RAD (end-user application) programmers.

But hey ho, if VB6 can do it, let's go for it. But wait, VB6 doesn't use CPU registers as efficiently as C and other lower level programs (or even assembler). So shouldn't we start talking about optimal use of CPU registers?

Y'all Take Care,
Elroy

[Schmidt]

In my mind, optimal sorting has LONG been relegated to the bowels of more low level programming, and need not be a concern of RAD (end-user application) programmers.

Since the vbRuntime does not offer built-in Sort-Methods (aside from the crude VB-ListBox-workaround) -
one either has to use external libraries - or implement a Sort-Algo in the VB-language itself.

So - since that is the situation, I don't really see why discussions about Sort-Algo-efficiency is misplaced -
or "not a concern for RAD-programmers".

But hey ho, if VB6 can do it, let's go for it. But wait, VB6 doesn't use CPU registers as efficiently as C and other lower level programs (or even assembler). So shouldn't we start talking about optimal use of CPU registers?

You seem not to be aware of the fact, that VB5/6-versions compile natively over a C-Compiler,
which ships with the product and ensures a compiled runtime-performance which is comparable
to the output of VC++6.

There's enough VB6-implemented routines out there, which outperform their counterparts
which were done in "native-C" (as one finds them in the vbRuntime or other MS-libs).

Olaf