A sorted array is an
array data structure
In computer science, an array is a data structure consisting of a collection of ''elements'' (value (computer science), values or variable (programming), variables), of same memory size, each identified by at least one ''array index'' or ''key' ...
in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
to implement
static lookup tables to hold multiple values which have the same
data type
In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these ...
. Sorting an array is useful in organising
data
Data ( , ) are a collection of discrete or continuous values that convey information, describing the quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted for ...
in ordered form and recovering them rapidly.
Overview
Sorted arrays are the most space-efficient data structure with the best
locality of reference
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
for sequentially stored data.
Elements within a sorted array are found using a
binary search, in O(log ''n''); thus sorted arrays are suited for cases when one needs to be able to look up elements quickly, e.g. as a
set or
multiset data structure
In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
. This complexity for lookups is the same as for
self-balancing binary search trees.
In some data structures, an array of structures is used. In such cases, the same sorting methods can be used to sort the structures according to some key as a structure element; for example, sorting records of students according to roll numbers or names or grades.
If one is using a sorted
dynamic array, then it is possible to insert and delete elements. The insertion and deletion of elements in a sorted array executes at O(''n''), due to the need to shift all the elements following the element to be inserted or deleted; in comparison a self-balancing binary search tree inserts and deletes at O(log ''n''). In the case where elements are deleted or inserted at the end, a sorted dynamic array can do this in
amortized O(1) time while a self-balancing binary search tree always operates at O(log ''n'').
Elements in a sorted array can be looked up by their index (
random access) at O(1) time, an operation taking O(log ''n'') or O(''n'') time for more complex data structures.
History
John von Neumann
John von Neumann ( ; ; December 28, 1903 – February 8, 1957) was a Hungarian and American mathematician, physicist, computer scientist and engineer. Von Neumann had perhaps the widest coverage of any mathematician of his time, in ...
wrote the first array sorting program (
merge sort
In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, wh ...
) in 1945, when the
first stored-program computer was still being built.
See also
*
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending ...
*
Binary search algorithm
*
Heap (data structure)
In computer science, a heap is a Tree (data structure), tree-based data structure that satisfies the heap property: In a ''max heap'', for any given Node (computer science), node C, if P is the parent node of C, then the ''key'' (the ''value'') o ...
*
Search data structure
References
{{reflist, 2
Arrays