Sorting Algorithm: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
m (Text replace - ".[" to ". [")
 
 
(37 intermediate revisions by 4 users not shown)
Line 1: Line 1:
A [[Sorting Algorithm]] is an [[Algorithm]] that can solve a [[Sorting Task]].
A [[Sorting Algorithm]] is a [[data processing algorithm]] that can be applied by a [[Sorting System]] (to solve a [[Sorting Task]]).
* <B><U>Example(s)</U>:</B>  
* <B>Context:</B>
** [[Quicksort Algorithm]].
** 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><U>See</U>:</B> [[Order Relation]], [[String 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]].
* <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, 2009) &rArr; http://en.wikipedia.org/wiki/Sorting_algorithm
== References ==
** In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:
 
*** 1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
=== 2023 ===
*** 2. The output is a permutation, or reordering, of the input.
* ([[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).
** The sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement. For example, bubble sort was analyzed as early as 1956. [1] Although many consider it a solved problem, useful new sorting algorithms are still being invented (for example, library sort was first published in 2004). Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notation, divide and conquer algorithms, data structures, randomized algorithms, best, worst and average case analysis, time-space tradeoffs, and lower bounds.
 
=== 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).



References

2023

2020a

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.

2020b

  1. Scott, William A. (December 1962). “Cognitive complexity and cognitive flexibility". Sociometry. 25 (4): 405–414. doi:10.2307/2785779. JSTOR 2785779.
  2. 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.
  3. 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.
  4. 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.
  5. 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.