Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 8 of 8

01082005, 09:04 AM #1
 Join Date
 Dec 2004
 Posts
 42
 Thanks
 0
 Thanked 0 Times in 0 Posts
don't know about Sorting Algorithms?
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
01082005, 07:26 PM
#2
 Join Date
 Oct 2004
 Posts
 230
 Thanks
 0
 Thanked 0 Times in 0 Posts
The simplest sorting method is the "Bubble Sort", google up a tutorial on it.
01082005, 08:26 PM
#3
Also the worst. Selection and Insertion sorts are better algorithms to start from (and to use, even).Originally Posted by aman
01102005, 07:46 AM
#4
 Join Date
 Dec 2004
 Posts
 42
 Thanks
 0
 Thanked 0 Times in 0 Posts
Thanks for info.
02092005, 03:36 AM
#5
 Join Date
 Feb 2005
 Posts
 27
 Thanks
 0
 Thanked 0 Times in 0 Posts
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
02092005, 08:55 AM
#6
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 BigOh).Originally Posted by JWizard
02092005, 10:13 PM
#7
 Join Date
 Feb 2005
 Posts
 27
 Thanks
 0
 Thanked 0 Times in 0 Posts
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 pseudorandom 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 BigOmega(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'?
02092005, 10:14 PM
#8
 Join Date
 Jul 2004
 Location
 Azerbaijan
 Posts
 25
 Thanks
 0
 Thanked 0 Times in 0 Posts
Visit these links:
http://linux.wku.edu/~lamonml/algor/sort/sort.html
http://www.cs.ubc.ca/spider/harrison...tingdemo.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
Last edited by OkIDaN; 02132005 at 07:30 AM.