Why is quicksort better than mergesort?

Subject: Why is quicksort better than mergesort?
Author: Alex_Raj
In response to: Why do I care about algorithm efficiency?
Posted on: 12/28/2013 01:52:41 AM

Two major reasons:

The real-world data most likely has some partial data sorted in nature. Quicksort's inner loop can significantly benefit from this by skipping swaps for those data.

Quicksort is an in-place sort which uses less storage and hence less disk/memory hits.

>
> On 12/19/2013 01:19:16 AM Alex_Raj wrote:

With computer power being doubled every 18 months as Moore's Law states, why do I care about algorithm efficiency as long as the algorithm is accurate?

Waaa, well let's look at the following real testing benchmark run on Intel Core-i7 2.8GHz
Table 1. Typical Algorithm Performance Benchmark (in second) ----------------+--------------+--------------+-----------+-----------+----------+------------+------------+--------------------- Size of problem | BinarySearch | LinearSearch | QuickSort | MergeSort | HeapSort | InsertSort | BubbleSort | Hanoi Tower (n) | O(logn) | O(n) | O(nlogn) | O(nlogn) | O(nlogn) | O(n^2) | O(n^2) | O(2^n) ----------------+--------------+--------------+-----------+-----------+----------+------------+------------+--------------------- 10 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 0.001 / 0.5 hour* 20 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 0.076 / 12 days* 32 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 175.171 / 136 years* ----------------+--------------+--------------+-----------+-----------+----------+------------+------------+--------------------- 1,000 | ~0 | 0.000 | 0.000 | 0.001 | 0.001 | 0.007 | 0.008 | 10,000 | ~0 | 0.000 | 0.015 | 0.003 | 0.008 | 0.022 | 0.166 | 100,000 | ~0 | 0.000 | 0.023 | 0.034 | 0.024 | 1.505 | 16.119 | 1,000,000 | ~0 | 0.001 | 0.151 | 0.202 | 0.214 | 151.941 | 1,598.389 | ----------------+--------------+--------------+-----------+-----------+----------+------------+------------+--------------------- 10,000,000 | 0.000 | 0.005 | 1.543 | 2.012 | 3.123 |17,736.500 | | 100,000,000 | 0.000 | 0.042 | 17.382 | 22.152 | 46.136 | | | 1,000,000,000 | 0.000 | 0.372 | | | | | | ----------------+--------------+--------------+-----------+-----------+----------+------------+------------+--------------------- * Note: If it were done by human with moving speed of 1 disk per second.

Observations:

For simple (O(n)) tasks like searching one item from a list, you may not care about which algorithm to choose with a powerful computer.

For decent (O(n^2)) tasks like sorting a list, you got to be very careful about which algorithm to choose if your size of problem (n) is greater than 1 million. As you can see from Table 1, QuickSort takes 0.151 second to finish your job whereas BubbleSort can easily bring your computer to its knees.

For complex (O(2^n)) tasks like moving Hanoi Tower, you really have to ask yourself the same question again: Why do I care about algorithm efficiency? The algorithm provided here took a 2.8GHz computer 175 seconds just to move 32 disks!

References:

Next Post: Why is mergesort better than quicksort? Alex_Raj 12/28/2013 01:57:26 AM
Previous Post: Why do I care about algorithm efficiency? Alex_Raj 12/19/2013 01:19:16 AM
Next Topic: Typical Algorithms Alex_Raj 12/24/2013 01:27:47 AM
Previous Topic: Big O Notation Alex_Raj 12/14/2013 09:28:33 PM
Index: by Date
Index: by Topic