Efficient yet simple sorting algorithms

[Sir Fredrick]

Yeah, there is certainly more to efficiency than reduced levels of recursion. My sorting algorithm is slightly less complex than the merge sort example I saw, so when working with small sets of data, my sort may be more efficient even if goes a few levels deeper. I also avoided wasting lots of memory by passing my vectors by reference with the start and end positions, rather than making two smaller vectors for the left and the right and passing those.

I could cut a few levels of recursion by adding in a test to see if it's already sorted (so it wouldn't go ALL the way down - if everything was sorted at the 60th recursive call, it would terminate, instead of at the 66th)...the problem with that is then I am performing an extra 60 operations each time, so in this case it would only pay off if my function had more than 10 comparisons in it already.

What is the O() all about anyway? (sorry, like I said, never took analysis of algorithms). n is the number of elements that must be sorted right? log n seems way too small then.

Interesting stuff, anyway.

 

[charrison]

The BIG O refers to run time complexity(time) of a given algorythm.

 

[IcemanJer]

<< The BIG O refers to run time complexity(time) of a given algorythm. >>

more specifically, Big-O is the UPPER LIMIT of the rum time complexity. Big-Theta is THE run time complexity since it factors in both the upper bound and lower bound.

 

[CSoup]

<<
What is the O() all about anyway? (sorry, like I said, never took analysis of algorithms). n is the number of elements that must be sorted right? log n seems way too small then.
>>



yes, n is generally the problem size which in this case is the number of elements. O(n log n) is the best that a classical sorting algorithm can do. You might want to try removing the median finding code in algorithm and try one fo the methods I mentioned earlier. You will likely get better performance on average. Basically, in a quicksort, each level you do about O(n) amount of work. This is why you want to minimize the number of levels of recursion (not number). In a worst case quicksort you split always with 1 element followed by the rest. This leads to a recursion tree of depth n which gives the worst case running time of O(n^2). If you split evenly then you have log n levels and thus O(n log n) running time.

Big-O notation is a formal way to specify the time complexity of an algorithm. Simple way to look at it is that it gives the upper bound complexity, so something in O(n) is also in O(n^2), but O(n) is a better indicator. Theta notation gives tight bounds and Sigma notation gives lower bounds. All of these come in little and big versions also.

 

[Bluga]

BST.

 

[CSoup]

Also, if you are going to do timing, you need to have at least 10-100 million elements to get significant times. Any sorting algorithm should be able to sort 64 elements in no time at all (except maybe random sort).

 

[darkshadow1]

A randomized quicksort should give you the best average time (still n lg n but better than a regular quicksort)

If you have any other information / assumptions then you could do others like selection or radix...

 

[Sir Fredrick]

<< Also, if you are going to do timing, you need to have at least 10-100 million elements to get significant times. Any sorting algorithm should be able to sort 64 elements in no time at all (except maybe random sort). >>



That's why I'm not really going to bother optimizing my algorithm further, I'm just interested in refreshing my memory on what's out there