Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 8 of 8
  1. #1
    New Coder
    Join Date
    Dec 2004
    Posts
    42
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question 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

  • #2
    Regular Coder
    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.

  • #3
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    Quote Originally Posted by aman
    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).

  • #4
    New Coder
    Join Date
    Dec 2004
    Posts
    42
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for info.

  • #5
    New Coder
    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

  • #6
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    Quote Originally Posted by JWizard
    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).

  • #7
    New Coder
    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 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'?

  • #8
    New Coder
    Join Date
    Jul 2004
    Location
    Azerbaijan
    Posts
    25
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Last edited by OkIDaN; 02-13-2005 at 06:30 AM.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •