Topic: sort algorithms

topics > computer science > Group: algorithms

external search and sort
search algorithms
database keys and indexing
string operations
Subtopic: search and sort algorithms up

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 up

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

Subtopic: quick sort up

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 up

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 up

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

Subtopic: hash-based sort up

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 up

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]

Subtopic: radix sort up

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 up

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

Subtopic: avoid sorting up

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

Related Topics up

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
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.