Lesson plan
Comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data; that is: # if a ≤ b and b ≤ c then a ≤ c (transitivity) # for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a with a ≠ b; in this case either may come first in the sorted list. In a stable sort, the input order determines the sorted order in this case. Comparison sorts studied in the literature are "comparison-based". Elements a and b can be swapped or otherwise re-arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between a and b can be derived via the transitive closure of these prior comparison outcomes. For comparison-based sorts, the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis, the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or assignments.…
Article summary
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data; that is: # if a ≤ b and b ≤ c then a ≤ c (transitivity) # for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a with a ≠ b; in this case either may come first in the sorted list. In a stable sort, the input order determines the sorted order in this case. Comparison sorts studied in the literature are "comparison-based". Elements a and b can be swapped or otherwise re-arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between a and b can be derived via the transitive closure of these prior comparison outcomes. For comparison-based sorts, the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis, the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or assignments.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.