Quicksort Algorithm
Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.
| |
| Class | Sorting algorithm |
|---|---|
| Worst-case performance | O(n2) |
| Best-case performance | O(n log n) (simple partition) or O(n) (three-way partition and equal keys) |
| Average performance | O(n log n) |
| Worst-case space complexity | O(n) auxiliary (naive) O(log n) auxiliary (Hoare 1962) |
| Optimal | No |
{{Infobox algorithm
|name = <!-- Defaults to article name -->
|class = <!-- Name of problem it solves -->
|image = <!-- filename only, no "File:" or "Image:" prefix, and no enclosing [[brackets]] -->
|caption =
|data =
|time = <!-- Worst time big-O notation -->
|best-time =
|average-time =
|space = <!-- Worst-case space complexity; auxiliary space
(excluding input) if not specified -->
}}
Infobox describing an algorithm
| Parameter | Description | Type | Status | |
|---|---|---|---|---|
| Name | name | Name of algorithm
| Content | required |
| Problem class | class | Type of problem it solves
| Content | required |
| Image | image | filename only, no 'File:' or 'Image:' prefix, and no enclosing [[brackets]] | Content | optional |
| Image size | size image size imagesize image_size | no description | Unknown | optional |
| Alt text | alt | Alt text for image | String | optional |
| Caption | caption | no description | Content | optional |
| Data structure | data | Data structure operated upon
| Content | required |
| Worst-case time complexity | time | Worst-case time complexity in big O notation
| Content | required |
| Best-case time complexity | best-time | no description | Content | optional |
| Average time complexity | average-time | no description | Content | optional |
| Worst-case space complexity | space | If not specified, this should be auxiliary space complexity and not include the space needed for the input
| Content | required |
