tag

#integer-sorting

6 pages tagged

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

Integer Sample Sort

Integer Sample Sort Integer sample sort is a specialization of sample sort for integer keys. It selects sample elements to estimate the distribution, chooses splitters, and partitions the array into buckets. Each bucket is then sorted recursively or with a suitable subroutine. Because keys are integers, classification can use arithmetic or bit operations, and buckets can be balanced more precisely than in general comparison sorting. Problem Given an array $A$...
algorithms sorting sample-sort integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Radix Sort

Radix Sort Radix sort sorts keys by decomposing them into smaller parts such as digits, bytes, or characters. Instead of comparing whole keys directly, it groups keys by one position at a time. It is most useful when keys have fixed width or bounded length, such as integers, fixed length strings, byte arrays, or identifiers. Problem Given an array $A$ of $n$ keys, sort the keys by their full value...
algorithms sorting radix-sort integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Signed Integer Radix Sort

Signed Integer Radix Sort Signed integer radix sort extends radix sorting to handle both negative and positive integers correctly. Since radix sort operates on digit or bit patterns, special handling is required to maintain numeric ordering. Problem Given an array $A$ of signed integers, sort the array in increasing order. Integers are represented in two's complement form, where direct unsigned interpretation does not preserve ordering. Idea Transform each integer into...
algorithms sorting radix-sort integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Coordinate Compression Sort

Coordinate Compression Sort Coordinate compression sort maps arbitrary values to a dense integer range based on their sorted order, then sorts using these compact indices. It is useful when values are large, sparse, or not directly suitable for counting or radix methods. Problem Given an array $A$ of values, possibly large integers or non-integer comparable items, sort the array efficiently by reducing the value domain. Idea Replace each value with...
algorithms sorting coordinate-compression integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Counting Sort with Negative Keys

Counting Sort with Negative Keys Counting sort normally assumes keys lie in a nonnegative range. This variant handles negative integers by shifting all values so that the minimum becomes zero, then applying standard counting sort. Problem Given an array $A$ of $n$ integers that may include negative values, sort the array. Let: $$ \min = \min(A),\quad \max = \max(A) $$ Idea Shift every value by $-\min$ so all keys become...
algorithms sorting counting-sort integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Counting Sort

Counting Sort Counting sort is a non-comparison sorting algorithm for integer keys within a bounded range. It counts how many times each value appears, then reconstructs the sorted order using these counts. It runs in linear time when the key range is not significantly larger than the number of elements. Problem Given an array $A$ of $n$ integers where each value lies in a range $[0, k]$, produce a sorted...
algorithms sorting counting-sort integer-sorting