Fastest Sorting Algorythm

[Koen]

I'm looking for a fast sorting algorythm to alphabetically sort a list from A to Z.

Dim Title() as String, NumOfTitles as Long
Dim Temp as String
Dim I as Long, J as Long


This algorythm I always use is too slow, can anyone write a better (optimized) algorythm?

For I = 1 To NumOfTitles
*For J = 1 To NumOfTitles
* *If LCase(Title(I)) < LCase(Title(J)) Then
* * *Temp = Title(I)
* * *Title(I) = Title(J)
* * *Title(J) = Temp
* *End If
*Next J
Next I


BTW, is there a function left like the old QB's Swap(String1, String2)?

[NrmMyth]

Did you try "Quick Sort"

[Pangloth]

Koen, look at your code. You have an outer loop on I and an inner loop on J, both of which run from 1 to the size of your input. Then you have a compare and 3 assignments. These don't matter, but the two nested loops give your code a time complexity of O(n^2), which means that for any input, your algorithm will take the quadratic of the input to complete. This is very bad, save for the smallest of inputs.

You might want to consider implementing Quicksort, which has an average case of O(n log(n)), and a worst case of O(n^2), but this can be made exponentially unlikely with a well chosen pivoting strategy.

You should consult a good book on algorithms and data structures. If your inputs will never be too big, you might also consider Shellsort or Mergesort.

I hope this helps.

EDIT: Recursive algorithms are not very efficient for small datasets due to the cost of recursion, so you might want to switch to a nonrecursive strategy to sort the last 20 - 30 elements in your set.

[Kon-Tiki]

Sorting algorithms (http://linux.wku.edu/~lamonml/algor/sort/sort.html). There's Quick Sort in there, with a full explanation and example sourcecode. Besides the Quick Sort algorithm, there're all the others, too.

[Pangloth]

Kon-Tiki, the example Quicksort source code you link to uses the leftmost element as the pivot, which could lead to disastrous results.

Imagine feeding sorted input to the algorithm. Then, because of the partitioning strategy, all elements will end up in the same half of the array. Worse, this happens consistently through the recursion, so the algorithm will take quadratic time to do nothing at all! Furthermore, input with largely sorted parts can be quite frequent in real life. This implementation is not recommended.

Median-of-three partitioning should be used instead.

That's why not having some understanding of what's going on can actually harm you.

[NrmMyth]

WOW............................................... .................yes.............................. :blink:
Admit Koen that you wasn't expecting this.

[taikara]

I am such a geek.

Once, in university, I was working on coding some stupid exercise or another, and my friend was sitting next to me, working on coding a graph that visually displayed the various sorting algorithm efficiencies...

He turned to me and said, "Something's just not right. What do you think?"

I looked at the screen, and the graph was most definitely not displaying correctly. Lines were going out of the margins, were not behaving according to the actual algorithms, etc.

I turned to my friend with a straight face and said:

"Well... it's a graph... of sorts..."

(If you get this, and laugh, you deserve to be locked up just as much as I do.) :D

Edit: Sorry about the :ot: ness... it's been one of those nights, and I couldn't resist :(

[Koen]

Originally posted by Kon-Tiki@Mar 12 2005, 09:29 PM
Sorting algorithms (http://linux.wku.edu/~lamonml/algor/sort/sort.html). There's Quick Sort in there, with a full explanation and example sourcecode. Besides the Quick Sort algorithm, there're all the others, too.
The link doesn't work. :tomato:

I'm using it for my random mp3 player to sort all files alphabetically. This can be on title, artist, album, key or bpm. The mp3 player was loading a bit slow, and in fact the only reason was that it was sorting all files, and I didn't expect that to work so slow...

Thanks for the reactions :ok: , I'll look for quicksort and see how well that's performing.

EDIT.
Found and example in VB, and for those who want to know it too:
http://www.vba-programmer.com/Word_Code/Qu...e_Dimension.txt (http://www.vba-programmer.com/Word_Code/QuickSort_Single_Dimension.txt)

[Kon-Tiki]

It's strange that that link doesn't work. Just tested it again, and it does work here.

[NrmMyth]

Works for me to.

I could save the page so you could download it if you still can't open the link. :ok: