![]() | This template uses Lua: |
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 |