Category:String sorting algorithms - Revision history

DB1729: Reverted 2 edits by Annekathrinhermann (talk): Misplaced content. This is a category page, not an article.

2024-03-01T22:32:44Z

Reverted 2 edits by Annekathrinhermann (talk): Misplaced content. This is a category page, not an article.

← Previous revision		Revision as of 22:32, 1 March 2024
Line 1:		Line 1:
	[[Category:Algorithms on strings\|Sorting]]		[[Category:Algorithms on strings\|Sorting]]
	[[Category:Sorting algorithms]]		[[Category:Sorting algorithms]]

	In [[computer science]], [[string]] [[sorting algorithms]] are a special case of [[sorting]] [[algorithms]]. The input is an [[array]] <math>S = [ s0,...,sn-1]</math> of <math>n</math> strings with characters from an alphabet {{math\|Σ}} in which the elements are then placed in the correct order.
	[[File:String Sorting.png\|thumb\|An example for sorting strings]]

	Unlike traditional sorting algorithms that deal with atomic keys, string sorting encounters unique challenges. Sorting strings using conventional atomic sorting algorithms, which treat keys as indivisible objects, is inefficient because comparing entire strings can be costly and must be performed numerous times. Efficient string sorting algorithms, in contrast, inspect most characters of the input only once during the entire sorting process and they examine only those characters that are necessary to establish the correct ordering. Another challenge is that strings are represented as arrays of [[pointers]]. This representation results in indirect access to string characters, leading to [[cache]] faults during the access, even when scanning an array of strings. This is in contrast to sorting atomic keys, where scanning is notably cache efficient. The [[efficiency]] of string sorting algorithms depens upon multiple factors, including the size of the dataset (<math>n</math>), the distinguishing prefix size of <math>S</math> (<math>D</math>), which is the minimal number of characters that need to be examined to sort the strings, the number of subproblems ({{math\|σ}}), into which the algorithm breaks down the problem, and the underlying hardware. This indicates that no singular algorithm is universally optimal.


	== Sequential Methods ==

	=== Multikey Quicksort ===
	[[File:Mulitkey Quicksort.png\|thumb\|An example for Mulitkey Quicksort for sorting strings]]
	Developed by Bentley and Sedgewick <ref>BENTLEY, Jon L.; SEDGEWICK, Robert. Fast algorithms for sorting and searching strings. In: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. 1997. S. 360-369.</ref>, this algorithm is an adaptation of the traditional [[Quicksort]], tailored for string sorting. It uses the character <math>x = s[h]</math> with a common prefix of length h as a splitter, organizing the strings into three distinct arrays based on their <math>(h+1)-th</math> character's relation to <math>x: <,>,=</math>. The algorithm recurses until the termination condition is met: if <math>x=0</math> termination with <math>S_=</math>. With Insertion Sort as a base case sorter for constant input sizes, multikey quicksort has a complexity of {{math\|O(D + n log n)}}.

	=== Most Significant Digit (MSD) Radix Sort ===
	[[File:MSD-Radix Sort.png\|thumb\|An example for MSD-Radix Sort for sorting strings]]
	Most Significant Digit (MSD) Radix Sort is especially efficient for sorting large datasets, particularly when the alphabet size is small <ref>KÄRKKÄINEN, Juha; RANTALA, Tommi. Engineering radix sort for strings. In: International Symposium on String Processing and Information Retrieval. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. S. 3-14.</ref>. The algorithm initiates sorting by examining the {{math\|(h+1)-th}} character of each string with <math>h</math> as the common prefix, subsequently dividing the dataset into {{math\|σ}} distinct subproblems. Each subproblem is then recursively sorted with the common prefix length <math>h + 1</math>. This strategy, which is a natural approach to string sorting, has been subject to numerous refinements and improvements across various studies in the literature <ref>KÄRKKÄINEN, Juha; RANTALA, Tommi. Engineering radix sort for strings. In: International Symposium on String Processing and Information Retrieval. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. S. 3-14.</ref> <ref>NG, Waihong; KAKEHI, Katsuhiko. Cache efficient radix sort for string sorting. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2007, 90. Jg., Nr. 2, S. 457-466.</ref> <ref>ANDERSSON, Arne; NILSSON, Stefan. Implementing radixsort. Journal of Experimental Algorithmics (JEA), 1998, 3. Jg., S. 7-es.</ref>. The [[time complexity]] is {{math\|O(D)}} plus the time required for sorting the base cases. For example, with multikey quicksort as the base case sorter MSD Radix Sort has a complexity of {{math\|O(D + n log σ)}}.

	=== Burstsort ===
	[[File:Burstsort.png\|thumb\|]]
	Burstsort <ref>SINHA, Ranjan; ZOBEL, Justin. Efficient trie-based sorting of large sets of strings. In: ACSC. 2003. S. 11-18.</ref> uses a [[trie]]<ref>HEINZ, Steffen; ZOBEL, Justin; WILLIAMS, Hugh E. Burst tries: a fast, efficient data structure for string keys. ACM Transactions on Information Systems (TOIS), 2002, 20. Jg., Nr. 2, S. 192-223.</ref>-based structure with containers at the leaves for sorting the strings. Upon reaching a predefined threshold, these containers "burst", redistributing the strings into new containers based on their next character. These new containers are then attached to the appropriate child nodes of the trie. The sorting process involves traversing the trie and individually sorting the small containers. Key factors influencing the runtime efficiency of Burstsort include the trie implementation, the design of the containers, the burst threshold, and the chosen base algorithm for sorting the containers. Sinha and Zoble <ref>SINHA, Ranjan; ZOBEL, Justin. Cache-conscious sorting of large sets of strings with dynamic tries. Journal of Experimental Algorithmics (JEA), 2004, 9. Jg., S. 1.5-es.</ref> used an array for each trie node and unordered dynamic arrays of string pointers for the leaf containers, with a bursting threshold set at {{math\|8192}}. With this configuration and Multikey Quicksort for sorting the leaves Burstsort has a complexity of {{math\|O(D + n log σ)}}.

	=== LCP-Mergesort ===

	LCP-Mergesort is an adaptation of the traditional [[Mergesort]] algorithm, which stores and reuses the longest common prefixes (LCPs) of consecutive strings in the sorted subproblems <ref>NG, Waihong; KAKEHI, Katsuhiko. Merging string sequences by longest common prefixes. IPSJ Digital Courier, 2008, 4. Jg., S. 69-78.</ref>. This strategy enhances the efficiency of string comparisons. In the conventional method the strings <math>s_a</math> and <math>s_b</math> must be compared character-by-character. However, with the LCP information for <math>s_a</math> and <math>s_b</math> relative to another string <math>p</math> of similar or smaller size allows the preliminary use of the LCP. If the LCP between <math>p</math> and <math>s_a</math> is shorter than that between <math>p</math> and <math>s_b</math>, it follows that <math>s_a</math> precedes <math>s_b</math> in lexicographical order due to <math>s_a</math> and <math>p</math> sharing a shorter common prefix than <math>s_b</math> and <math>p</math>. This also applies symmetrically. LCP-Mergesort has a worst-case time complexity of <math>O(D + n log n)</math>.

	=== Insertion Sort ===
	[[Insertion Sort]] <ref>MCCLELLAN, Michael T.; MINKER, Jack. The art of computer programming, vol. 3: sorting and searching. 1974.</ref> is frequently used as the base case sorter for small sets of strings. The algorithm stores an ordered array and inserts the unsorted items into their appropriate positions through linear scanning. This method treats strings as atomic units, necessitating full string comparisons during the linear scan to ensure the correct order. It has a worst-case time complexity of <math>O(nD)</math>. So it is particularly good for small <math>n</math> and <math>D</math>, due to the cache-efficient manner in which strings are scanned.

	== Parallel Methods ==
	The exploration of [[parallel]] string sorting algorithms remains limited, yet it is the only way to get performance out of [[Moore's Law]] <ref>MOORE, Gordon E. Cramming more components onto integrated circuits. Proceedings of the IEEE, 1998, 86. Jg., Nr. 1, S. 82-85.</ref>. The scalability of an algorithm in a parallel computing environment depends on various factors, similar to those affecting sequential methods. Many of the algorithms discussed in the sequential context can be adapted for parallel execution.

	== References ==

Annekathrinhermann at 20:30, 1 March 2024

2024-03-01T20:30:04Z

← Previous revision		Revision as of 20:30, 1 March 2024
Line 1:		Line 1:
	[[Category:Algorithms on strings\|Sorting]]		[[Category:Algorithms on strings\|Sorting]]
	[[Category:Sorting algorithms]]		[[Category:Sorting algorithms]]


	In [[computer science]], [[string]] [[sorting algorithms]] are a special case of [[sorting]] [[algorithms]]. The input is an [[array]] <math>S = [ s0,...,sn-1]</math> of <math>n</math> strings with characters from an alphabet {{math\|Σ}} in which the elements are then placed in the correct order.		In [[computer science]], [[string]] [[sorting algorithms]] are a special case of [[sorting]] [[algorithms]]. The input is an [[array]] <math>S = [ s0,...,sn-1]</math> of <math>n</math> strings with characters from an alphabet {{math\|Σ}} in which the elements are then placed in the correct order.

Annekathrinhermann at 20:29, 1 March 2024

2024-03-01T20:29:18Z

← Previous revision		Revision as of 20:29, 1 March 2024
Line 1:		Line 1:
	[[Category:Algorithms on strings\|Sorting]]		[[Category:Algorithms on strings\|Sorting]]
	[[Category:Sorting algorithms]]		[[Category:Sorting algorithms]]


			In [[computer science]], [[string]] [[sorting algorithms]] are a special case of [[sorting]] [[algorithms]]. The input is an [[array]] <math>S = [ s0,...,sn-1]</math> of <math>n</math> strings with characters from an alphabet {{math\|Σ}} in which the elements are then placed in the correct order.
			[[File:String Sorting.png\|thumb\|An example for sorting strings]]

			Unlike traditional sorting algorithms that deal with atomic keys, string sorting encounters unique challenges. Sorting strings using conventional atomic sorting algorithms, which treat keys as indivisible objects, is inefficient because comparing entire strings can be costly and must be performed numerous times. Efficient string sorting algorithms, in contrast, inspect most characters of the input only once during the entire sorting process and they examine only those characters that are necessary to establish the correct ordering. Another challenge is that strings are represented as arrays of [[pointers]]. This representation results in indirect access to string characters, leading to [[cache]] faults during the access, even when scanning an array of strings. This is in contrast to sorting atomic keys, where scanning is notably cache efficient. The [[efficiency]] of string sorting algorithms depens upon multiple factors, including the size of the dataset (<math>n</math>), the distinguishing prefix size of <math>S</math> (<math>D</math>), which is the minimal number of characters that need to be examined to sort the strings, the number of subproblems ({{math\|σ}}), into which the algorithm breaks down the problem, and the underlying hardware. This indicates that no singular algorithm is universally optimal.


			== Sequential Methods ==

			=== Multikey Quicksort ===
			[[File:Mulitkey Quicksort.png\|thumb\|An example for Mulitkey Quicksort for sorting strings]]
			Developed by Bentley and Sedgewick <ref>BENTLEY, Jon L.; SEDGEWICK, Robert. Fast algorithms for sorting and searching strings. In: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. 1997. S. 360-369.</ref>, this algorithm is an adaptation of the traditional [[Quicksort]], tailored for string sorting. It uses the character <math>x = s[h]</math> with a common prefix of length h as a splitter, organizing the strings into three distinct arrays based on their <math>(h+1)-th</math> character's relation to <math>x: <,>,=</math>. The algorithm recurses until the termination condition is met: if <math>x=0</math> termination with <math>S_=</math>. With Insertion Sort as a base case sorter for constant input sizes, multikey quicksort has a complexity of {{math\|O(D + n log n)}}.

			=== Most Significant Digit (MSD) Radix Sort ===
			[[File:MSD-Radix Sort.png\|thumb\|An example for MSD-Radix Sort for sorting strings]]
			Most Significant Digit (MSD) Radix Sort is especially efficient for sorting large datasets, particularly when the alphabet size is small <ref>KÄRKKÄINEN, Juha; RANTALA, Tommi. Engineering radix sort for strings. In: International Symposium on String Processing and Information Retrieval. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. S. 3-14.</ref>. The algorithm initiates sorting by examining the {{math\|(h+1)-th}} character of each string with <math>h</math> as the common prefix, subsequently dividing the dataset into {{math\|σ}} distinct subproblems. Each subproblem is then recursively sorted with the common prefix length <math>h + 1</math>. This strategy, which is a natural approach to string sorting, has been subject to numerous refinements and improvements across various studies in the literature <ref>KÄRKKÄINEN, Juha; RANTALA, Tommi. Engineering radix sort for strings. In: International Symposium on String Processing and Information Retrieval. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. S. 3-14.</ref> <ref>NG, Waihong; KAKEHI, Katsuhiko. Cache efficient radix sort for string sorting. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2007, 90. Jg., Nr. 2, S. 457-466.</ref> <ref>ANDERSSON, Arne; NILSSON, Stefan. Implementing radixsort. Journal of Experimental Algorithmics (JEA), 1998, 3. Jg., S. 7-es.</ref>. The [[time complexity]] is {{math\|O(D)}} plus the time required for sorting the base cases. For example, with multikey quicksort as the base case sorter MSD Radix Sort has a complexity of {{math\|O(D + n log σ)}}.

			=== Burstsort ===
			[[File:Burstsort.png\|thumb\|]]
			Burstsort <ref>SINHA, Ranjan; ZOBEL, Justin. Efficient trie-based sorting of large sets of strings. In: ACSC. 2003. S. 11-18.</ref> uses a [[trie]]<ref>HEINZ, Steffen; ZOBEL, Justin; WILLIAMS, Hugh E. Burst tries: a fast, efficient data structure for string keys. ACM Transactions on Information Systems (TOIS), 2002, 20. Jg., Nr. 2, S. 192-223.</ref>-based structure with containers at the leaves for sorting the strings. Upon reaching a predefined threshold, these containers "burst", redistributing the strings into new containers based on their next character. These new containers are then attached to the appropriate child nodes of the trie. The sorting process involves traversing the trie and individually sorting the small containers. Key factors influencing the runtime efficiency of Burstsort include the trie implementation, the design of the containers, the burst threshold, and the chosen base algorithm for sorting the containers. Sinha and Zoble <ref>SINHA, Ranjan; ZOBEL, Justin. Cache-conscious sorting of large sets of strings with dynamic tries. Journal of Experimental Algorithmics (JEA), 2004, 9. Jg., S. 1.5-es.</ref> used an array for each trie node and unordered dynamic arrays of string pointers for the leaf containers, with a bursting threshold set at {{math\|8192}}. With this configuration and Multikey Quicksort for sorting the leaves Burstsort has a complexity of {{math\|O(D + n log σ)}}.

			=== LCP-Mergesort ===

			LCP-Mergesort is an adaptation of the traditional [[Mergesort]] algorithm, which stores and reuses the longest common prefixes (LCPs) of consecutive strings in the sorted subproblems <ref>NG, Waihong; KAKEHI, Katsuhiko. Merging string sequences by longest common prefixes. IPSJ Digital Courier, 2008, 4. Jg., S. 69-78.</ref>. This strategy enhances the efficiency of string comparisons. In the conventional method the strings <math>s_a</math> and <math>s_b</math> must be compared character-by-character. However, with the LCP information for <math>s_a</math> and <math>s_b</math> relative to another string <math>p</math> of similar or smaller size allows the preliminary use of the LCP. If the LCP between <math>p</math> and <math>s_a</math> is shorter than that between <math>p</math> and <math>s_b</math>, it follows that <math>s_a</math> precedes <math>s_b</math> in lexicographical order due to <math>s_a</math> and <math>p</math> sharing a shorter common prefix than <math>s_b</math> and <math>p</math>. This also applies symmetrically. LCP-Mergesort has a worst-case time complexity of <math>O(D + n log n)</math>.

			=== Insertion Sort ===
			[[Insertion Sort]] <ref>MCCLELLAN, Michael T.; MINKER, Jack. The art of computer programming, vol. 3: sorting and searching. 1974.</ref> is frequently used as the base case sorter for small sets of strings. The algorithm stores an ordered array and inserts the unsorted items into their appropriate positions through linear scanning. This method treats strings as atomic units, necessitating full string comparisons during the linear scan to ensure the correct order. It has a worst-case time complexity of <math>O(nD)</math>. So it is particularly good for small <math>n</math> and <math>D</math>, due to the cache-efficient manner in which strings are scanned.

			== Parallel Methods ==
			The exploration of [[parallel]] string sorting algorithms remains limited, yet it is the only way to get performance out of [[Moore's Law]] <ref>MOORE, Gordon E. Cramming more components onto integrated circuits. Proceedings of the IEEE, 1998, 86. Jg., Nr. 1, S. 82-85.</ref>. The scalability of an algorithm in a parallel computing environment depends on various factors, similar to those affecting sequential methods. Many of the algorithms discussed in the sequential context can be adapted for parallel execution.

			== References ==

Qwertyus: ←Created page with 'Sorting Category:Sorting algorithms'

2015-11-13T11:34:28Z

←Created page with 'Sorting Category:Sorting algorithms'

New page

[[Category:Algorithms on strings|Sorting]]
[[Category:Sorting algorithms]]