yeah I meant log base 2, I was kind of out of it when I posted

Reply

Quicksort is average O(log N) time, but at worst O(N^2) if the data is annoyingly constructed. There are algorithms that run in more consistent log time (e.g. mergesort, heapsort) but there algorithms are much simpler. Well definately in the second case. In the former case (in Haskell notation which is so beautiful I AM introducing these forums to the lovely world of FP):

Merge (x:xs) (y:ys) = if (x < y) then x:Merge(xs, y:ys) else
Merge [] ys = ys
Merge xs [] = xs

MergeSort xs = Merge (Mergesort ys) (MergeSort zs)
where ys = odds xs
zs = evens xs

odds (x:y:xs) = x:odds(xs)
odds [x] = x
odds [] = []

evens (x:y:xs) = y:evens(ys)
evens [y] = []
evens [] = []

Where here x:xs represents x at the front of a list of xs, [] the empty list and [] the singleton list.

(In other words - to sort a list [3,2,4,1] we split into odds and evens - [3,4] and [2,1], then sort these recursively into [3,4] and [1,2] and then Merge them together into [1,2,3,4]. Merge takes to (ordered) lists and produces an (ordered) list by looking at the first element of both (see above.))

 

 

 

Reply

i think that in most cases the best choice is to use common library algorithms, like C++ quicksort. it's a very smart modification of insertion sort (much better than bubble sort, because it leaves the same element's in order they were in the beginning) and original quicksort. takes one line to write it.

if you don't want to use libraries, you can easily write insertion sort. works pretty fast with lists up to 50 elements (if larger think about QS).

if sorting integers from a certain range you can use algorithm that would work in O(n) (easy to guess how it works, i hope )

if you're just interested in theoretical algorythmic aspect of how fast can i sort a list of X elements (where X is constant), than it's quite easy to think out how can you do it with list of up to 6 elements. for a list of 24 elements it took 3 weeks to compute the result with 3 PCs (pentium III 1GHz).

regards

Reply

Many programmers consider the quicksort to be the fastest sorting algorithm available.

Technically its not.


There is a sort called the Merge Sort which takes a recursive means of sorting.

Let me give you a comparison. I hope you understand Big O notation, its pretty easy.




Bubble Sort:

• Data are in completely random order: O(n^2)
• Data are ordereed from lowest to highest: O(n)
• Data are ordered from highest to lowest: O(n^2)

Insertion Sort:

• Data are in completely random order: O(n log(n))
• Data are ordereed from lowest to highest: O(n)
• Data are ordered from highest to lowest: O(n log(n))

-I'm not 100% sure that these are the correct Big O runtimes for the Insertion sort.

Quick Sort:

• Data are in completely random order: O(n log(n) )
• Data are ordereed from lowest to highest: O(n^2)
• Data are ordered from highest to lowest: O(n^2)

Merge Sort:

• Data are in completely random order: O(n log(n) )
• Data are ordereed from lowest to highest: O(n log(n) )
• Data are ordered from highest to lowest: O(n log(n) )

As you can see, the Bubble sort is only good, when the list is already sorted. However your not going to sort an already sorted list.

The Quick sort is awesome when the list is random. However, if the list isn't completely random, and is only off by a few elements, it takes longer.

The Merge sort is consistent, providing O(n log(n) )


If you don't know, "n" is the number of elements in the list you are sorting.

People say the Quick Sort and Binary Search are related, because Binary Search uses the same technique and a Binary Search also has O(n log(n) ).

I have no code on the merge sort in any language I just know its there. One of the reasons that the Merge Sort proves to be more effective then the Quick Sort is that the Quick Sort is implemented in such a way to save Memory. The Merge Sort uses a recursive method and therefore, uses a ton of memory.

The Insertion sort looks better then the Merge sort, but I'm not 100% sure that I have the correct Big O runtimes for the insertion sort.

Anyways, I just posted this because I wanted to share information that I had.

Reply

qsort or quicksort is already implemented in many languages or their add-on libraries (e.g. C++ STL, Java, Python, Ruby) there is seldom a need to write your own sort method these days unless it is just as a learning exercise.

Note that many of these libraries come with source code if you want to look at how they are done.

Reply