Quicksort
E100207
Quicksort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy and is widely employed in computer science and software systems.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Quicksort canonical | 3 |
| quick sort | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T846541 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Quicksort Context triple: [Tony Hoare, notableWork, Quicksort]
-
A.
B-tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
-
B.
Introduction to Algorithms
Introduction to Algorithms is a widely used, comprehensive textbook on algorithms and data structures, renowned for its rigorous yet accessible coverage of theoretical and practical topics in computer science.
-
C.
BST
BST (British Summer Time) is the daylight saving time observed in the United Kingdom, set one hour ahead of Coordinated Universal Time (UTC+1) during the summer months.
-
D.
Presto
Presto is a discontinued proprietary browser engine developed by Opera Software that powered older versions of the Opera web browser.
-
E.
Aitken
Aitken is a Scottish-origin surname notably borne by Max Aitken, 1st Baron Beaverbrook, a prominent Canadian-British newspaper magnate and politician.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Quicksort Target entity description: Quicksort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy and is widely employed in computer science and software systems.
-
A.
B-tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
-
B.
Introduction to Algorithms
Introduction to Algorithms is a widely used, comprehensive textbook on algorithms and data structures, renowned for its rigorous yet accessible coverage of theoretical and practical topics in computer science.
-
C.
BST
BST (British Summer Time) is the daylight saving time observed in the United Kingdom, set one hour ahead of Coordinated Universal Time (UTC+1) during the summer months.
-
D.
Presto
Presto is a discontinued proprietary browser engine developed by Opera Software that powered older versions of the Opera web browser.
-
E.
Aitken
Aitken is a Scottish-origin surname notably borne by Max Aitken, 1st Baron Beaverbrook, a prominent Canadian-British newspaper magnate and politician.
- F. None of above. chosen
Statements (51)
| Predicate | Object |
|---|---|
| instanceOf |
comparison-based algorithm
ⓘ
divide-and-conquer algorithm ⓘ sorting algorithm ⓘ |
| advantage |
efficient for large datasets
ⓘ
good cache performance ⓘ low constant factors ⓘ |
| alsoKnownAs |
quick sort
ⓘ
linked to:
Quicksort
|
| belongsToClass | comparison sort ⓘ |
| canBeImplementedIteratively | true ⓘ |
| canBeRandomized | true ⓘ |
| category | algorithm ⓘ |
| comparedWith |
Heapsort
ⓘ
Insertion sort ⓘ Merge sort ⓘ |
| creator | Tony Hoare ⓘ |
| disadvantage |
not stable by default
ⓘ
performance depends on pivot selection ⓘ worst-case quadratic time ⓘ |
| field | computer science ⓘ |
| goal | order elements according to a total order ⓘ |
| inputType |
array
ⓘ
list ⓘ sequence of comparable elements ⓘ |
| isInPlace | true ⓘ |
| isStable | false ⓘ |
| keyIdea |
partition array around a pivot element
ⓘ
recursively sort subarrays ⓘ |
| notableProperty | expected O(n log n) performance with random pivots ⓘ |
| optimization | switch to insertion sort for small subarrays ⓘ |
| output | sorted sequence ⓘ |
| partitionScheme |
Hoare partition scheme
ⓘ
Lomuto partition scheme ⓘ |
| primaryOperation | comparison ⓘ |
| spaceComplexityAverageCase | O(log n) ⓘ |
| spaceComplexityWorstCase | O(n) ⓘ |
| strategy | divide and conquer ⓘ |
| timeComplexityAverageCase | O(n log n) ⓘ |
| timeComplexityBestCase | O(n log n) ⓘ |
| timeComplexityWorstCase | O(n^2) ⓘ |
| typicalPivotChoices |
first element
ⓘ
last element ⓘ median-of-three ⓘ random element ⓘ |
| usedIn |
general-purpose sorting
ⓘ
standard library implementations of sort in many languages ⓘ systems programming ⓘ |
| usesRecursion | true ⓘ |
| worstCaseOccursWhen |
array is already sorted with poor pivot choice
ⓘ
array is reverse sorted with poor pivot choice ⓘ |
| yearProposed | 1959 ⓘ |
| yearPublished | 1961 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Quicksort Description of subject: Quicksort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy and is widely employed in computer science and software systems.
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Quicksort