A sorted array is an
array data structure 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, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
to implement
static
Static may refer to:
Places
*Static Nunatak, a nunatak in Antarctica
United States
* Static, Kentucky and Tennessee
*Static Peak, a mountain in Wyoming
**Static Peak Divide, a mountain pass near the peak
Science and technology Physics
*Static el ...
lookup tables to hold multiple values which have the same
data type. Sorting an array is useful in organising
data
In the pursuit of knowledge, data (; ) is a collection of discrete Value_(semiotics), values that convey information, describing quantity, qualitative property, quality, fact, statistics, other basic units of meaning, or simply sequences of sy ...
in ordered form and recovering them rapidly.
Methods
There are many well-known methods by which an array can be sorted, which include, but are not limited to:
Selection sort
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is no ...
,
Bubble sort,
Insertion sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Ho ...
,
Merge sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
,
Quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
,
Heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
, and
Counting sort
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess dis ...
. These sorting techniques have different algorithms associated with them, and there are therefore different advantages to using each method.
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 computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
, 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
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
data structure. This complexity for lookups is the same as for
self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donal ...
s.
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
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case ...
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 (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...
wrote the first array sorting program (
merge sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
) in 1945, when the
first stored-program computer was still being built.
Applications of sorted arrays
Commercial computing
Government organizations, private companies and many web-based applications have to deal with huge amounts of data. The data will often have to be accessed multiple times. Keeping the data in a sorted format allows for quick and easy retrieval.
In discrete mathematics
Sorted arrays can be used to implement
Dijkstra's algorithm
Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
or
Prim's algorithm
In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every v ...
. Also, algorithms like
Kruskal's algorithm for finding minimal spanning trees.
In priority scheduling
At the
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also i ...
level, many processes are pending at a time but they can handle only one process at a single instance in time. Therefore, priorities are associated to each process. Then the processes are sent to the CPU according to the highest priority by using sorted array of process IDs. Here, processes got sorted depending upon their priorities and then CPU is allocated to them. The process having the highest priority takes first position in sorted array. Hence priority-wise system processes scheduling is done.
In shortest-job-first scheduling
This is the special case of priority scheduling. Here, processes get sorted according to burst time of the processes. The process requiring the shortest time will be allocated CPU first. Hence, processes are being sent to CPU according to their burst time.
See also
*
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important ...
*
Binary search algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
*
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a ''max heap'', for any given node C, if P is a parent node of C, then the ''key'' (the ''val ...
*
Search data structure
References
{{reflist, 2
Arrays