Sorted array
| Sorted array | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | Array | ||||||||||||||||||||
| Invented | 1945 | ||||||||||||||||||||
| Invented by | John von Neumann | ||||||||||||||||||||
| Time complexity in big O notation | |||||||||||||||||||||
|
|||||||||||||||||||||
| Algorithm | Average | Worst Case | |
|---|---|---|---|
| Space | O(n) | O(n) | |
| Search | O(log n) | O(log n) | |
| Insert | O(n) | O(n) | |
| Delete | O(n) | O(n) |
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 tables to hold multiple values which have the same data type. Sorting an array is useful in organising data in ordered form and recovering them rapidly.
There are many well-known methods by which an array can be sorted, which include, but are not limited to: selection sort, bubble sort, insertion sort, merge sort, quicksort, heapsort, and counting sort. These sorting techniques have different algorithms associated with them, and there are therefore different advantages to using each method.
Sorted arrays are the most space-efficient data structure with the best locality of reference 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. 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.
...
Wikipedia