pashah72

01-08-2005, 09:04 AM

Hello

I am new to Sorting Algorithms & I like to know more on this subject in simple format, step by step. I went to google & found various articles & sites on this but they were quite complex & not easy to understand. can you suggest something which is easy to understand, which is explained step by step.

Looking forward for an early reply.

Thanks

The simplest sorting method is the "Bubble Sort", google up a tutorial on it.

The simplest sorting method is the "Bubble Sort", google up a tutorial on it.

Also the worst. Selection and Insertion sorts are better algorithms to start from (and to use, even).

JWizard

02-09-2005, 03:36 AM

Algorithms are never easy to start learning. Sometimes it's easier to implement them than to analyze them. The two fastest sorting algorithms are merge sort and quick sort. They both are divide and conquer recursive algorithms in which one does the work, then the recursion, and the other does the recursion, then the work. Don't think about that too hard, it hurts.

You'll see when reading about algorithms that they have a running time associated with them...This just means that based on a input of size n, the algorithm will take T(n) steps to solve the problem (sorting n elements in this case). There's different notations about time complexities, but you'll learn them later I'm sure.

The two aforementioned algorithms run in Theta(nlogn), which cannot be beat, and it is in fact impossible to sort n elements without nlogn comparisons (I can prove it if you want using a comparison tree). A quadratic algorithm to sort n elements is inefficient and using more steps than it has to. This is why some algorithms are 'good' and some 'dirty'.

O.K...now repeat...bubble sort...dirty....quick sort...good

A quadratic algorithm to sort n elements is inefficient and using more steps than it has to. This is why some algorithms are 'good' and some 'dirty'.

O.K...now repeat...bubble sort...dirty....quick sort...good

Careful with what you say. It is well known that Quicksort is slower than some O(n^2) sorts (such as Insertion sort) for "small" lists (due to the asymptotically negligable terms and the coefficients that are ignored in Big-Oh).

JWizard

02-09-2005, 10:13 PM

Not by picking a deterministic pivot. In the case of a randomly chosen pivot, sure.

An upper bound on quick sort 'standard' algorithm (choosing the last element as a pseudo-random pivot), is in fact quadratic. Quick sort can be, and is, most of the time corrected by this choice in pivot (I'm sure your familiar with deterministic pivots in divide and conquer algorithms) For the sake of the lad asking about sorting algorithms, the two I mentioned are the best, and sorting n elements has a lower bound of Big-Omega(nlogn). If you know otherwise, please let me know.

We can argue about constant factors, their sizes, and worst case situations, small values of n, and other things, but the fact of the matter is that analysis is worthless for small values of n anyways. We are looking for an asymptotic function by which to bound a running time, not how fast an algorithm is for n=1,2,3,4, or some small value.

By the way, if I told you that the tallest person in the world was 10 feet tall, would you declare people as '10 foot creatues'?

OkIDaN

02-09-2005, 10:14 PM

Visit these links:

http://linux.wku.edu/~lamonml/algor/sort/sort.html

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Additionally this may be of help to you:

http://okidan.binaryshadow.org/sortdiff.jpg

which is based on this:

http://okidan.binaryshadow.org/sort.txt