 |
Business | Industries | Finance | Tax |
| Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|||||
| First Prev [ 1 2 3 4 ] Next Last |
Quicksort's inner loop is such that it is usually easy to implement very efficiently on most computer architectures, which makes it significantly faster in practice than other Θ(n log n) algorithms that can sort in place or nearly so in the average case (recursively-implemented quicksort is not, as is sometimes regarded, an in-place algorithm, requiring Θ(log n) on average, and Θ(n) in the worst case, of stack space for recursion.)
Because of its good average performance and simple implementation, Quicksort is one of the most popular sorting algorithms in use. It is an unstable sort in that it doesn't preserve any ordering that is already between elements of the same value. Quicksort's worst-case performance is Θ(n2); much worse than some other sorting algorithms such as heapsort or merge sort. However, if pivots are chosen randomly, most bad choices of pivots are unlikely; the worst-case has only probability 1/n ! of occurring.
The Quicksort algorithm uses a recursive divide and conquer strategy to sort a list. The steps are:
In pseudocode, the complete algorithm in its simplest form is:
The following is wikicode , a proposed pseudocode for use in many articles:
function partition(a, left, right, pivotIndex) pivotValue := a[pivotIndex] swap(a[pivotIndex], a[right]) // Move pivot to end storeIndex := left for i from left to right-1 if a[i] <= pivotValue swap(a[storeIndex], a[i]) storeIndex := storeIndex + 1 swap(a[right], a[storeIndex]) // Move pivot to its final place return storeIndex function quicksort(a, left, right) if right > left select a pivot value a[pivotIndex] pivotNewIndex := partition(a, left, right, pivotIndex) quicksort(a, left, pivotNewIndex-1) quicksort(a, pivotNewIndex+1, right)The inner loop which performs the partition is amenable to optimization, for two main reasons:
This is one reason why Quicksort is often the fastest sorting algorithm, at least on average over all inputs.
The most crucial problem of Quicksort is the choice of pivot element. A naļve implementation of Quicksort, like the ones below, will be terribly inefficient for certain inputs. For example, if the pivot always turns out to be the smallest element in the list, then Quicksort degenerates to Selection sort with Θ(n2) running time. A secondary problem is the recursion depth. This becomes linear, and the stack requires Θ(n) extra space.
Note that the partition procedure only requires the ability to traverse the list sequentially; therefore, quicksort is not confined to operating on arrays (it can be used, for example, on linked lists). Choosing a good pivot, however, benefits from random accessIn computer science, random access is the ability to access a random element of a group in equal time. The opposite is sequential access, where a remote element takes longer time to access. A typical illustration of this distinction is the ancient scroll, as we will see.
The worst-case behavior of quicksort is not merely a theoretical problem. When quicksort is used in web services, for example, it is possible for an attacker to deliberately exploit the worst case performance and choose data which will cause a slow running time or maximize the chance of running out of stack space. See competitive analysisCompetitive analysis shows how on-line algorithms perform and demonstrates the power of randomization in algorithms. For many algorithms, the performance is not dependent on the values of the data, only the amount. An example of one that is data dependent for more discussion of this issue.
Sorted or partially sorted data is quite common in practice and the naļve implementation which selects the first element as the pivot does poorly with such data. To avoid this problem the middle element can be used. This works well in practice but attacks can cause worst-case performance.
A better optimization can be to select the median element of the first, middle and last elements as the pivot. Adding two randomly selected elements resists chosen data attacks, more so if a cryptographically sound random number generator is used to reduce the chance of an attacker predicting the "random" elements. The use of the fixed elements reduces the chance of bad luck causing a poor pivot selection for partially sorted data when not under attack. These steps increase overhead, so it may be worth skipping them once the partitions grow small and the penalty for poor pivot selection drops.
Finding the true median value and using it as the pivot can be done if the number of elements is large enough to make it necessary but this is seldom done in practice.
| Politics | Business | Finance |
 |
 |
 |
|