CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: What algorithm is faster than Quick Sort?

1. Member
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?

Thanks

2. ## 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.

3. Member
Join Date
May 2004
Posts
123

## Re: What algorithm is faster than Quick Sort?

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

## 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.

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. Senior Member
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.

6. ## Re: What algorithm is faster than Quick Sort?

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...

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

## Re: What algorithm is faster than Quick Sort?

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.

8. Senior Member
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).

#### Posting Permissions

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