Sorted array
Encyclopedia
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
to implement static lookup table
s to hold multiple values which has the same data type
. Sorting an array is useful in organising data
in ordered form and recovering it rapidly.
Some of them are Selection sort
, Bubble sort
, Insertion sort
, Merge sort
, Quick sort, Heap sort, and counting sort
. These sorting techniques have different algorithms. Hence there are different advantages of each method.
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 lookup elements quickly, e.g. as a set
or multiset data structure
. This complexity for lookups is the same as for self-balancing binary search tree
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 we are 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.
wrote the first array sorting program (merge sort
) in 1945, when the first stored-program computer
was still being built.
Government organisations, private companies and many web based applications has to deal with huge amount of data. This data is stored by sorting it using different sorting algorithms. This can be used in quick and easy recovery of data.
2) In discrete mathematics
:
Sorted arrays can be used to implement Dijkstra's algorithm
or Prim's algorithm
. Also, algorithms like Kruskal's Algorithm
for finding minimal spanning trees.
3) In priority scheduling: At the operating system
level many processes are pending at a time, but CPU can handle only one process at single instance of time. Therefore, priorities are associated to each process.Then the processes are sent to CPU according to the highest priority by using sorted array of process ID's. Here, processes got sorted depending upon there 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.
4) 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
to implement static lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
s to hold multiple values which has the same data type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
. Sorting an array is useful in organising data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
in ordered form and recovering it rapidly.
Methods
There are many well-known methods by which an array can be sorted.Some of them are Selection sort
Selection sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort...
, Bubble sort
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
, Insertion sort
Insertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
, Merge sort
Merge sort
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
, Quick sort, Heap sort, and counting sort
Counting sort
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to...
. These sorting techniques have different algorithms. Hence there are different advantages of each method.
Overview
Sorted arrays are the most space efficient data structure with the best locality of referenceLocality of reference
In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources...
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 lookup elements quickly, e.g. as a set
Set (computer science)
In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...
or multiset data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
. This complexity for lookups is the same as for self-balancing binary search tree
Self-balancing binary search tree
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
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 we are using a sorted dynamic array
Dynamic array
In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
, 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
Self-balancing binary search tree
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
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
Amortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
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
Random access
In computer science, random access is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "random access"...
) at O(1) time, an operation taking O(log n) or O(n) time for more complex data structures.
History
John von NeumannJohn von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
wrote the first array sorting program (merge sort
Merge sort
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
) in 1945, when the first stored-program computer
EDVAC
EDVAC was one of the earliest electronic computers. Unlike its predecessor the ENIAC, it was binary rather than decimal, and was a stored program computer....
was still being built.
Applications of sorted arrays
1) Commercial Computing:Government organisations, private companies and many web based applications has to deal with huge amount of data. This data is stored by sorting it using different sorting algorithms. This can be used in quick and easy recovery of data.
2) In discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
:
Sorted arrays can be used to implement Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
or Prim's algorithm
Prim's algorithm
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
. Also, algorithms like Kruskal's Algorithm
Kruskal's algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
for finding minimal spanning trees.
3) In priority scheduling: At the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
level many processes are pending at a time, but CPU can handle only one process at single instance of time. Therefore, priorities are associated to each process.Then the processes are sent to CPU according to the highest priority by using sorted array of process ID's. Here, processes got sorted depending upon there 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.
4) 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.
| Process | Burst time |
|---|---|
| P1 | 3 |
| P2 | 4 |
| P3 | 1 |
| P4 | 8 |
| P5 | 6 |
See Also
- array data structure
- insertion sortInsertion sortInsertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
- sorting algorithmSorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
- binary search algorithmBinary search algorithmIn computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
- bubble sortBubble sortBubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
- Insertion sortInsertion sortInsertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
- Kruskal's AlgorithmKruskal's algorithmKruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
- Prim's algorithmPrim's algorithmIn computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
.