What algorithm is faster than Quick Sort?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: What algorithm is faster than Quick Sort?

  1. #1
    Join Date
    May 2004
    Posts
    123

    What algorithm is faster than Quick Sort?

    Gurus,

    Are there any algorithms out there that are faster than quick sort?

    If so what are they and where can I find more information about them?

    Thanks

  2. #2
    Join Date
    Dec 2001
    Location
    Greece, Athens
    Posts
    1,015

    Re: What algorithm is faster than Quick Sort?

    Hi engineer2004.
    Quicksort is mostly used in programming because it has the best order. Though, there are some algorithms that have a better worst case complexity. Here is a table:
    Code:
                        Order      WorstCase
    Merge Sort        Nlog(N)   Nlog(N)
    Quick Sort         Nlog(N)    N^2
    Heap Sort         Nlog(N)    Nlog(N)
    Selection Sort   N^2         N^2
    Of course, the worst case complexity (N^2) is rarely achieved for the quick sort algorithm. Another thing is that Merge sort is easier to implement than the quicksort algorithm, but it uses more memory.
    Generally, there are no other faster algorithms than Nlog(N) order. This is for numbers (and strings of course). There are some other algorithms which are ONLY for string sorting which are N-order (they are called Radix - Sort, or sth like that). Generally, search the net for all these algorithms and you'll find much...
    Last edited by yiannakop; September 10th, 2004 at 05:12 AM.
    Theodore
    Personal Web Page (some audio segmentation tools): www.di.uoa.gr/~tyiannak

  3. #3
    Join Date
    May 2004
    Posts
    123

    Re: What algorithm is faster than Quick Sort?

    Thanks! Appreciate the answer!

  4. #4
    Join Date
    Jul 2003
    Location
    Seoul, Korea(South)
    Posts
    16

    Red face Re: What algorithm is faster than Quick Sort?

    Hello, I am curious.

    Do the three sorting algorithms have same performance? the orders are appeared same, in contrast to your explanation.


    Quote Originally Posted by yiannakop
    Hi engineer2004.
    Quicksort is mostly used in programming because it has the best order. Though, there are some algorithms that have a better worst case complexity. Here is a table:
    Code:
                        Order      WorstCase
    Merge Sort        Nlog(N)   Nlog(N)
    Quick Sort         Nlog(N)    N^2
    Heap Sort         Nlog(N)    Nlog(N)
    Selection Sort   N^2         N^2
    Of course, the worst case complexity (N^2) is rarely achieved for the quick sort algorithm. Another thing is that Merge sort is easier to implement than the quicksort algorithm, but it uses more memory.
    Generally, there are no other faster algorithms than Nlog(N) order. This is for numbers (and strings of course). There are some other algorithms which are ONLY for string sorting which are N-order (they are called Radix - Sort, or sth like that). Generally, search the net for all these algorithms and you'll find much...

  5. #5
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245

    Re: What algorithm is faster than Quick Sort?

    Radix sort can have better performance for both typical and worst case scenarios. But as with merge sort it requires more memory. It also requires that things be able to be classified in a certain way. Generally, radix sort only works well for integers and strings.
    Kevin Hall

  6. #6
    Join Date
    Dec 2001
    Location
    Greece, Athens
    Posts
    1,015

    Re: What algorithm is faster than Quick Sort?

    Quote Originally Posted by Shanin
    Hello, I am curious.

    Do the three sorting algorithms have same performance? the orders are appeared same, in contrast to your explanation.
    What I said is that the 3 first algorithms have the same order, but different worst-case complexities. I also mentioned some differences in implementation. I don't see where did I not follow the table...
    Theodore
    Personal Web Page (some audio segmentation tools): www.di.uoa.gr/~tyiannak

  7. #7
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245

    Re: What algorithm is faster than Quick Sort?

    Quote Originally Posted by Shanin
    Hello, I am curious.
    Do the three sorting algorithms have same performance?
    Just because two algorithms have the same complexity doesn't mean they are just as efficient or just as fast. It basically tells you how the algorithm performance worsens as the data set grows.

    Assume one algorthm always takes exactly 10 times as long as another algorithm to execute. Well both algorithms would hve the same complexity. Complexity is therefore not a good measure of relative performance.

    For more information on complexity and "big O notation" look here.
    Kevin Hall

  8. #8
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245

    Re: What algorithm is faster than Quick Sort?

    Oh and for the record, radix sort has a typical complexity of O(n).
    Kevin Hall

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center