tag

#string-sorting

5 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Three Way String Quicksort

Three Way String Quicksort Three way string quicksort is a refinement of multikey quicksort that uses three-way partitioning to efficiently handle repeated characters. It splits the array into less than, equal to, and greater than partitions based on the character at a given position. It is one of the most practical general-purpose string sorting algorithms. Problem Given an array $A$ of strings, sort them in lexicographic order. For string $s$,...
algorithms sorting string-sorting quicksort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Burstsort String Sorting

Burstsort String Sorting Burstsort string sorting is a trie based method for lexicographic string sorting. It stores strings in buckets attached to trie leaves. When a bucket grows too large, the bucket is split by the next character position. The method is designed for large string collections where comparison sorting repeatedly examines the same prefixes and causes poor cache behavior. Problem Given an array $A$ of strings, sort the strings...
algorithms sorting string-sorting burstsort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Burstsort

Burstsort Burstsort is a high performance string sorting algorithm designed for large datasets. It combines trie based partitioning with deferred sorting of small buckets to improve cache locality and reduce memory traffic. Instead of sorting the entire dataset directly, it incrementally builds a trie where leaves store buckets of strings. When a bucket grows beyond a threshold, it "bursts" into child nodes. Problem Given a large array of strings, sort...
algorithms sorting string-sorting burstsort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

American Flag String Sort

American Flag String Sort American flag string sort is an in-place MSD radix sort for strings. It partitions strings by the character at the current position, then recursively sorts each bucket by the next character. It uses the same bucket permutation idea as American flag sort, but the digit source is a string character rather than an integer digit. Problem Given an array $A$ of strings, sort the strings in...
algorithms sorting string-sorting radix-sort american-flag-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Multikey Quicksort

Multikey Quicksort Multikey quicksort is a string sorting algorithm that combines quicksort partitioning with radix-style character inspection. Instead of comparing whole strings each time, it partitions strings by the character at a current depth. It is especially effective for strings with shared prefixes because it avoids repeatedly comparing characters that are already known to be equal. Problem Given an array $A$ of strings, sort the strings in lexicographic order. For...
algorithms sorting string-sorting quicksort