Map Index Random Help Topics

## Topic: sort algorithms

topics > computer science > Group: algorithms

Topic:
external search and sort
Topic:
search algorithms
Topic:
database keys and indexing
Topic:
b-trees
Topic:
string operations
Subtopic: search and sort algorithms

 Quote: algorithms for string search and sort; radix quicksort and ternary search trees [»bentJL1_1997] Quote: survey of sorting in database systems; in-memory sorting, disk-based external sorting, implementation techniques [»graeG9_2006]

Subtopic: duplicate detection

 Quote: delete duplicates by multiple passes using hashing; linear average time; constant extra space [»teuhJ3_1991]

Subtopic: quick sort

 Quote: quicksort algorithm; recursively partitions data by key [»hoarCA1_1962] Quote: improve quicksort on long keys with codewords; count of equal bytes, first nonequal byte, record pointer [»baerJL5_1989] Quote: library qsorts can be easily driven to quadratic behavior; derived from 7th edition Unix or 1983 Berkeley functions [»bentJL11_1993] Quote: implement qsort with different medians depending on size; insertion sort, middle element, median of three, median of nine [»bentJL11_1993] Quote: tripartite partitioning in qsort is equivalent to the Dutch National Flag problem; place equal elements at either end [»bentJL11_1993] Quote: better swapping and other improvements to qsort is on average 2x faster than previous versions; up to 12x [»bentJL11_1993]

Subtopic: sort algorithms

 Quote: proportion extended sort (psort); faster than qsort; linear on already sorted input; O(n log n) comparisons [»chenJC7_2004] Quote: proportion extended sort based on a sorted subsequence followed by an unsorted subsequence; uses reference elements to identify non-random inputs [»chenJC7_2004] Quote: psort uses fewer comparisons than qsort; faster for sorted input, nearly sorted input, random input, and random binary [»chenJC7_2004]

Subtopic: swap

 Quote: provides a formula to check data size and alignment; works on many machines including Crays [»bentJL11_1993]

Subtopic: hash-based sort

 Quote: trie hash by sort on leading digits with split between buckets by a prefix; better than B-tree, can 100% load for ordered insertion [»litwWA7_1991] Quote: linear probing sort for uniformly distributed elements; hash into range and shift as needed [»carlS2_1991] Quote: linear hashing with partial expansions and priority splitting; 80% storage utilization, 1 block access per search, and 8% overflow space [»manoY5_1994] Quote: use n-gram-hash-and-skip for matching keywords in a large dictionary of 10,000-100,000 entries [»coheJD12_1998]

Subtopic: nearly sorted lists

 Quote: for nearly sorted lists, insertion sort is best for small or very-nearly sorted lists; otherwise use Quicker-sort [»cookCR11_1980] Quote: for nearly sorted lists, separate into sorted and unsorted lists, then sort and merge [»cookCR11_1980]

 Quote: radix sort by bytes is faster than Quicksort [»daviIJ12_1992] Quote: radix quicksort for strings skips over common prefixes; can be 4 times faster than qsort [»bentJ11_1998] Quote: use American flag radix sort when comparison is not unit-time; best for heavy-duty sorting of at least 10,000 keys [»mcilPM1_1993]

Subtopic: history

 Quote: first table in lexicographic order; reciprocals of numbers [»knutDE7_1972]

Subtopic: avoid sorting

 Quote: compare SQL queries across multiple vendors; avoid sorting by comparing row counts and column checksums [»slutD8_1998, OK]

Related Topics

Topic: external search and sort (23 items)
Topic: search algorithms (40 items)
Topic: database keys and indexing (18 items)
Topic: b-trees (16 items)
Topic: string operations
(20 items)

Updated barberCB 10/05