Sorting Algorithm: Difference between revisions
m (Text replace - ".[" to ". [") |
|||
(37 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
A [[Sorting Algorithm]] is | A [[Sorting Algorithm]] is a [[data processing algorithm]] that can be applied by a [[Sorting System]] (to solve a [[Sorting Task]]). | ||
* <B>< | * <B>Context:</B> | ||
** [[ | ** It can be implemented by [[Sorting System]] to solve a [[Sorting Task]]. | ||
** [[Mergesort Algorithm]]. | ** It can range from being a [[Partial Sorting Algorithm]] to being a [[Total Sorting Algorithm]]. | ||
* <B>< | ** It can range from being a [[Comparative Sorting Algorithm]] to being a [[Non-Comparative Sorting Algorithm]]. | ||
** It can range from being a [[Simple Sorting Algorithm]] to being an [[Complex Sorting Algorithm]]. | |||
* <B>Example(s):</B> | |||
** [[Bead Sort Algorithm]], | |||
** [[Bogosort Algorithm]], | |||
** [[Simple Pancake Sort Algorithm]], | |||
** [[Spaghetti (Poll) Sort Algorithm]], | |||
** [[Sorting Network Algorithm]], | |||
** [[Bitonic Sorter Algorithm]], | |||
** [[Stooge Sort Algorithm]]. | |||
** [[Han's Algorithm]], | |||
** [[Thorup's Algorithm]], | |||
** an [[Index Sorting Algorithm]], | |||
** a [[String Sorting Algorithm]], | |||
** a [[Card Sorting Algorithm]] such as: | |||
*** a [[Dimensional Change Card Sort (DCCS) Algorithm]], | |||
*** a [[Wisconsin Card Sorting Test (WCST) Algorithm]], | |||
*** a [[Playing Card Sorting Algorithm]], | |||
** a [[Comparative Sorting Algorithm]] such as: | |||
*** [[Cubesort Algorithm]], | |||
*** [[Shell Sort Algorithm]], | |||
*** [[Binary Tree Sorting Algorithm]], | |||
** a [[Divide-and-Conquer Sorting Algorithm]] such as: | |||
*** a [[Bucket Sort Algorithm]], | |||
** an [[Efficient Sorting Algorithm]] such as: | |||
*** [[Timsort Algorithm]], | |||
*** [[Introsort Algorithm]], | |||
*** [[Mergesort Algorithm]], | |||
** a [[Non-Comparative Sorting Algorithm]] such as: | |||
*** an [[Integer Sorting Algorithm]], | |||
*** a [[Radix Sort Algorithm]], | |||
*** a [[Counting Sort Algorithm]], | |||
** an [[External Sorting Algorithm]] such as: | |||
*** a [[Distribution Sort Algorithm]], | |||
** a [[Recursive Sorting Algorithm]] such as: | |||
*** [[Stooge Sort Algorithm]], | |||
** a [[Simple Sorting Algorithm]] such as: | |||
*** a [[Bubble Sort Algorithm]], | |||
*** a [[Comb Sort Algorithm]]. | |||
*** an [[Insertion Sort Algorithm]]. | |||
** … | |||
* <B>Counter-Example(s):</B> | |||
** [[Randomization Algorithm]], | |||
** [[Selection Algorithm]], | |||
** [[Shuffling Algorithm]]. | |||
* <B>See:</B> [[Order Relation]], [[Lexicographical Order]], [[Search Algorithm]], [[Merge Algorithm]], [[Permutation]], [[Index Data Structure]][[Computer Science]], [[Algorithm]], [[List (Computing)]], [[Total Order]], [[Numerical Order]], [[Lexicographical Order]], [[Sorting]], [[Algorithmic Efficiency]], [[Search Algorithm]], [[Merge Algorithm]], [[Canonicalization]]. | |||
---- | ---- | ||
---- | ---- | ||
==References == | |||
* (Wikipedia, | == References == | ||
** In computer science | |||
** | === 2023 === | ||
** | * ([[2023_FasterSortingAlgorithmsDiscover|Mankowitz et al., 2023]]) ⇒ [[Daniel J. Mankowitz]], [[Andrea Michi]], [[Anton Zhernov]], [[Marco Gelmi]], [[Marco Selvi]], [[Cosmin Paduraru]], [[Edouard Leurent]], [[Shariq Iqbal]], [[Jean-Baptiste Lespiau]], [[Alex Ahern]], [[Thomas Köppe]], [[Kevin Millikin]], [[Stephen Gaffney]], [[Sophie Elster]], [[Jackson Broshear]], [[Chris Gamble]], [[Kieran Milan]], [[Robert Tung]], [[Minjae Hwang]], [[Taylan Cemgil]], [[Mohammadamin Barekatain]], [[Yujia Li]], [[Amol Mandhane]], [[Thomas Hubert]], [[Julian Schrittwieser]], [[Demis Hassabis]], [[Pushmeet Kohli]], [[Martin Riedmiller]], [[Oriol Vinyals]], and [[David Silver]]. ([[2023]]). “[https://www.nature.com/articles/s41586-023-06004-9 Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning].” In: Nature, 618(7964). | ||
=== 2020a === | |||
* (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Sorting_algorithm Retrieved:2020-1-5. | |||
** In [[computer science]], a '''sorting algorithm''' is an [[algorithm]] that puts elements of a [[List (computing)|list]] in a certain [[Total order|order]]. The most frequently used orders are [[numerical order]] and [[lexicographical order]]. Efficient [[sorting]] is important for optimizing the [[Algorithmic efficiency|efficiency]] of other algorithms (such as [[search algorithm|search]] and [[merge algorithm|merge]] algorithms) that require input data to be in sorted lists. Sorting is also often useful for [[Canonicalization|canonicalizing]] data and for producing human-readable output. More formally, the output of any sorting algorithm must satisfy two conditions: | |||
**# The output is in nondecreasing order (each element is no smaller than the previous element according to the desired [[total order]]); | |||
**# The output is a [[permutation]] (a reordering, yet retaining all of the original elements) of the input. | |||
:: Further, the input data is often stored in an [[Array data type|array]], which allows [[random access]], rather than a list, which only allows [[sequential access]]; though many algorithms can be applied to either type of data after suitable modification. <P> Sorting algorithms are often referred to as a word followed by the word "sort," and grammatically are used in English as noun phrases, for example in the sentence, "it is inefficient to use insertion sort on large lists," the phrase ''insertion sort'' refers to the [[insertion sort]] sorting algorithm. | |||
=== 2020b === | |||
* (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Cognitive_flexibility Retrieved:2020-1-31. | |||
** '''Cognitive flexibility''' has been described as the mental ability to switch between thinking about two different concepts, and to think about multiple concepts simultaneously.<ref name="Scott">Scott, William A. (December 1962). “Cognitive complexity and cognitive flexibility". Sociometry. 25 (4): 405–414. doi:10.2307/2785779. JSTOR 2785779.</ref> Cognitive flexibility is usually described as one of the [[executive functions]].<ref name="Cooper-Kahn">Cooper-Kahn, Joyce; Dietzel, Laurie C. (2008). “What is executive functioning?". ldonline.org. National Center for Learning Disabilities and WETA-TV. Archived from the original on September 20, 2014.</ref> Two subcategories of cognitive flexibility are [[Task switching (psychology)|task switching]] and [[cognitive shifting]], depending on whether the change happens unconsciously or consciously, respectively. <P> Cognitive flexibility varies during the lifespan of an individual.<ref name="Chelune">Chelune, Gordon J.; Baer, Ruth A. (1986). “Developmental norms for the Wisconsin Card Sorting Test". Journal of Clinical and Experimental Neuropsychology. 8 (3): 219–228. doi:10.1080/01688638608401314. PMID 3722348.</ref> In addition, certain conditions such as [[obsessive–compulsive disorder]] are associated with reduced cognitive flexibility. Since cognitive flexibility is a vital component of learning,<ref name="Boger-Mehall">Boger-Mehall, Stephanie R. (1996). “Cognitive flexibility theory: implications for teaching and teacher education". learntechlib.org. Association for the Advancement of Computing in Education. pp. 991–993. Archived from the original on March 9, 2018. Retrieved November 18, 2012.</ref> deficits in this area might have other implications. <P> Methods of measuring cognitive flexibility include the [[A-not-B task]], [[Dimensional Change Card Sorting Task]], [[Multiple Classification Card Sorting Task]], [[Wisconsin Card Sorting Task]], and the [[Stroop Test]]. [[Functional Magnetic Resonance Imaging]] (fMRI) research has shown that specific brain regions are activated when a person engages in cognitive flexibility tasks. These regions include the [[prefrontal cortex]] (PFC), [[basal ganglia]], [[anterior cingulate cortex]] (ACC), and [[posterior parietal cortex]] (PPC).<ref name="Leber 13592–7">Leber, A B; Turk-Browne N B; Chun M M (September 9, 2008). “Neural predictors of moment-to-moment fluctuations in cognitive flexibility". Proceedings of the National Academy of Sciences. 105 (36): 13592–7. doi:10.1073/pnas.0805423105. PMC 2527350. PMID 18757744.</ref> Studies conducted with people of various ages and with particular deficits have further informed how cognitive flexibility develops and changes within the brain. | |||
<references/> | |||
---- | ---- | ||
__NOTOC__ | __NOTOC__ | ||
[[Category:Concept]] | [[Category:Concept]] | ||
[[Category:Data Science]] | |||
[[Category:Machine Learning]] | |||
[[Category:Quality Silver]] | |||
__NOTOC__ |
Latest revision as of 19:59, 10 June 2024
A Sorting Algorithm is a data processing algorithm that can be applied by a Sorting System (to solve a Sorting Task).
- Context:
- It can be implemented by Sorting System to solve a Sorting Task.
- It can range from being a Partial Sorting Algorithm to being a Total Sorting Algorithm.
- It can range from being a Comparative Sorting Algorithm to being a Non-Comparative Sorting Algorithm.
- It can range from being a Simple Sorting Algorithm to being an Complex Sorting Algorithm.
- Example(s):
- Bead Sort Algorithm,
- Bogosort Algorithm,
- Simple Pancake Sort Algorithm,
- Spaghetti (Poll) Sort Algorithm,
- Sorting Network Algorithm,
- Bitonic Sorter Algorithm,
- Stooge Sort Algorithm.
- Han's Algorithm,
- Thorup's Algorithm,
- an Index Sorting Algorithm,
- a String Sorting Algorithm,
- a Card Sorting Algorithm such as:
- a Comparative Sorting Algorithm such as:
- a Divide-and-Conquer Sorting Algorithm such as:
- an Efficient Sorting Algorithm such as:
- a Non-Comparative Sorting Algorithm such as:
- an External Sorting Algorithm such as:
- a Recursive Sorting Algorithm such as:
- a Simple Sorting Algorithm such as:
- …
- Counter-Example(s):
- See: Order Relation, Lexicographical Order, Search Algorithm, Merge Algorithm, Permutation, Index Data StructureComputer Science, Algorithm, List (Computing), Total Order, Numerical Order, Lexicographical Order, Sorting, Algorithmic Efficiency, Search Algorithm, Merge Algorithm, Canonicalization.
References
2023
- (Mankowitz et al., 2023) ⇒ Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Minjae Hwang, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane, Thomas Hubert, Julian Schrittwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals, and David Silver. (2023). “Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning.” In: Nature, 618(7964).
2020a
- (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Sorting_algorithm Retrieved:2020-1-5.
- In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. More formally, the output of any sorting algorithm must satisfy two conditions:
- The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
- The output is a permutation (a reordering, yet retaining all of the original elements) of the input.
- In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. More formally, the output of any sorting algorithm must satisfy two conditions:
- Further, the input data is often stored in an array, which allows random access, rather than a list, which only allows sequential access; though many algorithms can be applied to either type of data after suitable modification.
Sorting algorithms are often referred to as a word followed by the word "sort," and grammatically are used in English as noun phrases, for example in the sentence, "it is inefficient to use insertion sort on large lists," the phrase insertion sort refers to the insertion sort sorting algorithm.
- Further, the input data is often stored in an array, which allows random access, rather than a list, which only allows sequential access; though many algorithms can be applied to either type of data after suitable modification.
2020b
- (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Cognitive_flexibility Retrieved:2020-1-31.
- Cognitive flexibility has been described as the mental ability to switch between thinking about two different concepts, and to think about multiple concepts simultaneously.[1] Cognitive flexibility is usually described as one of the executive functions.[2] Two subcategories of cognitive flexibility are task switching and cognitive shifting, depending on whether the change happens unconsciously or consciously, respectively.
Cognitive flexibility varies during the lifespan of an individual.[3] In addition, certain conditions such as obsessive–compulsive disorder are associated with reduced cognitive flexibility. Since cognitive flexibility is a vital component of learning,[4] deficits in this area might have other implications.
Methods of measuring cognitive flexibility include the A-not-B task, Dimensional Change Card Sorting Task, Multiple Classification Card Sorting Task, Wisconsin Card Sorting Task, and the Stroop Test. Functional Magnetic Resonance Imaging (fMRI) research has shown that specific brain regions are activated when a person engages in cognitive flexibility tasks. These regions include the prefrontal cortex (PFC), basal ganglia, anterior cingulate cortex (ACC), and posterior parietal cortex (PPC).[5] Studies conducted with people of various ages and with particular deficits have further informed how cognitive flexibility develops and changes within the brain.
- Cognitive flexibility has been described as the mental ability to switch between thinking about two different concepts, and to think about multiple concepts simultaneously.[1] Cognitive flexibility is usually described as one of the executive functions.[2] Two subcategories of cognitive flexibility are task switching and cognitive shifting, depending on whether the change happens unconsciously or consciously, respectively.
- ↑ Scott, William A. (December 1962). “Cognitive complexity and cognitive flexibility". Sociometry. 25 (4): 405–414. doi:10.2307/2785779. JSTOR 2785779.
- ↑ Cooper-Kahn, Joyce; Dietzel, Laurie C. (2008). “What is executive functioning?". ldonline.org. National Center for Learning Disabilities and WETA-TV. Archived from the original on September 20, 2014.
- ↑ Chelune, Gordon J.; Baer, Ruth A. (1986). “Developmental norms for the Wisconsin Card Sorting Test". Journal of Clinical and Experimental Neuropsychology. 8 (3): 219–228. doi:10.1080/01688638608401314. PMID 3722348.
- ↑ Boger-Mehall, Stephanie R. (1996). “Cognitive flexibility theory: implications for teaching and teacher education". learntechlib.org. Association for the Advancement of Computing in Education. pp. 991–993. Archived from the original on March 9, 2018. Retrieved November 18, 2012.
- ↑ Leber, A B; Turk-Browne N B; Chun M M (September 9, 2008). “Neural predictors of moment-to-moment fluctuations in cognitive flexibility". Proceedings of the National Academy of Sciences. 105 (36): 13592–7. doi:10.1073/pnas.0805423105. PMC 2527350. PMID 18757744.